P2839 [国家集训队] middle（二分+可持久化线段树）

P2839 [国家集训队] middle

二分+可持久化线段树

中位数经典做法，二分答案，将小于的部分看做 \(-1\)，大于等于的部分看做 \(+1\)，那么答案可以更大的条件就是区间和大于等于 \(0\)（等于 \(0\) 可不可以取到看是下取整还是上取整，本题是上取整）。

那么问题就是怎么判断有没有这样一个区间满足条件了。可以想到取 \([a,b]\) 中一段最大后缀子段和，取 \([b+1,c-1]\)，取 \([c,d]\) 的一段最大前缀子段和，和最大。

想到这里，如果每一次二分都要建一棵新的树，那么复杂度就炸了。这里可以发现每一个数从 \(+1\) 变为 \(-1\) 只改变了一条线段树上的链，所以可以用可持久化线段树预处理出每个数的线段树。

复杂度 \(O(n\log^2 n)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define mk std::make_pair
#define pb push_back

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e4 + 10;
int n, Q, ans, tot;
int q[4], a[N], id[N], rt[N];
struct seg {
	int l, r;
	int lmax, rmax, sum;
} t[N << 5];
void pushup(seg &u, seg ls, seg rs) {
	u.lmax = std::max(ls.lmax, ls.sum + rs.lmax);
	u.rmax = std::max(rs.rmax, rs.sum + ls.rmax);
	u.sum = ls.sum + rs.sum;
}
void build(int &u, int l, int r) {
	u = ++tot;
	if(l == r) {t[u].sum = t[u].lmax = t[u].rmax = 1; return;}
	int mid = (l + r) >> 1;
	build(t[u].l, l, mid), build(t[u].r, mid + 1, r);
	pushup(t[u], t[t[u].l], t[t[u].r]);
}
void upd(int &o, int u, int l, int r, int x) {
	o = ++tot;
	t[o] = t[u];
	if(l == r) {
		t[o].sum = t[o].lmax = t[o].rmax = -1;
		return;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) upd(t[o].l, t[u].l, l, mid, x);
	else upd(t[o].r, t[u].r, mid + 1, r, x);
	pushup(t[o], t[t[o].l], t[t[o].r]);
}
seg qry(int u, int l, int r, int L, int R) {
	if(L <= l && r <= R) return t[u];
	int mid = (l + r) >> 1;
	if(R <= mid) return qry(t[u].l, l, mid, L, R);
	if(L > mid) return qry(t[u].r, mid + 1, r, L, R);
	seg ret = {0, 0, 0}, ls = qry(t[u].l, l, mid, L, R), rs = qry(t[u].r, mid + 1, r, L, R);
	pushup(ret, ls, rs);
	return ret;
}
bool check(int x) {
	seg f1 = qry(rt[x], 1, n, q[0], q[1]), f3 = qry(rt[x], 1, n, q[2], q[3]);
	if(q[1] + 1 <= q[2] - 1) {
		seg f2 = qry(rt[x], 1, n, q[1] + 1, q[2] - 1);
		// std::cout << x << " " << f1.rmax << " " << f2.sum << " " << f3.lmax << " f\n";
		return f1.rmax + f2.sum + f3.lmax >= 0;
	}
	// std::cout << x << " " << f1.rmax << " " << f3.lmax << " f\n";
 	return f1.rmax + f3.lmax >= 0; 
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	std::cin >> n;
	for(int i = 1; i <= n; i++) std::cin >> a[i], id[i] = i;
	std::sort(id + 1, id + n + 1, [](int x, int y) {return a[x] < a[y];});
	build(rt[1], 1, n);
	for(int i = 2; i <= n; i++) {
		upd(rt[i], rt[i - 1], 1, n, id[i - 1]);
	}
	std::cin >> Q;
	int lst = 0;
	while(Q--) {
		for(int i = 0; i < 4; i++) std::cin >> q[i], q[i] = (q[i] + lst) % n + 1;
		std::sort(q, q + 4);
		// std::cout << q[0] << " " << q[1] << " " << q[2] << " " << q[3] << "\n";
		int l = 1, r = n;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if(check(mid)) ans = a[id[mid]], l = mid + 1;
			else r = mid - 1;
		}
		std::cout << ans << "\n";
		lst = ans;
	}

	return 0;
}