洛谷P3567 [POI2014]KUR-Couriers 主席树

挺裸的，没啥可讲的。

不带修改的主席树裸题

Code:

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn = 500000 + 5;

int  n, m ,root[maxn];

struct Chair_Tree{

	int cnt_Tree;

	int lson[maxn * 50], rson[maxn * 50], sumv[maxn * 50];

	void build(int l, int r, int &o){

		if(l > r) return ;

		o = ++cnt_Tree;

		if(l == r) return ;

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

		build(l, mid, lson[o]);

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

	}

	int insert(int l, int r, int pos, int o){

		int oo = ++cnt_Tree;

		lson[oo] = lson[o], rson[oo] = rson[o], sumv[oo] = sumv[o] + 1;

		if(l == r) return oo;

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

		if(pos <= mid) lson[oo] = insert(l, mid, pos, lson[o]);

		else rson[oo] = insert(mid + 1, r, pos, rson[o]);

		return oo;

	}

	int query(int l, int r, int k, int pre_o, int cur_o){

		if(l == r) return l;

		int lsum = sumv[lson[cur_o]] - sumv[lson[pre_o]];

		int cur_sum = sumv[cur_o] - sumv[pre_o];

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

		if(k <= lsum) return query(l, mid, k, lson[pre_o], lson[cur_o]);

		else if(cur_sum - lsum >= k) return query(mid + 1, r, k, rson[pre_o], rson[cur_o]);

		else return 0;

	}

}T;

int main(){

	scanf("%d%d",&n,&m);

	T.build(1, n, root[0]);

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

	{

		int cur_num;

		scanf("%d",&cur_num);

		root[i] = T.insert(1, n, cur_num, root[i - 1]);

	}

	while(m--){

		int l, r, k;

		scanf("%d%d",&l,&r);

		k = (r - l + 1)/2 + 1;

		printf("%d\n", T.query(1, n, k, root[l - 1], root[r]));

	}

	return 0;

}

巴特西

洛谷P3567 [POI2014]KUR-Couriers 主席树

最新文章

热门文章