bzoj 2653 middle(主席树）

题面:https://vjudge.net/problem/HYSBZ-2653

博客：https://blog.csdn.net/litble/article/details/78984846

这个题很明显不能建n棵动态开点的线段树，因为每颗线段树点分布都很密集，这样相当于都是满二叉树。但是，我们可以发现，相邻的每颗线段树只有一个位置不同，这样我们就可以用主席树了。主席树相当于每次只多开了O(logn)个节点就能新开一棵线段树。

代码：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 100010;

struct SegementTree {

	int lson, rson;

	int sum, lsum, rsum;

};

SegementTree tr[maxn * 200];

int tot = 0, n;

int root[maxn];

struct res {

	int sum, val;

};

struct node {

	int val, pos;

	bool operator < (const node& rhs) const {

		return val < rhs.val;

	}

};

node a[maxn];

int b[5];

void pushup(int x) {

	int ls = tr[x].lson, rs = tr[x].rson;

	tr[x].sum = tr[ls].sum + tr[rs].sum;

	tr[x].lsum = max(tr[ls].lsum, tr[ls].sum + tr[rs].lsum);

	tr[x].rsum = max(tr[rs].rsum, tr[rs].sum + tr[ls].rsum);

}

void build(int now, int l, int r) {

	if(l == r) {

		tr[now].sum = tr[now].lsum= tr[now].rsum = 1;

		return;

	}

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

	tr[now].lson = ++tot;build(tot, l, mid);

	tr[now].rson = ++tot;build(tot, mid + 1, r);

	pushup(now);

}

void insert(int lnow, int rnow, int l, int r, int pos, int val) {

	tr[rnow] = tr[lnow];

	if(l == r) {

		tr[rnow].sum = tr[rnow].lsum = tr[rnow].rsum = val;

		return;

	}

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

	if(pos <= mid) {

		tr[rnow].lson = ++tot;

		insert(tr[lnow].lson, tot, l, mid, pos ,val);

	} else {

		tr[rnow].rson = ++tot;

		insert(tr[lnow].rson, tot, mid + 1, r, pos, val);

	}

	pushup(rnow);

}

int query_sum(int now, int l, int r, int ql, int qr) {

	if(l >= ql && r <= qr) {

		return tr[now].sum;

	}

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

	int ans = 0;

	if(ql <= mid) ans += query_sum(tr[now].lson, l, mid, ql, qr);

	if(qr > mid) ans += query_sum(tr[now].rson, mid + 1, r, ql, qr);

	return ans;

}

res query_lsum(int now, int l, int r, int ql, int qr) {

	if(l >= ql && r <= qr) {

		return (res){tr[now].sum, tr[now].lsum};

	}

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

	res ans = (res){0, -INF}, tmp = (res){0, -INF};

	if(ql <= mid) ans = query_lsum(tr[now].lson, l, mid, ql, qr);

	if(qr > mid) tmp = query_lsum(tr[now].rson, mid + 1, r, ql, qr);

	ans.val = max(ans.val, ans.sum + tmp.val);

	ans.sum += tmp.sum;

	return ans;

}

res query_rsum(int now, int l, int r, int ql, int qr) {

	if(l >= ql && r <= qr) {

		return (res){tr[now].sum, tr[now].rsum};

	}

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

	res ans = (res){0, -INF}, tmp = {0, -INF};

	if(ql <= mid) ans = query_rsum(tr[now].lson, l, mid, ql, qr);

	if(qr > mid) tmp = query_rsum(tr[now].rson, mid + 1, r, ql, qr);

	ans.val = max(tmp.val, ans.val + tmp.sum);

	ans.sum += tmp.sum;

	return ans;

}

int solve(int x) {

	int tmp1 = 0, tmp2 = 0, tmp3 = 0;

	if(b[1] + 1 < b[2]) tmp1 = query_sum(root[x], 0, n - 1, b[1] + 1, b[2] - 1);

	tmp2 = query_lsum(root[x], 0, n - 1, b[2], b[3]).val;

	tmp3 = query_rsum(root[x], 0, n - 1,b[0], b[1]).val;

	if(tmp1 + tmp2 + tmp3 >= 0) return 1;

	return 0;

}

int main() {

	int m;

	scanf("%d", &n);

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

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

		a[i].pos = i;

	}

	sort(a, a + n);

	root[0] = ++tot;

	build(tot, 0, n - 1);

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

		root[i] = ++tot;

		insert(root[i - 1], tot, 0, n - 1, a[i - 1].pos, -1);

	}

	int ans = 0;

	scanf("%d", &m);

	while(m--) {

		for (int i = 0; i < 4; i++) {

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

			b[i] = (b[i] + ans) % n;

		}

		sort(b, b + 4);

		int l = 0, r = n - 1;

		while(l < r) {

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

			if(solve(mid))l = mid;

			else r = mid - 1;

		}

		ans = a[l].val;

		printf("%d\n", ans);

	}

}

//6

//1 2 3 4 5 6

//1

//0 1 4 5

巴特西

bzoj 2653 middle(主席树）

最新文章

热门文章