?
?log2S(i,j)?+1 就是S(i,j) 的二进制位数.....
枚举二进制的每一位数,计算相应的权值
具体作法就是对每个二进制位数 i ,扫一遍数组,对每个数 j 维护一个L,R 表示以该数为左端点,右端点可以在L~R的范围,这个区间内的值
加起来有 i 位二进制位数,那么这个数对答案的贡献为 设: dur = (R-L+1) 贡献值: dur*j+(R+L)*dur/2
?
C++秒T , G++ 1.3s ac
?
First One
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1183 Accepted Submission(s): 357
Problem Description soda has an integer array
a1,a2,…,an
. Let
S(i,j)
be the sum of
ai,ai+1,…,aj
. Now soda wants to know the value below:
∑i=1n∑j=in(?log2S(i,j)?+1)×(i+j)
Note: In this problem, you can consider
log20
as 0.
Input There are multiple test cases. The first line of input contains an integer
T
, indicating the number of test cases. For each test case:
The first line contains an integer
n
(1≤n≤105)
, the number of integers in the array.
The next line contains
n
integers
a1,a2,…,an
(0≤ai≤105)
.
Output For each test case, output the value.
Sample Input
1
2
1 1
Sample Output
12
Source 2015 Multi-University Training Contest 6
?
?
/* ***********************************************
Author :CKboss
Created Time :2015年08月07日 星期五 16时48分08秒
File Name :HDOJ5358.cpp
************************************************ */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include