主席树——可持久化线段树，权值线段树
运用：
-
在某个历史版本上修改某一个位置上的值
-
访问某个历史版本上的某一位置的值
3.区间内k小数
开点——前缀和思想
一.P3567 [POI2014] KUR-Couriers
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5;
const int M = N * 21;
struct Presiedent_Tree {
int sum, L, R;
} T[M];
int n, m, root[N], T_cnt = 1;
int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while ('0' <= ch && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void insert(int &now, int x, int l = 1, int r = n) {
T[T_cnt++] = T[now];
now = T_cnt - 1;
T[now].sum++;
if (l == r)
return;
int mid = (l + r) >> 1;
if (x <= mid)
insert(T[now].L, x, l, mid);
else
insert(T[now].R, x, mid + 1, r);
}
int query(int i, int j, int x, int l = 1, int r = n) {
if (l == r)
return l;
int mid = (l + r) >> 1;
if (2 * (T[T[j].L].sum - T[T[i].L].sum) > x)
return query(T[i].L, T[j].L, x, l, mid);
if (2 * (T[T[j].R].sum - T[T[i].R].sum) > x)
return query(T[i].R, T[j].R, x, mid + 1, r);
return 0;
}
int main() {
n = read(), m = read();
root[0] = 0;
for (int i = 1; i <= n; i++) {
int x = read();
root[i] = root[i - 1];
insert(root[i], x);
}
for (int i = 1; i <= m; i++) {
int l = read(), r = read();
printf("%d\n", query(root[l - 1], root[r], r - l + 1));
}
return 0;
}
二.#include <cstdio>
#include <cstring>
#include <algorithm>
#define mid (l+r)/2
using namespace std;
const int N = 200010;
int n, q, m, cnt = 0;
int a[N], b[N], T[N];
int sum[N << 5], L[N << 5], R[N << 5];
inline int build(int l, int r) {
int rt = ++ cnt;
sum[rt] = 0;
if (l < r) {
L[rt] = build(l, mid);
R[rt] = build(mid + 1, r);
}
return rt;
}
inline int update(int pre, int l, int r, int x) {
int rt = ++ cnt;
L[rt] = L[pre];
R[rt] = R[pre];
sum[rt] = sum[pre] + 1;
if (l < r) {
if (x <= mid)
L[rt] = update(L[pre], l, mid, x);
else
R[rt] = update(R[pre], mid + 1, r, x);
}
return rt;
}
inline int query(int u, int v, int l, int r, int k) {
if (l >= r)
return l;
int x = sum[L[v]] - sum[L[u]];
if (x >= k)
return query(L[u], L[v], l, mid, k);
else
return query(R[u], R[v], mid + 1, r, k - x);
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + 1 + n);
m = unique(b + 1, b + 1 + n) - b - 1;
T[0] = build(1, m);
for (int i = 1; i <= n; i ++) {
int t = lower_bound(b + 1, b + 1 + m, a[i]) - b;
T[i] = update(T[i - 1], 1, m, t);
}
while (q --) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
int t = query(T[x - 1], T[y], 1, m, z);
printf("%d\n", b[t]);
}
return 0;
}
三.P3919 【模板】可持久化线段树 1（可持久化数组）
#include <iostream>
using namespace std;
#define N 1000005
#define lc(x) tr[x].l
#define rc(x) tr[x].r
int n, m, a[N];
struct node {
int l, r;
int v;
} tr[N * 25];
int root[N], idx;
void build(int &x, int l, int r) {
x = ++idx;
if (l == r) {
tr[x].v = a[l];
return;
}
int m = l + r >> 1;
build(lc(x), l, m);
build(rc(x), m + 1, r);
}
void modify(int &x, int y, int l, int r, int pos, int v) {
x = ++idx;
tr[x] = tr[y];
if (l == r) {
tr[x].v = v;
return;
}
int mid = l + r >> 1;
if (pos <= mid)
modify(lc(x), lc(y), l, mid, pos, v);
else
modify(rc(x), rc(y), mid + 1, r, pos, v);
}
int query(int x, int l, int r, int pos) {
if (l == r)
return tr[x].v;
int mid = l + r >> 1;
if (pos <= mid)
return query(lc(x), l, mid, pos);
else
return query(rc(x), mid + 1, r, pos);
}
int main() {
int ver, op, x, y;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
build(root[0], 1, n);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &ver, &op);
if (op == 1) {
scanf("%d%d", &x, &y);
modify(root[i], root[ver], 1, n, x, y);
} else {
scanf("%d", &x);
printf("%d\n", query(root[ver], 1, n, x));
root[i] = root[ver];
}
}
}