题意：给出一个长为n的数列，以及n个操作，操作涉及区间加法，询问区间内小于某个值x的元素个数。
注意细节！！ 对于最后一块非整块，要特殊处理！！！
/* loj6278 */ #include<bits/stdc++.h> using namespace std; #define N 50005 int pos[N],sta[505],end[505],a[N],fl[505],b[N],block,n;//a是原数组 b是每一个块内有序的数组 void modify(int l,int r,int del) { int p=pos[l],q=pos[r]; if(p==q){ for(int i=sta[p];i<=end[p];i++){ a[i]+=fl[p];//注意加上原来已经有的区间标记 if(i>=l&&i<=r) a[i]+=del; b[i]=a[i]; } fl[p]=0; sort(b+sta[p],b+end[p]+1); return ; } //先处理零散的部分 暴力加后对整个块排序 记得要+1 一定要记得将块的标记下传！！ for(int i=sta[p];i<=end[p];i++){ a[i]+=fl[p]; if(i>=l) a[i]+=del; b[i]=a[i]; } fl[p]=0;//记得将标记置0 sort(b+sta[p],b+end[p]+1); for(int i=sta[q];i<=end[q];i++){ a[i]+=fl[q]; if(i<=r) a[i]+=del; b[i]=a[i]; } fl[q]=0; sort(b+sta[q],b+end[q]+1); //对于整块 直接打标记 for(int i=p+1;i<=q-1;i++) fl[i]+=del; } int query(int l,int r,int x) { int p=pos[l],q=pos[r],ans=0; if(p==q){ for(int i=l;i<=r;i++) ans+=(a[i]+fl[p]<x); return ans; } for(int i=l;i<=end[p];i++) ans+=(a[i]+fl[p]<x);//要加上原有的区间标记 for(int i=sta[q];i<=r;i++) ans+=(a[i]+fl[q]<x); for(int i=p+1;i<=q-1;i++) ans+=lower_bound(b+sta[i],b+end[i]+1,x-fl[i])-b-sta[i];//二分和sort尾结点都要+1！！ return ans; } int main() { int op,aa,bb,c; scanf("%d",&n); block=(int) sqrt(n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[i]=a[i]; pos[i]=(i+block-1)/block; if(!sta[pos[i]]) sta[pos[i]]=i; end[pos[i]]=i; } for(int i=1;i<=pos[n];i++){ int x=block*(i-1)+1,y=min(block*i,n);//一定要注意边界！！！ sort(b+x,b+y+1); } int t=n; while(t--){ scanf("%d%d%d%d",&op,&aa,&bb,&c); if(op==0) modify(aa,bb,c); else printf("%d ",query(aa,bb,c*c)); } } /* 4 3 2 2 1 0 1 3 1 1 1 3 2 1 1 4 1 1 2 3 2 ans 2 0 2 9 6 4 7 5 3 1 9 5 5 1 2 7 2 */