luogu3834 【模板】可持久化线段树 1（主席树）

关于空间，第零棵树是 \(4n\)，其后每棵树都要多来 \(\log(n)\) 的空间，所以我是开 \(n(4+\log(n))\) 的空间。

关于借用节点：

图片来自这里

#include <algorithm>

#include <iostream>

#include <cstdio>

using namespace std;

int n, m, rot[200005], a[200005], b[200005], sum[4400005], lson[4400005];

int rson[4400005], uu, vv, ww, r, cnt;

int build(int l, int r){

	int rt=++cnt;

	int mid=(l+r)>>1;

	sum[rt] = 0;

	if(l<r){

		lson[rt] = build(l, mid);

		rson[rt] = build(mid+1, r);

	}

	return rt;

}

int update(int pre, int l, int r, int x){//pre就是rt准备“借”的那棵树

	int rt=++cnt;

	int mid=(l+r)>>1;

	lson[rt] = lson[pre]; rson[rt] = rson[pre]; sum[rt] = sum[pre] + 1;

	if(l<r){

		if(x<=mid)	lson[rt] = update(lson[pre], l, mid, x);

		else	rson[rt] = update(rson[pre], mid+1, r, x);

	}

	return rt;

}

int query(int uu, int vv, int l, int r, int k){

	if(l>=r)	return l;

	int x=sum[lson[vv]]-sum[lson[uu]];

	int mid=(l+r)>>1;

	if(x>=k)	return query(lson[uu], lson[vv], l, mid, k);

	else	return query(rson[uu], rson[vv], mid+1, r, k-x);

}

int main(){

	cin>>n>>m;

	for(int i=1; i<=n; i++){

		scanf("%d", &a[i]);

		b[i] = a[i];

	}

	sort(b+1, b+1+n);

	r = unique(b+1, b+1+n) - (b + 1);

	rot[0] = build(1, r);

	for(int i=1; i<=n; i++){

		int t=lower_bound(b+1, b+1+r, a[i])-b;//快速找出a[i]在整个不可重数组中的位置

		rot[i] = update(rot[i-1], 1, r, t);

	}

	while(m--){

		scanf("%d %d %d", &uu, &vv, &ww);

		printf("%d\n", b[query(rot[uu-1], rot[vv], 1, r, ww)]);

	}

	return 0;

}

巴特西

luogu3834 【模板】可持久化线段树 1（主席树）

最新文章

热门文章