[ZJOI2013]K大数查询 (权值线段树套权值线段树+标记永久化）

#include 
using namespace std;
#define int long long
const int N = 5e4 + 10;
const int M = N * 300 + 10;


int n, m;
struct Node {
	int op, a, b, c;
} q[N];
vector<int>v;
int idx;
int  get(int x) {
	return  lower_bound(v.begin(), v.end(), x) - v.begin();
}
struct node {
	int l, r;
	int T;
#define ls i*2
#define rs i*2|1
} tr[N * 4];
int cnt;
struct NODE {
	int l, r;
	int sum, add;
} t[N*300];
int  acc(int a, int b, int c, int d) {
	return min(d, b) - max(a, c) + 1;
}

void update(int &i, int l, int r, int ql, int qr) {
	if(!i) i = ++idx;
	t[i].sum += acc(l, r, ql, qr);
	if(ql <= l && r <= qr) {
		t[i].add++;
		return ;
	}
	int mid = l + r >> 1;
	if(ql <= mid)update(t[i].l, l, mid, ql, qr);
	if(qr > mid) update(t[i].r, mid + 1, r, ql, qr);
}

int query1(int i, int l, int r, int ql, int qr, int add) {
	if(ql <= l && r <= qr) return t[i].sum + (r - l + 1) * add;
	int mid = l + r >> 1;
	int ans = 0;
	add += t[i].add;
	if(ql <= mid) {
		if(t[i].l) ans += query1(t[i].l, l, mid, ql, qr, add);
		else  ans += add * acc(l, mid, ql, qr);
	}
	if(qr > mid) {
		if(t[i].r) ans += query1(t[i].r, mid + 1, r, ql, qr, add);
		else  ans += add * acc(mid + 1, r, ql, qr);
	}
	return ans;
}
void build(int i, int l, int r) {
	tr[i] = {l, r, ++idx};
	int mid = l + r >> 1;
	if(l == r)return ;
	build(ls, l, mid);
	build(rs, mid + 1, r);
}
void change(int i, int a, int b, int c) {
	if(i ^ 1)update(tr[i].T, 1, n, a, b);
	if(tr[i].l == tr[i].r) return ;
	int mid = tr[i].l + tr[i].r >> 1;
	if(c <= mid)change(ls, a, b, c);
	else change(rs, a, b, c);
}
int query(int i, int a, int b, int c) {
	if(tr[i].l == tr[i].r)return tr[i].l;
	int mid = tr[i].l + tr[i].r >> 1;
	int tmp = query1(tr[rs].T, 1, n, a, b, 0);
	if(tmp >= c) return query(rs, a, b, c);
	else return query(ls, a, b, c - tmp);
}
signed main() {
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> q[i].op >> q[i].a >> q[i].b >> q[i].c;
		if(q[i].op == 1) v.push_back(q[i].c);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	build(1, 0, v.size() - 1);
	for(int i = 0; i < m; i++) {
		int op = q[i].op;
		int a = q[i].a;
		int b = q[i].b;
		int c = q[i].c;
	//	cin >> op >> a >> b >> c;
		if(op == 1) change(1, a, b, get(c));
		else cout << v[query(1, a, b, c)] << endl;
	}
}







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
101
102
103
104
105
106