(模板)Luogu3380-2B平衡树

Posted on |

Problem

传送门

一个长度为n的序列，支持一堆操作，大致操作如下：

1.k在区间的排名(由小到大)2.区间第k小；3.单点修改；4&5：k的在区间上的前驱/后继。

Solution

右边大佬说树套树很简单，就是两个基本操作套起来即可。

然后我码了一个半小时才码完。

timg

虽然话没说错，树状数组套主席树……

但是这代码……

算了，还是太菜了……

2,3操作：

其实做法比较好理解，树状数组具有前缀性，主席树也是利用前缀

所以可以将树状数组的每一个节点上建一颗主席树

这样就可以完美的实现修改操作了

具体实现……就是把原本的树状数组一般操作改为主席树上的修改操作

询问的时候将树状数组上$lowbit$到的点全部带进去主席树里去询问就可以了。

以上是第2,3操作(搞了半天才完成2,3操作)

1操作：

考虑线段树的遍历过程

如果当前权值线段树的$mid$大于当前询问的权值k，那么我们会走向左儿子，否则往走向右儿子

而且，当我们走向右儿子时k一定大于左边的所有数

所以我们只要在此时加左子树的数的个数即可

4,5操作：

既然知道了任意数在区间里的$rank$前驱和后继就很好处理了

$k$前驱只需要查$k$在区间里的$rank$，区间排名为$rank - 1$的数即为所求

$k$的后继则需要知道$k$在区间中的$rank$与$k$在区间中出现的次数$num$，再求区间中排名为$rank+num$的数即可。

放一份奇丑的代码，以后再改。

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
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
	int res = 0, fl = 1;
	char r = getchar();
	for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
	for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
	return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 4e5 + 10;

struct CMtree{
	int ls, rs, sum;
}tre[Maxn << 7];
struct SGT{
	int ch[20],siz;
	SGT(){ siz = 0;}
	SGT Ls(){
		SGT B;
		for (int i = 1; i <= siz; ++i) B.ch[i] = tre[ch[i]].ls;
		B.siz = siz;
		return B;
	}
	SGT Rs(){
		SGT B;
		for (int i = 1; i <= siz; ++i) B.ch[i] = tre[ch[i]].rs;
		B.siz = siz;
		return B;
	}
	int sum(){
		int num = 0;
		for (int i = 1; i <= siz; ++i) num += tre[ch[i]].sum;
		return num;
	}
};
int A[Maxn], n, m, cnt, root[Maxn << 6];
int INF = 1e8 + 10;
pii operator + (const pii a, const pii b){
	return mp(a.fst + b.fst, a.snd + b.snd);
}
namespace CMT{
	inline void modify(int &rt,int l, int r, int pos, int v){
		if(!rt) rt = ++cnt;
		tre[rt].sum += v;
		if(l == r) return;
		int mid = l + r >> 1;
		if(mid >= pos) modify(tre[rt].ls, l, mid, pos, v);
		else modify(tre[rt].rs, mid + 1, r, pos, v);
	}
	inline void build(int &rt, int grt,int l, int r, int pos){
		tre[rt = ++cnt] = tre[grt];
		tre[rt].sum++;
		if(l == r) return;
		int mid = l + r >> 1;
		if(mid >= pos) build(tre[rt].ls, tre[grt].ls, l, mid, pos);
		else build(tre[rt].rs, tre[grt].rs, mid + 1, r, pos);
	}
	inline int Query(SGT a, SGT b, int l, int r, int k){
		if(l == r) return l;
		int mid = l + r >> 1, t = b.Ls().sum() - a.Ls().sum();
		//printf("%d %d %d %d\n", l, r, t, k);
		if(k <= t) return Query(a.Ls(), b.Ls(), l, mid, k);
		else return Query(a.Rs(), b.Rs(), mid + 1, r, k - t);
	}
	inline pii rank(SGT a, SGT b,int l,int r, int k){
		if(l == r) {
			return mp(1,b.sum() - a.sum());
		}
		int mid = l + r >> 1;
		if(k <= mid) return rank(a.Ls(), b.Ls(), l, mid, k);
		else return mp(b.Ls().sum() - a.Ls().sum(), 0) + rank(a.Rs(), b.Rs(), mid + 1, r, k);
	}
}
namespace BIT{
	int lst[Maxn];
	inline int lowbit(int x) {return x & -x;}
	inline void change(int pos,int a, int b){
		for (; pos <= n; pos += lowbit(pos))
			CMT :: modify(root[pos], 1,INF, a, -1), CMT :: modify(root[pos], 1,INF, b, 1);
	}
	inline void add(int pos,int a){
		for (; pos <= n; pos += lowbit(pos)){
			CMT :: build(root[pos], lst[pos], 1, INF, a), lst[pos] = root[pos];
		}
	}
	inline pii Query(int l, int r, int k, bool fl){
		SGT a, b;
		for (int i = l - 1; i > 0; i -= lowbit(i)) a.ch[++a.siz] = root[i];
		for (int i = r; i > 0; i -= lowbit(i)) b.ch[++b.siz] = root[i];
		if(fl) return mp(CMT :: Query(a, b, 1, INF, k), 0);
		else return CMT :: rank(a, b, 1, INF, k);
	}
}
void Front(int l, int r, int k) {
	pii Rank = BIT::Query(l, r, k, 0);
	if(Rank.fst == 1) printf("-2147483647\n");
	else printf("%d\n",BIT::Query(l, r, Rank.fst - 1, 1).fst);
}
void Next(int l, int r, int k){
	pii Rank = BIT::Query(l, r, k, 0);
	int all = r - l + 1;
	if(Rank.fst + Rank.snd > all) printf("2147483647\n");
	else printf("%d\n",BIT::Query(l, r, Rank.fst + Rank.snd, 1).fst);
}
int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) A[i] = read(), BIT::add(i, A[i]);
	while(m--){
		int opt = read();
		if(opt == 3) {int pos = read(), k = read(); BIT::change(pos,A[pos],k); A[pos] = k; continue;}
		int l = read(), r = read(), k = read();
		if(opt == 1) printf("%d\n",BIT::Query(l, r, k, 0).fst);
		if(opt == 2) printf("%d\n",BIT::Query(l, r, k, 1).fst);
		if(opt == 4) Front(l, r, k);
		if(opt == 5) Next(l, r, k);
	}
	return 0;
}