区间加法,区间查询
显然就是分块辣
维护一个按块排好序的数组。
每次修改依然是整块打标记,零散块暴力。蓝后对零散块重新排序。
询问时整块二分,零散块暴力就好辣
注意细节挺多和边界问题TAT
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; inline int Min(int a,int b){return a<b?a:b;} void read(int &x){ static char c=getchar();x=0; while(c<'0'||c>'9') c=getchar(); while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar(); } #define N 1000005 int n,Len,m,a[N],b[N],add[1005]; inline int Bel(int x){return (x-1)/Len+1;} void Add(int l,int r,int v){ register int i,p; if(Bel(l)==Bel(r)){//注意l,r在同一块内,下同 p=Bel(l)*Len; for(i=l;i<=r;++i) a[i]+=v; for(i=p-Len+1;i<=p;++i) b[i]=a[i]; sort(b+p-Len+1,b+p); return ; } p=Bel(l)*Len; for(i=l;i<=p;++i) a[i]+=v; for(i=p-Len+1;i<=p;++i) b[i]=a[i]; sort(b+p-Len+1,b+p); for(i=Bel(l)+1;i<Bel(r);++i) add[i]+=v; p=(Bel(r)-1)*Len+1; for(i=p;i<=r;++i) a[i]+=v; for(i=Min(n,p+Len);i>=p;--i) b[i]=a[i]; sort(b+p,b+Min(n,p+Len));//注意最后一块右端不超过n } int Ask(int l,int r,int v){ register int i,p,re=0; if(Bel(l)==Bel(r)){ for(i=l;i<=r;++i) re+=(a[i]>=v-add[Bel(l)]); return re; } p=Bel(l)*Len; for(i=l;i<=p;++i) re+=(a[i]>=v-add[Bel(l)]); for(i=Bel(l)+1;i<Bel(r);++i){ int tmp=lower_bound(b+(i-1)*Len+1,b+i*Len,v-add[i])-b; re+=i*Len-tmp+(b[tmp]>=v-add[i]);//如果整块都>v-add[i],注意lower_bound找到的tmp仍指向块的开头 } p=(Bel(r)-1)*Len+1; for(i=p;i<=r;++i) re+=(a[i]>=v-add[Bel(r)]); return re; } int main(){ register int i; char opt[3]; int q1,q2,q3; read(n);read(m); Len=sqrt(n); for(i=1;i<=n;++i) read(a[i]),b[i]=a[i]; for(i=1;i+Len<=n;i+=Len) sort(b+i,b+i+Len); sort(b+i,b+n+1); while(m--){ scanf("%s%d%d%d",opt,&q1,&q2,&q3); if(opt[0]=='M') Add(q1,q2,q3); else if(opt[0]=='A') printf("%d\n",Ask(q1,q2,q3)); }return 0; }