题解 | #Petya and Array#
Petya and Array
https://ac.nowcoder.com/acm/problem/113097
代码
转载自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;
}
查看10道真题和解析
