学了一下整体二分,就拿这题练练手- -
线段树标记下传的时候把+=写成了=调了N久也是醉
#include <cstdio> #include <algorithm> using namespace std; const int N=50010,INF=~0u>>1; struct ask{int op,cur,ans,tmp,l,r,c,id;}qs[N],q[N*4],q1[N*4],q2[N*4]; int T[N*4],tag[N*4],L[N*4],R[N*4],ans[N*4],n,m; typedef long long LL; void up(int x){T[x]=T[x<<1]+T[x<<1|1];} void down(int x){ if(tag[x]){ T[x<<1]+=(R[x<<1]-L[x<<1]+1)*tag[x];tag[x<<1]+=tag[x]; T[x<<1|1]+=(R[x<<1|1]-L[x<<1|1]+1)*tag[x];tag[x<<1|1]+=tag[x]; tag[x]=0; } } void build(int x,int l,int r){ L[x]=l;R[x]=r; if(l==r){T[x]=0;return;} int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); up(x); } void change(int x,int l,int r,int d){ if(l<=L[x] && R[x]<=r) {tag[x]+=d;T[x]+=d*(R[x]-L[x]+1);return;} int mid=(L[x]+R[x])>>1; down(x); if(mid>=l) change(x<<1,l,r,d); if(mid<r) change(x<<1|1,l,r,d); up(x); } int query(int x,int l,int r){ if(l<=L[x] && R[x]<=r) {return T[x];} int mid=(L[x]+R[x])>>1,ret=0; down(x); if(mid>=l) ret+=query(x<<1,l,r); if(mid<r) ret+=query(x<<1|1,l,r); return ret; } void solve(int s,int t,LL l,LL r){ if(s>t) return ; if(l==r) {for(int i=s;i<=t;i++) if(q[i].op==2) ans[q[i].id]=l;return;} int mid=(l+r)>>1,t1=0,t2=0; for(int i=s;i<=t;i++){ if(q[i].op==1 && q[i].c>mid) change(1,q[i].l,q[i].r,1); if(q[i].op==2)q[i].tmp=query(1,q[i].l,q[i].r); } for(int i=s;i<=t;i++) if(q[i].op==1 && q[i].c>mid) change(1,q[i].l,q[i].r,-1); for(int i=s;i<=t;i++) if(q[i].op==2){ if(q[i].cur+q[i].tmp>=q[i].c) q1[++t1]=q[i]; else q[i].cur+=q[i].tmp,q2[++t2]=q[i]; }else{ if(q[i].c>mid) q1[++t1]=q[i];else q2[++t2]=q[i]; } for(int i=1;i<=t1;i++) q[s+i-1]=q1[i]; for(int i=1;i<=t2;i++) q[s+t1+i-1]=q2[i]; solve(s,s+t1-1,mid+1,r); solve(s+t1,t,l,mid); } int main(){ //freopen("3110.in","r",stdin);freopen("3110.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d%d",&qs[i].op,&qs[i].l,&qs[i].r,&qs[i].c),qs[i].id=i,q[i]=qs[i]; build(1,1,n); solve(1,m,-INF,INF); for(int i=1;i<=m;i++) if(qs[i].op==2)printf("%d\n",ans[i]==INF?0:ans[i]); return 0; }