题目大意：给定一个序列，提供两种操作：
1.区间加上一个数
2.询问区间中有多少大于等于C的数
n<=100W。树套树不用想了，Q<=3000，分块走起~
将原数组复制一份副本。副本中每一块排序
对于每次改动，中间块的部分打标记。两边改动后重建
对于每次查询。中间块的部分二分答案。两边暴力枚举
别忘考虑标记
#include#include #include #include #include #define M 1001001using namespace std;int n,m,ans,block,a[M],b[M],mark[1010];void Rebuild(int x){ memcpy(b+x*block+1,a+x*block+1,sizeof(a[0])*(x*block+block<=n?block:n-x*block) ); sort(b+x*block+1,b+min(x*block+block,n)+1);}int main(){ int i,j,x,y,z; char p[10]; cin>>n>>m; for(i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; block=static_cast (sqrt(n)+1e-7); for(i=0;i*block+1<=n;i++) sort(b+i*block+1,b+min(i*block+block,n)+1); for(i=1;i<=m;i++) { scanf("%s%d%d%d",p,&x,&y,&z); if(p[0]=='M') { if((x-1)/block==(y-1)/block) { for(j=x;j<=y;j++) a[j]+=z; Rebuild((x-1)/block); continue; } int b1=(x-2)/block+1; int b2=y/block-1; for(j=b1;j<=b2;j++) mark[j]+=z; for(j=x;j<=b1*block;j++) a[j]+=z; for(j=b2*block+block+1;j<=y;j++) a[j]+=z; Rebuild((x-1)/block); Rebuild((y-1)/block); } else { ans=0; if((x-1)/block==(y-1)/block) { for(j=x;j<=y;j++) if(a[j]+mark[(j-1)/block]>=z) ++ans; printf("%d\n",ans); continue; } int b1=(x-2)/block+1; int b2=y/block-1; for(j=b1;j<=b2;j++) ans+=(b+min(j*block+block,n)+1)-lower_bound(b+j*block+1,b+min(j*block+block,n)+1,z-mark[j]); for(j=x;j<=b1*block;j++) if(a[j]+mark[(j-1)/block]>=z) ++ans; for(j=b2*block+block+1;j<=y;j++) if(a[j]+mark[(j-1)/block]>=z) ++ans; printf("%d\n",ans); } } }