题解 | #Petya and Array#

代码

转载自https://www.cnblogs.com/cj-xxz/p/9811806.html
写得太好了，可惜没有注释，所以这里解释一下CDQ分治的写法。
首先处理前缀和，要求的是sum[j]-sum[i]<t的区间数量。
离线操作，对前缀和排序，就变成了一个二维偏序问题，
对左区间任意i，右区间取j，答案加上满足偏序关系的对数，类似求逆序对。
处理后效性：将计算完的区间排序成一个非降序的区间，可以消除对后续操作的影响。

#include<bits/stdc++.h>
#define int long long
const int maxn=2e5+7;
inline void read(int &data){ //快读优化 
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    data=x*f;
}

int n,t,x,sum[maxn],ans;

void div(int *beg,int *end){
    if(end-beg<=1) return; //如果是单个点 
    int *mid=beg+(end-beg>>1); //区间中点 
    div(beg,mid); //分治 
    div(mid,end);
    for(int *i=beg,*j=mid;i!=mid;i++,ans+=j-mid){  //答案加上偏序对数
        while(j!=end&&(*j)<t+(*i)) ++j;//j往右移动
    }
    std::inplace_merge(beg,mid,end); //归并排序合并成一个非降序的区间 
}

signed main(){
    read(n);read(t);
    for(int i=1;i<=n;i++){
        read(x);
        sum[i]=sum[i-1]+x; //处理前缀和 
    }
    div(sum,sum+1+n); //cdq分治 
    printf("%lld\n",ans);
    return 0;
}