BZOJ3110 K大数查询 <树套树>

Problem

K大数查询

Description

NN个位置,MM个操作。操作有两种,每次操作如果是1 a b c1\ a\ b\ c的形式表示在第aa个位置到第bb个位置,每个位置加入一个数cc;如果是2 a b c2\ a\ b\ c形式,表示询问从第aa个位置到第bb个位置,第cc大的数是多少。

Input

第一行NNMM
接下来MM行,每行形如1 a b c1\ a\ b\ c2 a b c2\ a\ b\ c

Output

输出每个询问的结果

Sample Input

1
2
3
4
5
6
2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

Sample Output

1
2
3
1
2
1

Hint

样例说明
第一个操作后位置11的数只有11,位置22的数也只有11。第二个操作后位置11的数有1122,位置22的数也有1122。第三次询问位置11到位置1122大的数是11。第四次询问位置11到位置1111大的数是22。第五次询问位置11到位置2233大的数是11
数据规模
N,M5×104N,M\le 5\times 10^4
abNa\le b\le N
11操作中cN|c|\le N
22操作中cMaxLongintc\le MaxLongint

标签:值域线段树套区间线段树

Solution

这道题乍一看时主席树,但实际上是树套树。
外层值域线段树,内层区间线段树,外层只提供内层的根的位置,真正参与计算的是内层。

Code

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
#include <iostream>
#include <cstdio>
#define MAX_N 50000
using namespace std;
typedef long long ll;
int n, m, cnt;
int root[(MAX_N<<2)+500], ls[MAX_N*16*16+500], rs[MAX_N*16*16+500];
ll tr[MAX_N*16*16+500], tag[MAX_N*16*16+500];
inline void updata(int v, int s, int t) {tr[v] = tr[ls[v]]+tr[rs[v]]+tag[v]*(ll)(t-s+1);}
//内层修改
void modify(int &v, int s, int t, int l, int r) {
if (!v) v = ++cnt;
if (s >= l && t <= r) {tr[v] += (ll)(t-s+1), tag[v]++; return;}
int mid = s+t>>1;
if (l <= mid) modify(ls[v], s, mid, l, r);
if (r >= mid+1) modify(rs[v], mid+1, t, l, r);
updata(v, s, t);
}
//外层修改
void insert(int v, int s, int t, int l, int r, int x) {
modify(root[v], 1, n, l, r);
if (s == t) return;
int mid = s+t>>1;
if (x <= mid) insert(v<<1, s, mid, l, r, x);
if (x >= mid+1) insert(v<<1|1, mid+1, t, l, r, x);
}
//内层查询
ll calc(int v, int s, int t, int l, int r) {
if (!v) return 0;
if (s >= l && t <= r) return tr[v];
int mid = s+t>>1;
ll ret = tag[v]*(ll)(min(t, r)-max(s, l)+1);
if (l <= mid) ret += calc(ls[v], s, mid, l, r);
if (r >= mid+1) ret += calc(rs[v], mid+1, t, l, r);
return ret;
}
//外层查询
ll query(int v, int s, int t, int l, int r, int k) {
if (s == t) return s;
int mid = s+t>>1;
ll tmp = calc(root[v<<1|1], 1, n, l, r);
if (k >= tmp+1) return query(v<<1, s, mid, l, r, k-tmp);
if (k <= tmp) return query(v<<1|1, mid+1, t, l, r, k);
}
int main() {
scanf("%d%d", &n, &m);
while (m--) {
int opt, a, b, c;
scanf("%d%d%d%d", &opt, &a, &b, &c);
if (opt == 1) insert(1, 1, n, a, b, c);
if (opt == 2) printf("%lld\n", query(1, 1, n, a, b, c));
}
return 0;
}