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
", ans);
	}
	
}
//6
//1 2 3 4 5 6
//1
//0 1 4 5