OctoberOctoberOctober 主席树 关于主席树的一些总结

const int maxn = 1e8 + 1;
inline int ()
{
	register int x = 0, ch = getchar(), f = 1;
	while(!isdigit(ch)){if(ch=='-') f = -1;ch = getchar();}
	while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return x*f;
}
struct node{
	int l, r;
	int val;
}t[maxn];

int n, q;
int cnt;
int a[maxn];
int root[maxn];

int build(int l, int r)
{
	int p = ++ cnt;
	if(l == r)
	{
		t[p].val = a[l];
		return cnt;
	}
	int mid = l +r >> 1;
	t[p].l = build(l, mid);
	t[p].r = build(mid+1, r);
	return p;
}

int ins(int pre, int l, int r, int q, int w)
{
	int p = ++ cnt;
	t[p] = t[pre];//完全继承它的上一个节点
	if(l == r)
	{
		t[p].val = w;//修改
		return p;
	}
	int mid = l + r >> 1;
	if(q <= mid) t[p].l = ins(t[p].l, l, mid, q, w);//按线段树的方法递归下去，显然会新建log(n)个节点
	else t[p].r = ins(t[p].r, mid + 1, r, q, w);
	return p;
}

int query(int p, int l, int r, int q)
{
	if(l == r) return t[p].val;
	int mid = l + r >> 1;
	if(q <= mid) return query(t[p].l, l, mid, q);
	else return query(t[p].r, mid + 1, r, q);
}
int main()
{
	n = read();
	q = read();
	for(int i = 1; i <= n; i ++)
	{
		a[i] = read();
	}
	root[0] = build(1, n);
	for(int i = 1; i <= q; i ++)
	{
		int op, x, rt, w;
		rt = read();
		op = read();
		x = read();
		if(op == 1)
		{
			w = read();
			root[i] = ins(root[rt], 1, n, x, w);//一个版本新开一个root
		}
		if(op == 2)
		{
			printf("%dn", query(root[rt], 1, n, x));//查询类似于线段树
			root[i] = root[rt];
		}
	}
}

const int maxn = 1e7 + 1;

struct node{
	int l, r;
	int sum;
}t[maxn];

int root[maxn];
int a[maxn];
int b[maxn];

inline int ()
{
	int x = 0, ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = x * 10 + ch -'0', ch = getchar();
	return x;
}
int n, q;
int cnt;
int m;

int build(int l, int r)
{
	int p = ++ cnt;
	t[p].sum = 0;
	int mid = l + r >> 1;
	if(l < r)
	{
		t[p].l = build(l, mid);
		t[p].r = build(mid + 1, r);
	}	
	return p;
}

int add(int pre, int l, int r, int x)
{
	int p = ++ cnt;
	t[p] = t[pre];//完全继承上一个节点，只会修改log(n)个节点
	t[p].sum ++;
	int mid = l + r >> 1;
	if(l < r)
	{
		if(x <= mid) t[p].l = add(t[pre].l, l, mid, x);
		else t[p].r = add(t[pre].r, mid + 1, r, x);//一路递归下去
	}
	return p;
}

int query(int u, int v, int l, int r, int k)
{
	if(l >= r) return l;
	int x = t[t[v].l].sum - t[t[u].l].sum;//和上文一样所说的相减操作
	int mid = l + r >> 1;
	if(x >= k) return query(t[u].l, t[v].l, l, mid, k);//和权值线段树一样的查询操作
	else return query(t[u].r, t[v].r, mid + 1, r, k - x);
}
int main()
{
	n = read();
	q = read();
	for(int i = 1; i <= n; i ++)
	{
		a[i] = read();
		b[i] = a[i];
	}
	std:: sort(b + 1, b + 1 + n);
	m = std:: unique(b + 1, b + 1 + n) - b - 1;//离散化操作
	root[0] = build(1, m);
	for(int i = 1; i <= n; i ++)
	{
		int t = std:: lower_bound(b + 1, b + 1 + m, a[i]) - b;
		root[i] = add(root[i - 1], 1, m, t);//每一次新建一个根节点
	}
	while(q --)
	{
		int x, y, z;
		x = read();
		y = read();
		z = read();
		int t = query(root[x-1], root[y], 1, m, z);//同时查询r和了l - 1所代表的权值线段树
		printf("%dn", b[t]);
	}
}