11.19.2018
1042.D Petya and Array
New Point：
前缀 + 树状数组 ：树状数组逐个维护前缀个数
Describe:
给你一个数组，一个标记数，问你有多少区间[l,r]使得这个区间的和小于这个标记数值
Solution:
没能想到
前缀数组 + 树状数组快速查询
记录前缀数组sum[i]，得到区间和为sum[i] - sum[j] < t，转化为求sum[i] - t < sum[j],遍历i，求取情况，然后利用树状数组快速查询符合的区间j的个数
树状数组维护的是 sum[j],而且遍历i[1,n]的时候j的范围是[0,i-1]，所以对于一个新i，我们应该找到sum[i-1]在树上的位置进行全局更新，但是对于第一个i，更新sum[0] = 0即可，可以想到j取0的时候表示a1 + …… + ai
Code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 1e3;
ll sum[maxn];
ll f[maxn];
ll tree[maxn];
int n;
ll lowbit(ll x)
{
return x & (-x);
}
void add(ll x)
{
while(x <= n+1)
{
++tree[x];
x += lowbit(x);
}
}
ll Get(ll x)
{
ll ans = 0;
while(x > 0)
{
ans += tree[x];
x -=lowbit(x);
}
return ans;
}
int main()
{
ll t;
while(~scanf("%d %lld",&n,&t))
{
memset(sum,0,sizeof(sum));
memset(tree,0,sizeof(tree));
for(int i = 1;i <= n;++i)
{
scanf("%lld",&sum[i]);
sum[i] += sum[i-1];
f[i] = sum[i];
}
f[0] = 0;
sort(f,f+n+1);
ll ans = 0;
for(int i = 1;i <= n;++i)
{
add(lower_bound(f,f+n+1,sum[i-1]) + 1 - f);
ans += i - Get(lower_bound(f,f+n+1,sum[i] - t + 1) - f);
}
printf("%lld\n",ans);
}
return 0;
}