记录编号	357278	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] K大数查询	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.430 s
提交时间	2016-12-10 10:13:09	内存使用	6.30 MiB

//%cstdio
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <cstdarg>
using namespace std;
namespace IO
{
char buf[1<<18], *fs, *ft;
inline char readc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++;
}
inline int fast_read()
{
    int r;
    char c;
    bool s = false;
    while(c = readc())
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')s = true;
    }
    while(isdigit(c = readc()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return s?-r:r;
}

}using IO::fast_read;

namespace segtree
{

struct node
{
    int l; int r;
    int ls, rs;
    int sum;
    int lazy;
    void addv(int v)
    {
        lazy += v;
        sum += (r-l+1)*v;
    }
}ns[110001];
int last = 1;
#define ld ns[d.ls]
#define rd ns[d.rs]
inline void pushup(node &d)
{
    d.sum = ld.sum + rd.sum;
}
int build(int l, int r)
{
    if(l > r)return 0;
    int c = last++;
    node &d = ns[c];
    d.l = l;
    d.r = r;
    if(l < r)
    {
        int m = (l+r)>>1;
        d.ls = build(l, m);
        d.rs = build(m+1, r);
    }
    return c;
}
inline void pushdown(node &d)
{
    if(d.lazy)
    {
        ld.addv(d.lazy);
        rd.addv(d.lazy);
        d.lazy = 0;
    }
}
int query(int c, int l, int r)
{
    if(!c)return 0;
    node &d = ns[c];
    if(d.l == l && r == d.r)return d.sum;
    else{
        pushdown(d);
        if(l >= rd.l)return query(d.rs, l, r);
        else if(r <= ld.r)return query(d.ls, l, r);
        else return query(d.ls, l, ld.r)+query(d.rs, rd.l, r);
    }
}
void addval(int c, int l, int r, int v)
{
    if(!c)return;
    node &d = ns[c];
    if(d.l == l && r == d.r)d.addv(v);
    else{
        pushdown(d);
        if(l >= rd.l)addval(d.rs, l, r, v);
        else if(r <= ld.r)addval(d.ls, l, r, v);
        else{
            addval(d.ls, l, ld.r, v);
            addval(d.rs, rd.l, r, v);
        }
        pushup(d);
    }
}

}using segtree::query; using segtree::addval;
int N, M;
int ques = 0;
int mn = 0x7fffffff, mx = 0;
struct que
{
    int id, cmd, a, b, c;
}qs[50050], s1[50050], s2[50050];
int ans[50050];
int cnt[50050];
void solve(int a, int b, int l, int r)  //操作qs[a, b] 的答案均在 [l, r]内
{
    if(l == r)
    {
        for(int i = a; i <= b; i++)if(qs[i].cmd == 2)ans[qs[i].id] = l;
        return;
    }
    int m = (long long)(l+r)>>1;
    for(int i = a; i <= b; i++)
    {
        if(qs[i].cmd == 1)
        {
            if(qs[i].c >= m+1)addval(1, qs[i].a, qs[i].b, 1);
        }else if(qs[i].cmd == 2)
            cnt[i] = query(1, qs[i].a, qs[i].b);
    }
    for(int i = a; i <= b; i++) //撤销
        if(qs[i].cmd == 1 && qs[i].c >= m+1)addval(1, qs[i].a, qs[i].b, -1);
    int p1 = 0, p2 = 0;
    for(int i = a; i <= b; i++)
    {
        if(qs[i].cmd == 1)
        {
            if(qs[i].c <= m)s1[p1++] = qs[i];else s2[p2++] = qs[i];
        }else if(qs[i].cmd == 2)
        {
            if(cnt[i] >= qs[i].c)s2[p2++] = qs[i];
            else qs[i].c -= cnt[i], s1[p1++] = qs[i];
        }
    }
    for(int i = 0; i < p1; i++)qs[a+i] = s1[i];
    for(int i = 0; i < p2; i++)qs[a+p1+i] = s2[i];
    solve(a, a+p1-1, l, m);
    solve(a+p1, b, m+1, r);
}
int main()
{
    //freopen("test_data.txt", "r", stdin);
    freopen("zjoi13_sequence.in", "r", stdin);
    freopen("zjoi13_sequence.out", "w", stdout);
    N = fast_read();
    M = fast_read();
    segtree::build(0, N);
    for(int i = 1; i <= M; i++)
    {
        qs[i].cmd = fast_read();
        qs[i].a = fast_read();
        qs[i].b = fast_read();
        qs[i].c = fast_read();
        if(qs[i].cmd == 2)qs[i].id = ++ques;
        else mn = min(mn, qs[i].c), mx = max(mx, qs[i].c);
    }
    solve(1, M, mn, mx);
    for(int i = 1; i <= ques; i++)
        printf("%d\n", ans[i]);
    return 0;
}