记录编号	443917	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] K大数查询	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	10.296 s
提交时间	2017-09-01 19:44:51	内存使用	1.56 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc(), f = 1;
    while(!isgraph(tmp)) tmp = getc();
    if(tmp == '-') f = -1, tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res * f;
}

char ops[1 << 20], *opt = ops, *const opt_end = ops + (1 << 20);

inline void write_all(void) { 
    fwrite(ops, 1, opt - ops, stdout);
    opt = ops; return ;
}

inline void write(LL x) { 
    static char *p = new char[20]();
    if(x < 0) { 
        *(opt++) = '-'; 
        if(opt == opt_end) write_all();
        x = -x;
    }
    do{ 
        *(++p) = (x % 10) | 0x30;
        x /= 10;
    }while(x);
    while(*p) { 
        *(opt++) = *(p--);
        if(opt == opt_end) write_all();
    }
    *(opt++) = '\n';
    if(opt == opt_end) write_all();
    return ;
}

struct NODE2{ //区间线段树节点
    unsigned cnt, tag;
    NODE2 *ls, *rs;
    NODE2() { ls = rs = NULL; cnt = 0;}
};

struct NODE1{ //权值线段树节点
    NODE2 *root;
    NODE1 *ls, *rs;
    NODE1() { root = NULL; ls = rs = NULL;}
};

void Build(NODE1 *&node, int L, int R);
inline void Pushdown(NODE2 *node, int L, int R);
void Insert(NODE1 *&node, int l, int r, int k, int L, int R);
int Query(NODE1 *node, int l, int r, unsigned k, int L, int R);

int N, M, a, b, c;
unsigned d;
NODE1 *root;

int main() { 
#ifndef LOCAL
    freopen("zjoi13_sequence.in", "r", stdin);
    freopen("zjoi13_sequence.out", "w", stdout);
#endif
    N = read(), M = read();
    Build(root, -N, N);
    while(M--) 
        if(read() == 1) 
            a = read(), b = read(), c = read(),
            Insert(root, a, b, c, -N, N);
        else a = read(), b = read(), c = read(),
            write(Query(root, a, b, c, -N, N));
    write_all();
    return 0;
}
//建立权值线段树
void Build(NODE1 *&node, int L, int R) { 
    node = new NODE1();
    if(L ^ R) { 
        int M = (L + R) >> 1;
        Build(node->ls, L, M);
        Build(node->rs, M + 1, R);
    }
    return ;
}
//下方lazy tag并动态开点
inline void Pushdown(NODE2 *node, int L, int R) { 
    if(L == R || !node->tag) return ;
    int M = (L + R) >> 1, Len;
    if(!node->ls) node->ls = new NODE2();Len = M - L + 1;
    node->ls->tag += node->tag; node->ls->cnt += node->tag * Len;
    if(!node->rs) node->rs = new NODE2();Len = R - M;
    node->rs->tag += node->tag; node->rs->cnt += node->tag * Len;
    node->tag = 0; return ;
}
//插入区间线段树
void Insert(NODE2 *&node, int l, int r, int L, int R) { 
    if(!node) node = new NODE2();
    Pushdown(node, L, R);
    if(l <= L && R <= r) ++node->tag, node->cnt += (R - L + 1);
    else { 
        int M = (L + R) >> 1;
        if(l <= M) Insert(node->ls, l, r, L, M);
        if(M < r) Insert(node->rs, l, r, M + 1, R);
        node->cnt = 0;
        if(node->ls) node->cnt += node->ls->cnt;
        if(node->rs) node->cnt += node->rs->cnt;
    }
    return ;
}
//插入权值线段树
void Insert(NODE1 *&node, int l, int r, int k, int L, int R) { 
    Insert(node->root, l, r, 1, N); 
    if(L == R) return ;
    int M = (L + R) >> 1;
    if(k <= M) Insert(node->ls, l, r, k, L, M);
    else Insert(node->rs, l, r, k, M + 1, R);
    return ;
}
//查询数字个数
unsigned Query(NODE2 *node, int l, int r, int L, int R) { 
    if(!node) return 0;
    Pushdown(node, L, R);
    if(l <= L && R <= r) return node->cnt;
    int M = (L + R) >> 1; unsigned ret = 0;
    if(l <= M) ret += Query(node->ls, l, r, L, M);
    if(M < r) ret += Query(node->rs, l, r, M + 1, R);
    return ret;
}
//查询从l到r之间第k大
int Query(NODE1 *node, int l, int r, unsigned k, int L, int R) { 
    if(L == R) return L;
    unsigned tmp = Query(node->rs->root, l, r, 1, N);
    int M = (L + R) >> 1;
    if(k <= tmp) return Query(node->rs, l, r, k, M + 1, R);
    else return Query(node->ls, l, r, k - tmp, L, M);
}