欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CF Round #510 (Div. 2) D - Petya and Array (树状数组)

程序员文章站 2022-05-09 15:07:14
...

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

 题意即让求区间和小于kk的区间的个数。即求sum[i]sum[j]&lt;=k(i&lt;j)sum[i]-sum[j]&lt;=k(i&lt;j),即我们需要求满足i&lt;ji&lt;j的,并且满足sum[i]k&lt;sum[j]sum[i]-k&lt;sum[j](i,j)(i,j),即对所有的ii,求出大于sum[i]ksum[i]-k的并且小于iijj的个数。

 这里即为求逆序对(i&lt;jxi&gt;xji&lt;j,x_i&gt;x_j),那么就使用树状数组,由于序列aaa[i]a[i]1e91e9,所以还需要离散化一下。具体参考逆序数求法。

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;
}

我们坚持一件事情,并不是因为这样做了会有效果,而是坚信,这样做是对的。
——哈维尔