題目
題解
區間修改，詢問區間小于c的個數。分塊排序，用vector。至于那個塊的大小，好像要用到均值不等式
我不太會。。。就開始一個個試，發現siz=sqrt(n)/4時最快！！！明天去學一下算分塊復雜度的方法。
代碼
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>using namespace std;
const int MAXN = 50005;
const int N = 1005;inline int rd(){int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}vector<int> b[N];int n,siz;
int a[MAXN],l[N],r[N];
int num,bl[MAXN],inc[MAXN];inline void reset(int id){b[id].clear();for(register int i=l[id];i<=r[id];i++) b[id].push_back(a[i]);sort(b[id].begin(),b[id].end());
}inline void build(){siz=sqrt(n);siz/log2(n);num=n/siz;if(n%siz) num++;for(register int i=1;i<=n;i++)bl[i]=(i-1)/siz+1; for(register int i=1;i<=num;i++){l[i]=(i-1)*siz+1;r[i]=i*siz;}r[num]=n;for(register int i=1;i<=num;i++) reset(i);
}inline void update(int ql,int qr,int w){if(bl[ql]==bl[qr]){for(register int i=ql;i<=qr;i++)a[i]+=w;reset(bl[ql]);return;}for(register int i=ql;i<=r[bl[ql]];i++)a[i]+=w;reset(bl[ql]);for(register int i=bl[ql]+1;i<bl[qr];i++) inc[i]+=w;for(register int i=l[bl[qr]];i<=qr;i++)a[i]+=w;reset(bl[qr]);
}inline int query(int ql,int qr,int c){int ret=0;if(bl[ql]==bl[qr]){for(register int i=ql;i<=qr;i++)ret+=(a[i]+inc[bl[i]]<c);return ret;}for(register int i=ql;i<=r[bl[ql]];i++)ret+=(a[i]+inc[bl[i]]<c);for(register int i=l[bl[qr]];i<=qr;i++)ret+=(a[i]+inc[bl[i]]<c);for(register int i=bl[ql]+1;i<bl[qr];i++){int tar=c-inc[i];ret+=lower_bound(b[i].begin(),b[i].end(),tar)-b[i].begin();}return ret;
}int main(){n=rd();for(register int i=1;i<=n;i++) a[i]=rd();build();for(register int i=1;i<=n;i++){int op,L,R,k;op=rd();L=rd();R=rd();k=rd();if(op==0)update(L,R,k);elseprintf("%d\n",query(L,R,k*k));}return 0;
}
