数据结构模板 - 洛谷保存站

### KMP算法生成next数组
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6;

int n1, n2;
char pa[N], str[N];
int _next[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

cin >> n1 >> pa + 1;
	cin >> n2 >> str + 1;

for (int i = 2, j = 0; i <= n1; ++i) {
		while (j && pa[j + 1] != pa[i]) j = _next[j];
		if (pa[j + 1] == pa[i]) j++;
		_next[i] = j;
	}

for (int i = 1, j = 0; i <= n2; ++i) {
		while (j && pa[j + 1] != str[i]) j = _next[j];
		if (pa[j + 1] == str[i]) j++;
		if (j == n1) {
			cout << i - j << " ";
			j = _next[j];
		}
	}

return 0;
}
```

### Trie树的插入和查询
```
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int tr[N][26], cnt[N], idx;
char str[N];

void insert() {
	int ptr = 0;
	for (int i = 0; str[i]; ++i) {
		int _index = str[i] - 'a';
		if (!tr[ptr][_index]) tr[ptr][_index] = ++idx;
		ptr = tr[ptr][_index];
	}
	cnt[ptr]++;
}

int query() {
	int ptr = 0;
	for (int i = 0; str[i]; ++i) {
		int _index = str[i] - 'a';
		if (!tr[ptr][_index]) return 0;
		ptr = tr[ptr][_index];
	}
	return cnt[ptr];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

cin >> n;
	while (n--) {
		char op[2];
		cin >> op >> str;

if (*op == 'I') insert();
		else cout << query() << endl;
	}

return 0;
}
```

### 堆排序
```
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, range;
int heap[N], sz;

void down(int u) {
	int t = u;
	if (u << 1 <= sz && heap[u << 1] <= heap[t]) t = u << 1;
	if ((u << 1 | 1) <= sz && heap[u << 1 | 1] <= heap[t]) t = u << 1 | 1;

if (t != u) {
		swap(heap[t], heap[u]);
		down(t);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

cin >> n >> range;
	for (int i = 1; i <= n; ++i) cin >> heap[i];

// 线性建堆的方式
	sz = n;
	for (int i = n >> 1; i >= 1; --i) down(i);

// 每次输出最小值后将堆尾元素赋值到堆顶然后down
	while (range--) {
		cout << heap[1] << " ";
		heap[1] = heap[sz--];
		down(1);
	}

return 0;
}
```

### 模拟堆
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

// idx[i]代表第i个插入点的下标, cnt[i]代表堆中下标i对应第几个插入的点
int n;
int heap[N], idx[N], cnt[N];
int sz;

bool cmp(char str1[], char str2[]) {
	return !strcmp(str1, str2);
}

void heap_swap(int u, int v) {
	swap(idx[cnt[u]], idx[cnt[v]]);
	swap(cnt[u], cnt[v]);
	swap(heap[u], heap[v]);
}

// 将一个数字变大, 向下交换
void down(int u) {
	int t = u;
	if (u << 1 <= sz && heap[u << 1] < heap[t]) t = u << 1;
	if ((u << 1 | 1) <= sz && heap[u << 1 | 1] < heap[t]) t = u << 1 | 1;
	if (t != u) {
		heap_swap(t, u);
		down(t);
	}
}

// 将一个数字变小向上交换
void up(int u) {
	while (u >> 1 && heap[u] < heap[u >> 1]) {
		heap_swap(u, u >> 1);
		u >>= 1;
	}
}

int main() {
	scanf("%d", &n);

// index是给堆分配的下标
	int index = 0;
	while (n--) {
		char op[5];
		int k, val;

scanf("%s", op);
		if (cmp(op, "I")) {
			scanf("%d", &val);
			sz++;
			index++;

idx[index] = sz, cnt[sz] = index;
			heap[sz] = val;
			up(sz);
		}
		// 输出堆的最小元素
		else if (cmp(op, "PM")) {
			printf("%d\n", heap[1]);
		}
		// 删除堆的最小元素, 将其与堆最后一个元素进行交换, 然后向下更新
		else if (cmp(op, "DM")) {
			heap_swap(1, sz);
			sz--;
			down(1);
		}
		// 删除第k个插入的数
		else if (cmp(op, "D")) {
			scanf("%d", &k);
			// 获取第k个插入数在堆中的下标
			k = idx[k];
			heap_swap(k, sz);
			sz--;
			up(k), down(k);
		}
		// 修改第k个插入的数
		else {
			scanf("%d%d", &k, &val);
			k = idx[k];
			heap[k] = val;
			up(k), down(k);
		}
	}

return 0;
}
```

### 单调栈
[Acwing830.单调栈](https://www.acwing.com/problem/content/832/)
![](https://cdn.luogu.com.cn/upload/image_hosting/h74r2d9v.png)

```cpp
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int stack[N], top;

int main() {
    cin >> n;

while (n--) {
        int val;
        cin >> val;
        while (top && stack[top] >= val) top--;
        if (!top) cout << -1 << " ";
        else cout << stack[top] << " ";
        stack[++top] = val;
    }

return 0;
}
```

### 树状数组求前缀和
```cpp
void lowbit(int val) {
	return val & -val;
}

void add(int u, int val) {
	for (int i = u; i <= n; i += lowbit(i)) tr[i] += val;  
}

int query(int u) {
	int res = 0;
	for (int i = u; i; i -= lowbit(i)) res += tr[i];
	return res;
}
```

### 树状数组求第K大数(二分)
[谜一样的牛](https://www.luogu.com.cn/article/vbvbbl6v)

[F-Insert](https://www.luogu.com.cn/article/okplw3x1)

### 基础线段树(单点修改, 区间查询)
[Acwing.245你能回答这些问题吗](https://www.acwing.com/problem/content/description/246/)
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 500010, INF = 0x3f3f3f3f;

int n, op_num;
int arr[N];
struct Node {
    int l, r;
    int res, lm, rm, sum;
} tr[N << 2];

void push_up(Node &u, Node &ls, Node &rs) {
    u.sum = ls.sum + rs.sum;
    u.lm = max(ls.lm, ls.sum + rs.lm);
    u.rm = max(rs.rm, rs.sum + ls.rm);
    u.res = max({ls.res, rs.res, ls.rm + rs.lm});
}

void push_up(int u) {
    push_up(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
    if (l == r) {
        int val = arr[l];
        tr[u] = {l, r, val, val, val, val};
        return;
    }

tr[u] = {l, r};
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);

push_up(u);
}

void modify(int u, int pos, int val) {
    if (tr[u].l == tr[u].r) {
        tr[u] = {pos, pos, val, val, val, val};
        return;
    }

int mid = tr[u].l + tr[u].r >> 1;
    if (pos <= mid) modify(u << 1, pos, val);
    else modify(u << 1 | 1, pos, val);

push_up(u);
}

Node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];

int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) return query(u << 1, l, r);
    if (l > mid) return query(u << 1 | 1, l, r);

// 子节点信息计算父节点信息, 因为最大子段和是连续的, 因此可能被两个子节点更新
    Node ls = query(u << 1, l, r);
    Node rs = query(u << 1 | 1, l, r);
    Node res;
    push_up(res, ls, rs);
    return res;
}

int main() {
    scanf("%d%d", &n, &op_num);

for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
    build(1, 1, n);

while (op_num--) {
        int op, val1, val2;
        scanf("%d%d%d", &op, &val1, &val2);

if (op == 1) {
            if (val1 > val2) swap(val1, val2);
            Node res = query(1, val1, val2);
            printf("%d\n", res.res);
        }
        else {
            modify(1, val1, val2);
            arr[val1] = val2;
        }
    }

return 0;
}
```

### 基础先线段树求连续字段和绝对值的最大值
[小红的数组](https://ac.nowcoder.com/acm/problem/275626)

```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long LL;
const int N = 5e5 + 10;

int n, op_num;
struct Node {
    int l, r;
    LL sum;
    LL lmin, rmin;
    LL lmax, rmax;
    LL res;
} tr[N << 2];
int arr[N];

void push_up(Node &u, Node &ls, Node &rs) {
    u.sum = ls.sum + rs.sum;

u.lmin = min(ls.lmin, ls.sum + rs.lmin);
    u.lmax = max(ls.lmax, ls.sum + rs.lmax);
    u.rmin = min(rs.rmin, rs.sum + ls.rmin);
    u.rmax = max(rs.rmax, rs.sum + ls.rmax);

u.res = max({ls.res, rs.res, ls.rmax + rs.lmax, -ls.rmin - rs.lmin});
}

void push_up(int u) {
    push_up(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
    if (l == r) {
        int val = arr[l];
        tr[u] = {l, r, val, val, val, val, val, abs(val)};
        return;
    }

tr[u] = {l, r};
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u);
}

Node query(int u, int ql, int qr) {
    if (tr[u].l >= ql && tr[u].r <= qr) return tr[u];

int mid = tr[u].l + tr[u].r >> 1;

if (ql > mid) return query(u << 1 | 1, ql, qr);
	else if (qr <= mid) return query(u << 1, ql, qr);
	else {
		Node node1 = query(u << 1, ql, qr);
		Node node2 = query(u << 1 | 1, ql, qr);
		Node res;
		push_up(res, node1, node2);
		return res;
	}
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

cin >> n;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    build(1, 1, n);
    cin >> op_num;

while(op_num--) {
        int l, r;
        cin >> l >> r;
        Node node = query(1, l, r);
        cout << node.res << "\n";
    }

return 0;
}
```

### 懒标记线段树(区间修改, 区间查询)
[Acwing243.一个简单的整数问题2](https://www.acwing.com/problem/content/244/)
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, op_num;
int arr[N];
struct Node {
	int l, r;
	LL add, sum;
} tr[N << 2];

void push_up(int u) {
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void push_down(int u) {
	Node &ls = tr[u << 1], &rs = tr[u << 1 | 1];
	if (tr[u].add) {
		ls.add += tr[u].add;
		ls.sum += (LL) tr[u].add * (ls.r - ls.l + 1);
		rs.add += tr[u].add;
		rs.sum += (LL) tr[u].add * (rs.r - rs.l + 1);
		tr[u].add = 0;
	}
}

void build(int u, int l, int r) {
	if (l == r) {
		tr[u] = {l, r, 0, arr[l]};
		return;
	}

tr[u] = {l, r, 0, 0};
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);

push_up(u);
}

void modify(int u, int l, int r, int val) {
	if (tr[u].l >= l && tr[u].r <= r) {
		tr[u].sum += (tr[u].r - tr[u].l + 1) * val;
		tr[u].add += val;
		return;
	}

push_down(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if (l <= mid) modify(u << 1, l, r, val);
	if (r > mid) modify(u << 1 | 1, l, r, val);
	push_up(u);
}

LL query(int u, int l, int r) {
	if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

push_down(u);
	
	LL res = 0;
	int mid = tr[u].l + tr[u].r >> 1;
	if (l <= mid) res += query(u << 1, l, r);
	if (r > mid) res += query(u << 1 | 1, l, r);

return res;
}

int main() {
	scanf("%d%d", &n, &op_num);

for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
	build(1, 1, n);

while (op_num--) {
		char op[2];
		int l, r, val;

scanf("%s", op);
		if (*op == 'C') {
			scanf("%d%d%d", &l, &r, &val);
			modify(1, l, r, val);
		}
		else {
			scanf("%d%d", &l, &r);
			printf("%lld\n", query(1, l, r));
		}
	}

return 0;
}
```

### 线段树扫描线
[Acwing247.亚特兰蒂斯](https://www.acwing.com/problem/content/249/)
![](https://oi-wiki.org/geometry/images/scanning.svg)

两个操作
- 在一段区间内**加上一个数**, 区间修改
- 求一段区间内的长度大于$0$的**区间总长度**是多少

线段树中的节点信息
- $cnt$当前区间**整个被覆盖的次数**
- $len$当前线段树节点区间长度大于$0$的区间长度(类似**懒标记**, 不考虑**祖先节点**)

> 因为查询的时候只会用到**根节点**, 因此不需要`push_down`操作
```cpp
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n;
struct Seg {
	double x, y1, y2;
	int val;

bool operator< (const Seg &t) const {
		return x < t.x;
	}
} segs[N << 1];
struct Node {
	int l, r;
	// cnt代表当前区间被覆盖的次数
	int cnt;
	// len代表当前区间的有效的长度
	double len;
} tr[N * 2 * 4];
vector<double> nums;

int get(double val) {
	return lower_bound(nums.begin(), nums.end(), val) - nums.begin();
}

void push_up(int u) {
	// 只要当前区间被覆盖, 有效
	if (tr[u].cnt) {
		 tr[u].len = nums[tr[u].r + 1] - nums[tr[u].l];
	}
	// 如果当前的cnt == 0, 当前长度就是两个儿子的长度之和
	else if (tr[u].l != tr[u].r) {
		tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
	}
	else {
		tr[u].len = 0;
	}
}

void build(int u, int l, int r) {
	tr[u] = {l, r};
	if (l == r) return;

int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int val) {
	if (tr[u].l >= l && tr[u].r <= r) {
		tr[u].cnt += val;
		push_up(u);
		return;
	}

int mid = tr[u].l + tr[u].r >> 1;
	if (l <= mid) modify(u << 1, l, r, val);
	if (r > mid) modify(u << 1 | 1, l, r, val);

push_up(u);
}

int main() {
    int cases = 1;
    while (scanf("%d", &n), n) {
        nums.clear();

for (int i = 0, j = 0; i < n; ++i) {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

segs[j++] = {x1, y1, y2, 1};
            segs[j++] = {x2, y1, y2, -1};
            nums.push_back(y1), nums.push_back(y2);
        }

sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());

build(1, 0, nums.size() - 1);

sort(segs, segs + (n << 1));

double res = 0;
        for (int i = 0; i < n << 1; ++i) {
            if (i > 0) {
                res += tr[1].len * (segs[i].x - segs[i - 1].x);
            }
            Seg seg = segs[i];
            modify(1, get(seg.y1), get(seg.y2) - 1, seg.val);
        }

printf("Test case #%d\n", cases++);
        printf("Total explored area: %.2lf\n\n", res);
    }

return 0;
}
```

### 持久化线段树(支持区间查询, 不支持修改)
> 持久化权值线段树 + 线段树二分查询

**权值线段树**中记录的是**左右儿子节点下标**, 而不是左右区间, 在查询或者修改的时候, 需要用$l$和$r$**维护区间**

```cpp
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int n, op_num, arr[N];
struct Node {
	int ls, rs;
	int cnt;
} tr[N * 4 + N * 17];
int root[N], idx;
vector<int> nums;

int get(int val) {
	return lower_bound(nums.begin(), nums.end(), val) - nums.begin();
}

void push_up(int u) {
	tr[u].cnt = tr[tr[u].ls].cnt + tr[tr[u].rs].cnt;
}

int build(int l, int r) {
	int u = ++idx;
	if (l == r) return u;

int mid = l + r >> 1;
	tr[u].ls = build(l, mid);
	tr[u].rs = build(mid + 1, r);

return u;
}

int insert(int pre, int l, int r, int val) {
	int u = ++idx;
	tr[u] = tr[pre];
	if (l == r) {
		tr[u].cnt++;
		return u;
	}

int mid = l + r >> 1;
	if (val <= mid) tr[u].ls = insert(tr[pre].ls, l, mid, val);
	if (val > mid) tr[u].rs = insert(tr[pre].rs, mid + 1, r, val);

push_up(u);
	return u;
}

// 查询第K小数
int query(int pre, int curr, int l, int r, int k) {
	if (l == r) return nums[l];

int mid = l + r >> 1;
	int cnt = tr[tr[curr].ls].cnt - tr[tr[pre].ls].cnt;
	if (k <= cnt) return query(tr[pre].ls, tr[curr].ls, l, mid, k);
	return query(tr[pre].rs, tr[curr].rs, mid + 1, r, k - cnt);
}

int main() {
	scanf("%d%d", &n, &op_num);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &arr[i]);
		nums.push_back(arr[i]);
	}

sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());

root[0] = build(0, n);
	for (int i = 1; i <= n; ++i) {
		int new_val = get(arr[i]);
		root[i] = insert(root[i - 1], 0, nums.size() - 1, new_val);
	}

while (op_num--) {
		int l, r, k;
		scanf("%d%d%d", &l, &r, &k);
		int res = query(root[l - 1], root[r], 0, nums.size() - 1, k);
		printf("%d\n", res);
	}

return 0;
}
```

### 持久化Trie
找到$S[p - 1]$`^`$S[n]$`^`$x$的最大值

也就是在找到$S[p - 1]$在区间$[l, r]$之间`^`一个定值$v$的最大值, 也就是在$[l, r]$之间寻找一个合法的$p$

如果只有右边的限制, $[1, r]$那么只需要查询对应版本的Trie即可, 但是因为有左边的限制, 因此还需要记录一个`max_id`, 在递归寻找数字的时候, 判断当前节点子树**是否至少存在**一个数的下标大于等于$l$, 说明当前子树节点的范围是合法的
```cpp
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 6e5 + 10;

int n, op_num;
int s[N];
int tr[N * 25][2], max_id[N * 25];
int root[N], idx;

void insert(int pre, int curr, int i, int k) {
    if (k < 0) {
        max_id[curr] = i;
        return;
    }

int v = s[i] >> k & 1;
    if (pre) tr[curr][v ^ 1] = tr[pre][v ^ 1];
    tr[curr][v] = ++idx;
    insert(tr[pre][v], tr[curr][v], i, k - 1);
    // 处理当前点的最大max_id
    max_id[curr] = max(max_id[tr[curr][0]], max_id[tr[curr][1]]);
}

int query(int l, int r, int val) {
    int u = root[r];

for (int i = 23; i >= 0; --i) {
        int v = val >> i & 1;
        if (max_id[tr[u][v ^ 1]] >= l) u = tr[u][v ^ 1];
        else u = tr[u][v];
    }

return val ^ s[max_id[u]];
}

int main() {
    scanf("%d%d", &n, &op_num);
    max_id[0] = -1;
    root[0] = ++idx;
    insert(0, root[0], 0, 23);

for (int i = 1; i <= n; ++i) {
        int val;
        scanf("%d", &val);
        s[i] = s[i - 1] ^ val;
        root[i] = ++idx;
        insert(root[i - 1], root[i], i, 23);
    }

char op[2];
    int l, r, val;
    while (op_num--) {
        scanf("%s", op);
        if (*op == 'A') {
            scanf("%d", &val);
            n++;
            root[n] = ++idx;
            s[n] = s[n - 1] ^ val;
            insert(root[n - 1], root[n], n, 23);
        }
        else {
            scanf("%d%d%d", &l, &r, &val);
            int res = query(l - 1, r - 1, s[n] ^ val);
            printf("%d\n", res);
        }
    }

return 0;
}
```

### Splay伸展树
```cpp
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, INF = 2147483647;

int n;
struct Node {
    int son[2], pre;
    int val, cnt, size;

void init(int _pre, int _val) {
        pre = _pre;
        val = _val;
        cnt = size = 1;
    }
} tr[N];
int root, idx;

void push_up(int u) {
    tr[u].size = tr[tr[u].son[0]].size + tr[tr[u].son[1]].size + tr[u].cnt;
}

void rotate(int u) {
    int pre = tr[u].pre;
    int grand = tr[pre].pre;
    int k = tr[pre].son[1] == u;

tr[grand].son[tr[grand].son[1] == pre] = u, tr[u].pre = grand;
    tr[pre].son[k] = tr[u].son[k ^ 1], tr[tr[u].son[k ^ 1]].pre = pre;
    tr[u].son[k ^ 1] = pre, tr[pre].pre = u;

push_up(pre), push_up(u);
}

void splay(int u, int k) {
    while (tr[u].pre != k) {
        int pre = tr[u].pre;
        int grand = tr[pre].pre;

if (grand != k) {
            (tr[pre].son[1] == u) ^ (tr[grand].son[1] == pre) ? rotate(u) : rotate(pre);
        }
        rotate(u);
    }

if (!k) root = u;
}

void insert(int val) {
    if (!root) {
        root = ++idx;
        tr[root].init(0, val);
        return;
    }

int u = root, pre = 0;
    while (u && tr[u].val != val) {
        pre = u;
        u = tr[u].son[val > tr[u].val];
    }

if (u) {
        tr[u].cnt++;
        splay(u, 0);
        return;
    }

u = ++idx;
    if (pre) tr[pre].son[val > tr[pre].val] = u;
    tr[u].init(pre, val);

push_up(u), push_up(pre);
    splay(u, 0);
}

// 将当前点转到根
void upper(int val) {
    int u = root;
    while (tr[u].val != val && tr[u].son[val > tr[u].val]) u = tr[u].son[val > tr[u].val];
    splay(u, 0);
}

int get_pre(int val) {
    upper(val);
    if (tr[root].val < val) return root;
    int u = tr[root].son[0];
    while (tr[u].son[1]) u = tr[u].son[1];
    splay(u, 0);
    return u;
}

int get_suff(int val) {
    upper(val);
    if (tr[root].val > val) return root;
    int u = tr[root].son[1];
    while (tr[u].son[0]) u = tr[u].son[0];
    splay(u, 0);
    return u;
}

// 统计有多少个数比当前数小
int get_rank(int val) {
    int res = 0, u = root;

while (u) {
        if (tr[u].val < val) {
            res += tr[tr[u].son[0]].size + tr[u].cnt;
            u = tr[u].son[1];
        }
        else u = tr[u].son[0];
    }

return res;
}

void remove(int val) {
    int pre = get_pre(val);
    int suff = get_suff(val);
    splay(pre, 0), splay(suff, pre);

int u = tr[suff].son[0];

if (tr[u].val != val) return;
    
    if (tr[u].cnt > 1) {
        tr[u].cnt--;
        splay(u, 0);
        return;
    }

tr[suff].son[0] = 0;
    push_up(suff), push_up(pre);
}

int get_val(int k) {
    int l = -1e7, r = 1e7;

while (l < r) {
        int mid = l + r + 1 >> 1;
        if (get_rank(mid) <= k) l = mid;
        else r = mid - 1;
    }

return l;
}

int main() {
    scanf("%d", &n);
    insert(-INF), insert(INF);

int op, val;
    while (n--) {
        scanf("%d%d", &op, &val);

if (op == 1) {
            insert(val);
        }
        else if (op == 2) {
            remove(val);
        }
        else if (op == 3) {
            int res = get_rank(val);
            printf("%d\n", res);
        }
        // 求排名第K大的数
        else if (op == 4) {
            int res = get_val(val);
            printf("%d\n", res);
        }
        else if (op == 5) {
            int pre = get_pre(val);
            printf("%d\n", tr[pre].val);
        }
        else {
            int suff = get_suff(val);
            printf("%d\n", tr[suff].val);
        }
    }

return 0;
}
```

### AC自动机

```cpp
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50 * (1e4 + 10), LEN = 1e6 + 10;

int n;
int tr[N][26], cnt[N], idx;
int queue[N], fail[N];

void insert() {
    int u = 0;
    for (int i = 0; str[i]; ++i) {
        int v = str[i] - 'a';
        if (!tr[u][v]) tr[u][v] = ++idx;
        u = tr[u][v];
    }
    cnt[u]++;
}

void build() {
    int head = 0, tail = -1;
    for (int i = 0; i < 26; ++i) if (tr[0][i]) queue[++tail] = tr[0][i];

while (head <= tail) {
        int u = queue[head++];

for (int i = 0; i < 26; ++i) {
            int ver = tr[u][i];
            if (!ver) tr[u][i] = tr[fail[u]][i];
            else {
                fail[ver] = tr[fail[u]][i];
                queue[++tail] = ver;
            }
        }
    }

}
```
[修复DNA](https://www.acwing.com/problem/content/1055/)
```
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;

int n;
char str[N];
int tr[N][4], cnt[N], idx;
int fail[N];
int dp[N][N];

int get(char c) {
    if (c == 'A') return 0;
    else if (c == 'G') return 1;
    else if (c == 'T') return 2;
    return 3; 
}

void insert() {
    int u = 0;

for (int i = 0; str[i]; ++i) {
        int v = get(str[i]);
        if (!tr[u][v]) tr[u][v] = ++idx;
        u = tr[u][v];
    }

cnt[u] = 1;
}

void build() {
    int queue[N] = {0}, head = 0, tail = -1;

for (int i = 0; i < 4; ++i) {
        if (tr[0][i]) queue[++tail] = tr[0][i];
    }

while (head <= tail) {
        int u = queue[head++];

for (int i = 0; i < 4; ++i) {
            int ver = tr[u][i];
            if (!ver) tr[u][i] = tr[fail[u]][i];
            else {
                fail[ver] = tr[fail[u]][i];
                queue[++tail] = ver;
                cnt[ver] |= cnt[fail[ver]];
            }
        }
    }

}

int main() {
    int cases = 1;

while (scanf("%d", &n), n) {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(fail, 0, sizeof fail);
        idx = 0;

for (int i = 0; i < n; ++i) {
            scanf("%s", str);
            insert();
        }

scanf("%s", str);
        int len = strlen(str);

build();

memset(dp, 0x3f, sizeof dp);
        dp[0][0] = 0;

for (int i = 0; i < len; ++i) {
            for (int j = 0; j <= idx; ++j) {
                for (int k = 0; k < 4; ++k) {
                    int val = get(str[i]) != k;
                    int u = tr[j][k];

if (!cnt[u]) {
                        dp[i + 1][u] = min(dp[i + 1][u], dp[i][j] + val);
                    }
                }
            }
        }

int res = INF;
        for (int i = 0; i <= idx; ++i) {
            res = min(res, dp[len][i]);
        }
        if (res == INF) res = -1;

printf("Case %d: %d\n", cases++, res);
    }
    return 0;
}
```

### 分块
```cpp
```

### 树链剖分
```cpp
```

### 动态树
```cpp
```

### 点分治

### 点分树

### CDQ分治
[陈丹琦分治](https://www.luogu.com.cn/article/b8pjv85r)

### 仙人掌
[求仙人掌直径](https://www.luogu.com.cn/article/muwr58x2)

正在渲染内容...