题目链接 题目可转化为值域线段树的写法，题目上说让求所有区间和的值在L到R之间的有多少个，每一个区间值可以由数组的前缀和快速求出来，设sum[i]为i之前的和，i小于j即求sum[j]-sum[i]在L到R之间的有多少个，可以转化为 sum[j]-R<=sum[i]<=sum[j]-L,用sum[i]建一颗值域线段树每次询问在sum[j]-R到sum[j]-L之间的值有多少个累加起来就是结果。
/* 值域线段树区间里面存的是在这个区间内的数的个数有多少个 */ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; const int maxn=7e6+10; const LL inf=10000000000; LL x[maxn]; struct AC { struct zp { LL lson,rson,sum; } tree[maxn]; int cnt; int newnode()//动态开辟节点 { tree[cnt].lson=tree[cnt].rson=-1; tree[cnt].sum=0; cnt++; return cnt-1; } void init() { cnt=0; } void update(LL &k,LL l,LL r,LL num)//更新/插入值 { if(k==-1) k=newnode();//没有这个值新开节点 tree[k].sum++;//这个值所处的路线上的值都加一 if(l==r) return ; LL mid=(l+r)>>1; if(num<=mid) update(tree[k].lson,l,mid,num); else update(tree[k].rson,mid+1,r,num); } LL query(LL k,LL l,LL r,LL ql,LL qr)//查询区间内有多少个值 { if(k==-1) return 0; if(l==ql&&r==qr) return tree[k].sum; LL mid=(l+r)>>1; if(qr<=mid) return query(tree[k].lson,l,mid,ql,qr); else if(ql>mid) return query(tree[k].rson,mid+1,r,ql,qr); else return query(tree[k].lson,l,mid,ql,mid)+query(tree[k].rson,mid+1,r,mid+1,qr); } } ac; int main() { LL n,L,R; while(~scanf("%lld%lld%lld",&n,&L,&R)) { ac.init();//注意初始化 scanf("%lld",&x[0]); for(int i=1; i<n; i++) scanf("%lld",&x[i]),x[i]+=x[i-1]; LL root=-1; ac.update(root,-inf,inf,0);//先插入0,因为x[0]也要算一次 LL ans=0; for(int i=0; i<n; i++) { ans+=ac.query(root,-inf,inf,x[i]-R,x[i]-L);//统计答案 ac.update(root,-inf,inf,x[i]);//将这个值插入后面要用到 } printf("%lld\n",ans); } }题目链接
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; const int maxn=7e6+10; const LL inf=10000000000; struct AC { struct zp { int lson,rson; LL sum; bool lazy; } tree[maxn]; int cont; void init() { cont=0; } int newnode() { tree[cont].lson=tree[cont].rson=-1; tree[cont].sum=0; tree[cont].lazy=0; cont++; return cont-1; } void pushdown(int k) { if(tree[k].lazy==1) { if(tree[k].lson!=-1) { tree[tree[k].lson].lazy=1; tree[tree[k].lson].sum=0; } if(tree[k].rson!=-1) { tree[tree[k].rson].lazy=1; tree[tree[k].rson].sum=0; } tree[k].lazy=0; } } void pushup(int k) { LL ans=0; if(tree[k].lson!=-1) ans+=tree[tree[k].lson].sum; if(tree[k].rson!=-1) ans+=tree[tree[k].rson].sum; tree[k].sum=ans; } void update1(int &k,LL l,LL r,LL num,LL cnt)//opt 1 { if(k==-1) k=newnode(); pushdown(k); tree[k].sum+=cnt; if(l==r) return ; LL mid=(l+r)>>1; if(num<=mid) update1(tree[k].lson,l,mid,num,cnt); else update1(tree[k].rson,mid+1,r,num,cnt); } void update2(int k,LL l,LL r,LL ql,LL qr)//设置清空标记 { if(k==-1) return ; pushdown(k); if(ql==l&&qr==r) { tree[k].lazy=1,tree[k].sum=0; return ; } LL mid=(l+r)>>1; if(qr<=mid) update2(tree[k].lson,l,mid,ql,qr); else if(ql>mid) update2(tree[k].rson,mid+1,r,ql,qr); else { update2(tree[k].lson,l,mid,ql,mid); update2(tree[k].rson,mid+1,r,mid+1,qr); } pushup(k); } LL query(int k,LL l,LL r,LL ql,LL qr)//查询区间值 { if(k==-1) return 0; pushdown(k); if(l==ql&&r==qr) return tree[k].sum; LL mid=(l+r)>>1; if(qr<=mid) return query(tree[k].lson,l,mid,ql,qr); else if(ql>mid) return query(tree[k].rson,mid+1,r,ql,qr); else return query(tree[k].lson,l,mid,ql,mid)+query(tree[k].rson,mid+1,r,mid+1,qr); } LL query1(int k,LL l,LL r,LL num)//查询第num小的数 { pushdown(k); if(l==r) return l; LL mid=(l+r)>>1; if(tree[k].lson!=-1) { if(tree[tree[k].lson].sum>=num) return query1(tree[k].lson,l,mid,num); else return query1(tree[k].rson,mid+1,r,num-tree[tree[k].lson].sum); } else return query1(tree[k].rson,mid+1,r,num); } } ac; int main() { int n; while(~scanf("%d",&n)) { ac.init(); int root=-1; for(int i=0; i<n; i++) { int opt; LL num,sum; scanf("%d%lld",&opt,&num); switch(opt) { case 1: ac.update1(root,-inf,inf,num,1); break; case 2: sum=ac.query(root,-inf,inf,-inf,num-1); ac.update2(root,-inf,inf,-inf,num-1); ac.update1(root,-inf,inf,num,sum); break; case 3: sum=ac.query(root,-inf,inf,num+1,inf); ac.update2(root,-inf,inf,num+1,inf); ac.update1(root,-inf,inf,num,sum); break; case 4: printf("%lld\n",ac.query1(root,-inf,inf,num)); break; case 5: printf("%lld\n",ac.query(root,-inf,inf,-inf,num-1)); break; } } } }