CF Round #510 (Div. 2) D - Petya and Array (树状数组)
Link
http://codeforces.com/contest/1042/problem/D
Description
Problem Statement
Petya has an array a consisting of n
integers. He has learned partial sums recently, and now he can calculate the sum of elements on any segment of the array really fast. The segment is a non-empty sequence of elements standing one next to another in the array.
Now he wonders what is the number of segments in his array with the sum less than t.
Help Petya to calculate this number.
More formally, you are required to calculate the number of pairs l,r(l≤r) such that al+al+1+⋯+ar−1+ar<t.
Input
The first line contains two integers n and t (1≤n≤200000,|t|≤2⋅1014).
The second line contains a sequence of integers a1,a2,…,an(|ai|≤109) — the description of Petya’s array. Note that there might be negative, zero and positive elements.
Output
Print the number of segments in Petya’s array with the sum of elements less than t.
Sample Input
5 4
5 -1 3 4 -1
Sample Output
5
Sample Input
3 0
-1 2 -3
Sample Output
4
Solution
题意即让求区间和小于的区间的个数。即求,即我们需要求满足的,并且满足的,即对所有的,求出大于的并且小于的的个数。
这里即为求逆序对(),那么就使用树状数组,由于序列中为,所以还需要离散化一下。具体参考逆序数求法。
Code
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<unordered_map>
using namespace std;
#pragma GCC optimize(2)
#define maxn 200090
#define inf 0x3f3f3f3f
#define PI acos(-1)
typedef long long ll;
struct edge{
int u,v,next,w;
}e[2];
int head[1],cnt;
void add(int x,int y,int w){
e[cnt].u=x;
e[cnt].v=y;
e[cnt].w=w;
e[cnt].next=head[x];
head[x]=cnt++;
e[cnt].u=y;
e[cnt].v=x;
e[cnt].w=w;
e[cnt].next=head[y];
head[y]=cnt++;
}
int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
ll n,a[maxn],c[maxn],tr[maxn];
ll t,sum[maxn];
void insert(int x,int val){
while(x<=n+2){
tr[x]+=val;
x+=x&-x;
}
}
int getsum(int x){
int res=0;
while(x){
res+=tr[x];
x-=x&-x;
}
return res;
}
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++){
a[i]=read();
sum[i]=sum[i-1]+a[i];
c[i]=sum[i];
}
sort(c,c+1+n);
ll res=0;
int pos=lower_bound(c,c+1+n,0)-c+1; //首先把sum[0]即0插入树状数组
insert(pos,1); //树状数组是不能处理0的,所以需要加1
for(int i=1;i<=n;i++){
pos=upper_bound(c,c+1+n,sum[i]-t)-c;
//cout<<i<<" "<<getsum(pos)<<endl;
res+=(i-getsum(pos));
pos=lower_bound(c,c+1+n,sum[i])-c+1;//树状数组是不能处理0的,所以需要加1
insert(pos,1);
}
cout<<res<<endl;
}
我们坚持一件事情,并不是因为这样做了会有效果,而是坚信,这样做是对的。
——哈维尔
推荐阅读
-
Codeforces Round #220 (Div. 2) D 树状数组 && 二分_html/css_WEB-ITnose
-
Codeforces Round #510 (Div. 2) D. Petya and Array
-
Codeforces Round #510 (Div. 2) - D. Petya and Array (树状数组+离散化)
-
Codeforces Round #510 (Div. 2) D. Petya and Array(树状数组或线段树)
-
Codeforces Round #510 (Div. 2) D. Petya and Array
-
【Codeforces Round #510 (Div. 2) D.Petya and Array】 树状数组
-
Codeforces Round 510 D. Petya and Array (树状数组)
-
【权值线段树】Codeforces Round #510 (Div. 2) D. Petya and Array
-
Codeforces Round #510 (Div. 2) D. Petya and Array
-
CF Round #510 (Div. 2) D - Petya and Array (树状数组)