【CF1042D】Petya and Array

题目大意：给定一个 N 个数组成的序列，给定一个 T，求有多少个区间满足\(\sum_{i=l}^ra[i]<T\)。

题解：区间和问题可以用前缀和优化，即：求有多少个区间满足\(sum[r]-sum[l-1]<T\) 成立。移项得：\(sum[l-1]>sum[r]-T\)，即：维护 sum 数组中的每个数，前面有多少数满足以上关系式。直接用平衡树维护即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;

struct node{
    #define ls(x) t[x].lc
    #define rs(x) t[x].rc
    int lc,rc,rd,size,cnt;
    long long val;
}t[maxn];
int tot,root;
inline void pushup(int p){
    t[p].size=t[ls(p)].size+t[rs(p)].size+t[p].cnt;
}
inline int newnode(long long val){
    ++tot,t[tot].val=val,t[tot].rd=rand(),t[tot].cnt=t[tot].size=1;
    return tot;
}
inline void zig(int &p){
    int lson=ls(p);
    ls(p)=rs(lson),rs(lson)=p,p=lson;
    pushup(rs(p)),pushup(p);
}
inline void zag(int &p){
    int rson=rs(p);
    rs(p)=ls(rson),ls(rson)=p,p=rson;
    pushup(ls(p)),pushup(p);
}
void insert(int &p,long long val){
    if(!p)p=newnode(val);
    else if(t[p].val==val)++t[p].size,++t[p].cnt;
    else if(val<t[p].val){
        ++t[p].size,insert(ls(p),val);
        if(t[ls(p)].rd>t[p].rd)zig(p);
    }else{
        ++t[p].size,insert(rs(p),val);
        if(t[rs(p)].rd>t[p].rd)zag(p);
    }
}
int query(int p,long long val){
    if(!p)return 0;
    else if(t[p].val>val)return t[p].cnt+t[rs(p)].size+query(ls(p),val);
    else return query(rs(p),val);
}

int n;
long long m,ans,sum[maxn];

void read_and_parse(){
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&sum[i]),sum[i]+=sum[i-1];
}

void solve(){
    insert(root,0);
    for(int i=1;i<=n;i++){
        ans+=query(root,sum[i]-m);
        insert(root,sum[i]);
    }
    printf("%lld\n",ans);
}

int main(){
    read_and_parse();
    solve();
    return 0;
}

【CF1042D】Petya and Array

原文：https://www.cnblogs.com/wzj-xhjbk/p/10459232.html