有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c 如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
MDZZ，这道题换了新数据后坑的一批，RE了我整整一版。这道题就是一道整体二分裸题，但有一个加数操作，那就只要算它的贡献就可以了，具体看代码。本题有两个大坑点，第一个要用unsigned int，第二个在二分答案时，取mid在/2时要用位运算，不要单纯的/2，大坑点啊。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<iostream> #define ui unsigned int using namespace std; struct node { int l,r,id,d,k; }q[51000],t1[51000],t2[51000]; int n,m; struct trnode { int l,r,lc,rc,he; ui c,lazy; }tr[410000];ui trlen; void bt(int l,int r) { trlen++;ui now=trlen; tr[now].l=l;tr[now].r=r; tr[now].lc=tr[now].rc=-1; if(l<r) { int mid=(l+r)/2; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid+1,r); } } inline void update(int now) { int lc=tr[now].lc,rc=tr[now].rc; if(lc==-1 && rc==-1)return ; if(tr[now].he!=0) { tr[lc].c=tr[lc].lazy=tr[rc].c=tr[rc].lazy=0; tr[lc].he=tr[rc].he=1; tr[now].he=0; } if(tr[now].lazy!=0) { tr[lc].c+=(tr[lc].r-tr[lc].l+1)*tr[now].lazy;tr[lc].lazy+=tr[now].lazy; tr[rc].c+=(tr[rc].r-tr[rc].l+1)*tr[now].lazy;tr[rc].lazy+=tr[now].lazy; tr[now].lazy=0; } } inline void change(int now,int l,int r) { if(tr[now].l==l && tr[now].r==r) { tr[now].c+=(ui)(tr[now].r-tr[now].l+1); tr[now].lazy++; return ; } if(tr[now].lazy!=0 || tr[now].he!=0)update(now); int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2; if(r<=mid)change(lc,l,r); else if(mid+1<=l)change(rc,l,r); else change(lc,l,mid),change(rc,mid+1,r); tr[now].c=tr[lc].c+tr[rc].c; } inline ui getsum(int now,int l,int r) { if(tr[now].l==l && tr[now].r==r)return tr[now].c; if(tr[now].lazy!=0 || tr[now].he!=0)update(now); int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2; if(r<=mid)return getsum(lc,l,r); else if(mid+1<=l)return getsum(rc,l,r); else return (ui)getsum(lc,l,mid)+getsum(rc,mid+1,r); } long long ans[51000]; void solve(int ll,int rr,int sl,int sr) { if(sl==sr) { for(int i=ll;i<=rr;i++) { if(q[i].id==2)ans[q[i].d]=sl; } return ; } int stl=0,str=0,mid=sl+sr>>1;//奇坑无比 tr[1].he=1;tr[1].c=tr[1].lazy=0; for(int i=ll;i<=rr;i++) { if(q[i].id==2) { ui wy=getsum(1,q[i].l,q[i].r); if(wy<(ui)q[i].k) { q[i].k-=wy; t1[++stl]=q[i]; } else t2[++str]=q[i]; } else { if(q[i].k<=mid)t1[++stl]=q[i]; else change(1,q[i].l,q[i].r),t2[++str]=q[i]; } } int now=ll; for(int i=1;i<=stl;i++)q[now++]=t1[i]; for(int i=1;i<=str;i++)q[now++]=t2[i]; if(stl!=0)solve(ll,ll+stl-1,sl,mid); if(str!=0)solve(ll+stl,rr,mid+1,sr); } int main() { int ss=0; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&q[i].id,&q[i].l,&q[i].r,&q[i].k); if(q[i].id==2)q[i].d=++ss; } bt(1,n);solve(1,m,-n,n); for(int i=1;i<=ss;i++)printf("%lld\n",ans[i]); return 0; }