题目地址：洛谷：【P3332】[ZJOI2013]K大数查询 – 洛谷、BZOJ：Problem 3110. — [Zjoi2013]K大数查询

题目描述

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

输入输出格式

输入格式：
第一行N，M接下来M行，每行形如1 a b c或2 a b c

输出格式：
输出每个询问的结果

输入输出样例

输入样例#1：

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

输出样例#1：

1
2
1

说明

【样例说明】
第一个操作 后位置 1 的数只有 1 ， 位置 2 的数也只有 1 。 第二个操作 后位置 1的数有 1 、 2 ，位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3大的数是 1 。
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中c<=long long

题解

可以用线段树套线段树的写法。我们在外面维护一个权值线段树，每个节点挂一个普通的区间求和线段树，这样，我们就可以在利用权值线段树查询k大的时候，通过普通线段树查到询问区间内的数字个数。总复杂度O(n \log^2 n)可以接受，但是这种方法常数较大，洛谷不开O2无法通过，且需要动态开点，否则容易爆内存。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

struct SGTNode {
    int lch, rch;
    LL tag, val;
} sgt[MAXN * 200];
int stot;

inline void pushdown(int o, int l, int r) {
    int mid = (l + r) >> 1;
    if(sgt[o].tag) {
        if(!sgt[o].lch) sgt[o].lch = ++stot;
        sgt[sgt[o].lch].val += sgt[o].tag * (mid - l + 1);
        sgt[sgt[o].lch].tag += sgt[o].tag;
        if(!sgt[o].rch) sgt[o].rch = ++stot;
        sgt[sgt[o].rch].val += sgt[o].tag * (r - mid);
        sgt[sgt[o].rch].tag += sgt[o].tag;
        sgt[o].tag = 0;
    }
}

struct SegmentTree {
    int rt;

    inline void add(int &o, int l, int r, int ll, int rr, int v) {
        if(!o) o = ++stot;
        if(l >= ll && r <= rr) {
            sgt[o].tag += v;
            sgt[o].val += v * (r - l + 1);
            return;
        }
        pushdown(o, l, r);
        int mid = (l + r) >> 1;
        if(ll <= mid) add(sgt[o].lch, l, mid, ll, rr, v);
        if(rr > mid) add(sgt[o].rch, mid + 1, r, ll, rr, v);
        sgt[o].val = sgt[sgt[o].lch].val + sgt[sgt[o].rch].val;
    }

    inline LL query(int o, int l, int r, int ll, int rr) {
        if(l >= ll && r <= rr) {
            return sgt[o].val;
        }
        pushdown(o, l, r);
        int mid = (l + r) >> 1; LL res = 0;
        if(ll <= mid) res += query(sgt[o].lch, l, mid, ll, rr);
        if(rr > mid) res += query(sgt[o].rch, mid + 1, r, ll, rr);
        return res;
    }
} sts[MAXN << 2];

int n, m;

#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)

inline void insert(int o, int l, int r, int x, int il, int ir) {
    sts[o].add(sts[o].rt, 1, n, il, ir, 1);
    if(l == r) return;
    if(x <= mid) insert(lch, l, mid, x, il, ir);
    else insert(rch, mid + 1, r, x, il, ir);
}

inline int query(int o, int l, int r, LL k, int ql, int qr) {
    if(l == r) return l;
    LL rsiz = sts[rch].query(sts[rch].rt, 1, n, ql, qr);
    if(k <= rsiz) return query(rch, mid + 1, r, k, ql, qr);
    else return query(lch, l, mid, k - rsiz, ql, qr);
}

int op, a, b; LL c;

int main() {
    n = readint(); m = readint();
    while(m--) {
        op = readint(); a = readint(); b = readint(); c = readint();
        if(op == 1) insert(1, 0, n << 1, c + n, a, b);
        if(op == 2) printf("%d\n", query(1, 0, n << 1, c, a, b) - n);
    }
    return 0;
}