1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 #define N 50005 7 #define lc o*2 8 #define rc o*2+1 9 #define done seg.ql=q[i].l,seg.qr=q[i].r10 struct SegmentTree{11     int ql,qr;bool clr[N<<2];12     int add[N<<2],sum[N<<2];13 14     inline void init(){sum[1]=add[1]=0,clr[1]=1;}15     inline void updata(int o){sum[o]=sum[lc]+sum[rc];}16     inline void pushdown(int o,int L,int R){17         if(clr[o]){sum[lc]=sum[rc]=add[lc]=add[rc]=0,18             clr[lc]=clr[rc]=1,clr[o]=0;}19         int M=(L+R)>>1;20         if(add[o]){add[lc]+=add[o],add[rc]+=add[o];21             sum[lc]+=(M-L+1)*add[o],sum[rc]+=(R-M)*add[o];add[o]=0;}22     }23     void Add(int o,int L,int R){24         if(ql<=L&&R<=qr){add[o]++,sum[o]+=(R-L+1);return;}25         int M=(L+R)>>1;pushdown(o,L,R);26         if(ql<=M) Add(lc,L,M);if(qr>M) Add(rc,M+1,R);updata(o);27     }28     int Query(int o,int L,int R){29         if(ql<=L&&R<=qr){return sum[o];}30         pushdown(o,L,R);int res=0,M=(L+R)>>1;31         if(ql<=M) res+=Query(lc,L,M);if(qr>M) res+=Query(rc,M+1,R);32         return res;33     }34 }seg;35 struct qs{int opt,l,r,v,id,k;}q[N];36 int n,m;int ans[N];37 int cmp(qs a,qs b){return a.k==b.k?a.id<b.id:a.k<b.k;}38 void solve(int L,int R,int l,int r){39     if(l>r) return;40     if(L==R){41         for(int i=l;i<=r;i++)42             if(q[i].opt==2) ans[q[i].id]=L;43         return;44     }45     seg.init();46     int M=(L+R)>>1,t=l-1,s;47     for(int i=l;i<=r;i++){48         if(q[i].opt==1){49             if(q[i].v>M){done;seg.Add(1,1,n);q[i].k=1;}50             else{t++,q[i].k=0;}51         }52         else{53             done;s=seg.Query(1,1,n);54             if(q[i].v<=s) q[i].k=1;55             else t++,q[i].k=0,q[i].v-=s;56         }57     }58     sort(q+l,q+r+1,cmp);59     solve(L,M,l,t);solve(M+1,R,t+1,r);60 }61 inline int in(int x=0,char ch=getchar()){62     while(ch>‘9‘||ch<‘0‘) ch=getchar();63     while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x;64 }65 int main(){66     n=in(),m=in();67     for(int i=1;i<=m;i++){68         q[i].opt=in(),q[i].l=in(),q[i].r=in(),q[i].v=in(),q[i].id=i;69     }70     memset(ans,-1,sizeof(ans));71     solve(0,n,1,m);72     for(int i=1;i<=m;i++) if(ans[i]!=-1) printf("%d\n",ans[i]);73     return 0;74 } 

 1 #include <stdio.h> 2 #include <algorithm> 3 int w,C[2000010],ans[10010]; 4 struct Que{ 5     int x,y,v,tp,ID; 6 }q[200010]; 7 bool cmp(Que a,Que b){return a.x<b.x;} 8 inline void add(int i,int d){ 9     for(;i<=w;i+=i&(-i))C[i]+=d;10 }11 inline int sum(int i){12     int res=0;13     for(;i;i-=i&(-i))res+=C[i];14     return res;15 }16 void cdq(int l,int r){17     if(l==r) return;18     int mid=l+r>>1;19     cdq(l,mid),cdq(mid+1,r);20     std::sort(q+l,q+mid+1,cmp);21     std::sort(q+mid+1,q+r+1,cmp);22     int j=l;23     for(int i=mid+1;i<=r;i++){24         for(;j<=mid&&q[j].x<=q[i].x;j++)25             if(q[j].tp==1)add(q[j].y,q[j].v);26             if(q[i].tp==2)ans[q[i].ID]+=q[i].v*sum(q[i].y);27     }28     for(int i=l;i<j;i++)29         if(q[i].tp==1)add(q[i].y,-q[i].v);30 }31 int main(){32     int op,a,b,c,d,id=0,tot=0;33     freopen("mokia.in","r",stdin),freopen("mokia.out","w",stdout);34     while(scanf("%d",&op)&&op != 3){35         if(op==0)scanf("%d",&w);36         else if(op==1){scanf("%d%d%d",&a,&b,&c);q[++id]=(Que){a,b,c,1,0};}37         else{38             ++tot;scanf("%d%d%d%d",&a,&b,&c,&d);39             q[++id]=(Que){a-1,b-1,1,2,tot};40             q[++id]=(Que){c,d,1,2,tot};41             q[++id]=(Que){a-1,d,-1,2,tot};42             q[++id]=(Que){c,b-1,-1,2,tot};43         }44     }45     cdq(1,id);46     for(int i=1;i<=tot;i++)47         printf("%d\n",ans[i]);48     fclose(stdin),fclose(stdout);49     return 0;50 }