1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
| #include<bits/stdc++.h> #define RG register using namespace std;
inline int read() { int data=0, w=1; char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') w=-1, ch=getchar(); while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar(); return data*w; }
const int maxn(50010); struct node { bool clr; int lazy; long long sum; inline void clear() { clr=lazy=sum=0; } }tree[maxn << 2];
int n, m, ans[maxn]; #define son(i) ((root<<1)|i) inline void pushdown(int root, int l, int r) { if(tree[root].clr) { tree[son(0)].clear(); tree[son(1)].clear(); tree[son(0)].clr=tree[son(1)].clr=1; tree[root].clr=0; } int mid(l+r>>1); tree[son(0)].sum+=tree[root].lazy*(mid-l+1); tree[son(1)].sum+=tree[root].lazy*(r-mid); tree[son(0)].lazy+=tree[root].lazy; tree[son(1)].lazy+=tree[root].lazy; tree[root].lazy=0; }
void update(int ql, int qr, int root=1, int l=1, int r=n) { if(r<ql || qr<l) return; if(ql<=l && r<=qr) { tree[root].sum+=r-l+1; tree[root].lazy++; return; } pushdown(root, l, r); int mid(l+r>>1); update(ql, qr, son(0), l, mid); update(ql, qr, son(1), mid+1, r); tree[root].sum=tree[son(0)].sum+tree[son(1)].sum; }
long long query(int ql, int qr, int root=1, int l=1, int r=n) { if(r<ql || qr<l) return 0; if(ql<=l && r<=qr) return tree[root].sum; pushdown(root, l, r); int mid(l+r>>1); return query(ql, qr, son(0), l, mid)+query(ql, qr, son(1), mid+1, r); }
struct question { int opt, l, r, c, id; } p[maxn], p1[maxn], p2[maxn]; void divde(int ql, int qr, int l, int r) { if(ql>qr) return; if(l==r) { for(RG int i=ql;i<=qr;i++) ans[p[i].id]=l; return; } int mid=(l+r)>>1, t1=0, t2=0; for(RG int i=ql;i<=qr;i++) { if(p[i].opt^1) { long long q=query(p[i].l, p[i].r); if(q>=p[i].c) p2[++t2]=p[i]; else p[i].c-=q, p1[++t1]=p[i]; } else { if(p[i].c<=mid) p1[++t1]=p[i]; else { p2[++t2]=p[i]; update(p[i].l, p[i].r); } } } for(RG int i=1;i<=t1;i++) p[ql+i-1]=p1[i]; for(RG int i=1;i<=t2;i++) p[ql+t1+i-1]=p2[i]; tree[1].clear(); tree[1].clr=1; divde(ql, ql+t1-1, l, mid); divde(ql+t1, qr, mid+1, r); }
int main() { n=read(); m=read(); int tot=0; for(RG int i=1;i<=m;i++) { p[i]=(question){read(), read(), read(), read(), 0}; if(p[i].opt^1) p[i].id=++tot; } divde(1, m, -n, n); for(RG int i=1;i<=tot;i++) printf("%d\n", ans[i]); return 0; }
|