原题链接
考察:双指针
思路:
??很明显可以枚举\(log_2sum(i,j)\)的值,然后枚举左端点求右端点的区间,用二分TLE到我整个人都麻了,看题解是用双指针...
??我自己想的是用枚举右端点,二分求左端点区间,也是TLE...
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010,M = 35;
int n;
LL sum[N],logs[M];
int main()
{
int T;
scanf("%d", &T);
for(int i=1;i<M;i++) logs[i] = 1ll<<i;
while(T--)
{
scanf("%d", &n);
for (int i = 1; i <= n;i++)
{
scanf("%lld", &sum[i]);
sum[i] += sum[i - 1];
}
LL res = 0;
for(int j=0;j<35;j++)
{
if(sum[n]<logs[j]) break;
int l = 1,r = 0;
for(int i=1;i<=n;i++)
{
if(sum[i-1]+logs[j]>sum[n]) break;
// int l = lower_bound(sum+i,sum+n+1,sum[i-1]+logs[j])-sum;
// int r = lower_bound(sum+i,sum+n+1,sum[i-1]+logs[j+1])-sum;
l = max(l,i);
while(l<=n&&sum[l]-sum[i-1]<logs[j]) l++;
r = max(l-1,r);
while(r+1<=n&&sum[r+1]-sum[i-1]<logs[j+1]) r++;
if(l>r) continue;
res+=((LL)(r-l+1)*(l+r)/2+(LL)(r-l+1)*i)*(j+1);
}
}
printf("%lld\n", res);
}
return 0;
}