洛谷 [P3834] 可持久化线段树（主席树）

主席树可以存储线段树的历史状态，空间消耗很大，一般开45n即可
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <queue>

#define lson l, mid

#define rson mid+1, r

#define ll long long

using namespace std;

const int MAXN = 200005;

ll init() {

	ll rv = 0, fh = 1;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-' ) fh = -1;

		c = getchar();

	}

	while(c >= '0' && c <='9') {

		rv = (rv<<1) + (rv<<3) + c - '0';

		c = getchar();

	}

	return fh * rv;

}

ll n, m, num[MAXN],tmp[MAXN];

struct LTSGT {

	ll rot[MAXN], sum[MAXN*45], lpos[MAXN*45], rpos[MAXN*45];

	int cnt = 0;

	int build(int l, int r) {

		int rt = ++cnt;

		if(l == r) {

			sum[rt] = 0;

			return rt;

		}

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

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

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

		return rt;

	}

	int Update(int pre, int l, int r, int x) {

		int rt = ++cnt;

		if(l == r) {

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

			return rt;

		}

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

		lpos[rt] = lpos[pre]; rpos[rt] = rpos[pre]; sum[rt] = sum[pre] + 1;

		if(x <= mid) lpos[rt] = Update(lpos[pre], l, mid, x);

		else rpos[rt] = Update(rpos[pre], mid + 1, r, x);

		return rt;

	}

	int Query(int aa, int bb, int l, int r, int k) {

		if(l == r) return l;

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

		int x = sum[lpos[bb]] - sum[lpos[aa]];

		if(x >= k) return Query(lpos[aa], lpos[bb], l, mid, k);

		else return Query(rpos[aa], rpos[bb], mid + 1, r, k - x); //注意。这里要k-x

	}

	void print(int rt){

		cout<<sum[rt]<<endl;

		if(lpos[rt]) print(lpos[rt]);

		if(rpos[rt]) print(rpos[rt]);

	}

}ltsgt;

int main() {

	freopen("in.txt", "r", stdin);

	n = init(); m = init();

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

		num[i] = init();

		tmp[i] = num[i];

	}

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

	ltsgt.rot[0] = ltsgt.build(1, n);

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

		int t = lower_bound(tmp + 1, tmp + n + 1, num[i]) - tmp;

		ltsgt.rot[i] = ltsgt.Update(ltsgt.rot[i-1], 1, n ,t);

	}

	//ltsgt.print(ltsgt.rot[4]);

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

		int aa = init(), bb = init(), k = init();

		printf("%lld\n", tmp[ltsgt.Query(ltsgt.rot[aa-1], ltsgt.rot[bb], 1, n, k)]); //注意这里是aa-1

	}

	fclose(stdin);

	return 0;

}
巴特西

洛谷 [P3834] 可持久化线段树（主席树）

最新文章

热门文章
