整体二分加深理解~

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;int n;struct trnode{ int l,r,lc,rc;LL c,lazy;}tr[110000];int trlen;void bt(int l,int r){ int now=++trlen; tr[now].l=l;tr[now].r=r; tr[now].lc=tr[now].rc=-1; tr[now].c=0;tr[now].lazy=0; if(l
           
            r)return 0; if(tr[now].l==l&&tr[now].r==r)return tr[now].c; int mid=(tr[now].l+tr[now].r)/2; int lc=tr[now].lc,rc=tr[now].rc; if(tr[now].lazy!=0) { tr[lc].c+=(tr[lc].r-tr[lc].l+1)*tr[now].lazy; tr[rc].c+=(tr[rc].r-tr[rc].l+1)*tr[now].lazy; tr[lc].lazy+=tr[now].lazy; tr[rc].lazy+=tr[now].lazy; tr[now].lazy=0; } if(r<=mid) return getsum(lc,l,r); else if(mid+1<=l)return getsum(rc,l,r); else return getsum(lc,l,mid)+getsum(rc,mid+1,r);}//------------seg_tree----------------------struct node{ int t,x,y,k;}q[51000],lq[51000],rq[51000];int as[51000];void solve(LL l,LL r,int st,int ed){ if(st>ed)return ; if(l==r) { for(int i=st;i<=ed;i++) if(q[i].t>0)as[q[i].t]=l; return ; } LL mid=(l+r)/2,lt=0,rt=0; for(int i=st;i<=ed;i++) { if(q[i].t==0) { if(q[i].k<=mid)lq[++lt]=q[i]; else { change(1,q[i].x,q[i].y,1); rq[++rt]=q[i]; } } else { LL d=getsum(1,q[i].x,n)-getsum(1,q[i].y+1,n); if(d
            
             =st;i--) if(q[i].t==0&&q[i].k>mid)change(1,q[i].x,q[i].y,-1); for(int i=1;i<=lt;i++)q[st+i-1]=lq[i]; for(int i=1;i<=rt;i++)q[st+lt+i-1]=rq[i]; solve(l,mid,st,st+lt-1); solve(mid+1,r,st+lt,ed);}char ss[10];int main(){ int Q,m=0,op; scanf("%d%d",&n,&Q); for(int i=1;i<=Q;i++) { scanf("%d%d%d%d",&op,&q[i].x,&q[i].y,&q[i].k); if(op==1)q[i].t=0; else q[i].t=++m; } trlen=0;bt(1,n); solve(0,(1LL<<33),1,Q); for(int i=1;i<=m;i++)printf("%d\n",as[i]); return 0;}