首页

嗯。。传说中的主席树，迈出了可持久化的第一步 |･ω･｀)

万恶之源： P3919 【模板】可持久化线段树 1（可持久化数组）

​ 显然，每次修改都开一颗线段树，空间 n2n^2 爆炸。。

​ 但因为是单点修改，所以对于每次修改操作，直接开一条链就好了， nlog⁡nn \log n 大小。

​ 用 root [i] 记录每次操作的树根即可，，

具体长这样：

<img src = "https://s1.ax1x.com/2020/08/16/dExadS.jpg" width = "400px" >

然后跟线段树一样，，就直接写，别怕写不出来，，记得复制操作什么的不要写错（嘤～

指针写的丑逼代码才不要放在博客里 ε٩(๑> ₃ <)۶ з

这就完事了？不行啊得把篇幅水够才行 qwq

经典题目唔..P3834 【模板】可持久化线段树 2（主席树）

（以下为便于区分，对于原序列的位置用大写 L, R 表示； 对于线段树的点用小写 l, r 表示）

# 整个区间的 kth

​ 直接一颗线段树，，以数值 （记得离散化）建立线段树。把序列中的数字一个一个地插入到线段树完成初始化。对于 kth 查询这样整：

fake code:

int query()
{
    if (l == r) return l;
	if (k <= sum_l) // 记左儿子的值为 sum_l，即左儿子所记录的数字个数。
        return query(左儿子, kth);
    else return query(右儿子, (kth - sum_l));
}
print a[query(1,n)];
# 区间 [L, R] 的 kth

​ 看上段加黑字体 emmm，用可持久化线段树就好啦。插入第 i 个数的时候对应区间就是 [1,i][1,\ i] 。查询 [L,R][L,\ R] 就是查询 [1,R]−[1,L−1][1,\ R]\ -\ [1,\ L - 1] ，用第 R 次的版本减去第 L-1 次的版本即可。详见代码 (´▽｀) ノ♪

code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define mid (l+r)>>1
using namespace std;
const int MAXN = 2e5 + 233;
int n0, n, M, a0[MAXN], a[MAXN], root[MAXN], tmp;
struct tree
{
	int lson, rson;
	int sum;
} z[MAXN << 5];
void build(int l, int r, int rt)
{
	if (l == r)
		return;
	int m = mid;
	z[rt].lson = ++tmp;
	build(l, m, z[rt].lson);
	z[rt].rson = ++tmp;
	build(m + 1, r, z[rt].rson);
}
void modify(int l, int r, int rt, int v, int pre) //rt 是当前点，pre 是要复制的点
{
	z[rt].sum = z[pre].sum + 1; // 插入当前 v，该点记录数字个数 + 1
	if (l == r)
		return;
	int m = mid;
	if (v <= m) // 往左插入
	{ 
		z[rt].lson = ++tmp;
		z[rt].rson = z[pre].rson;
		modify(l, m, z[rt].lson, v, z[pre].lson);
	}
	else // 往右插入
	{
		z[rt].lson = z[pre].lson;
		z[rt].rson = ++tmp;
		modify(m + 1, r, z[rt].rson, v, z[pre].rson);
	}
}
int query(int l, int r, int lrt, int rrt, int k)
{
	if (l == r)
		return l;
	int m = mid, d = z[z[rrt].lson].sum - z[z[lrt].lson].sum; 
    //d 是 左儿子记录的 [L, R] 里的 数字个数，即 sum [1, L] - sum [1, R]
	if (k <= d) 
		return query(l, m, z[lrt].lson, z[rrt].lson, k);
	else
		return query(m + 1, r, z[lrt].rson, z[rrt].rson, k - d); // 注意是 k - d
}
int main()
{
//	freopen("in.txt", "r", stdin);
	scanf("%d%d", &n0, &M);
	rep(i, 1, n0)
	{
		scanf("%d", &a0[i]);
		a[i] = a0[i];
	}
	
	sort(a + 1, a + n0 + 1);
	n = unique(a + 1, a + n0 + 1) - a - 1;
	root[0] = ++tmp; //tmp 用来分配新的点
	build(1, n, 0); // 建个空树，，L = 1 的时候还是要用的
	rep(i, 1, n0) // 依次把每个数字插入进去，每次记录当前状态
	{
		root[i] = ++tmp; //root 即每次操作对应的树根
		int val = lower_bound(a + 1, a + n + 1, a0[i]) - a;
		modify(1, n, root[i], val, root[i-1]);
	}
	
	int L, R, k;
	while (M--)
	{
		scanf("%d%d%d", &L, &R, &k);
		printf("%d\n", a[query(1, n, root[L - 1], root[R], k)]); 
        // 查出来的是排名，记得对应回原数
	}
	
	return 0;
}
水完啦，，溜了溜了
  
 更新于