自动搬运

查看原文

来自洛谷，原作者为

	Cyhlnj **

搬运于2025-08-24 21:42:09，当前版本为作者最后更新于2018-03-12 20:40:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Sol

丽洁姐的题目还是棒棒的

考虑二分答案

$Check?$ 把小于它的设为$-1$，大于等于它的设为$1$

$[a, b]$求一个最大后缀子段和 $[c, d]$求一个最大前缀子段和 $[b+1, c-1]$求一个和

加起来如果大于等于$0$，那么满足要求 且这个数还可以变大，否则就只能缩小

每个数开一个线段树来做，空间开不下，用主席树即可

那么问题来了 会不会二分的答案不在这个区间内呢？ 显然是不会的，如果区间外有个数满足要求，那么区间内一定会有个数大于等于它，显然区间内的那个数最优，而且也是满足要求的

那么做完了

# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(1e5 + 5);

IL int Input(){
    RG int x = 0, z = 1; RG char c = getchar();
    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x * z;
}

int rt[_], a[_], n, tot, q[4], id[_];
struct Mx{
	int lmax, rmax, sum, mx;

	IL void Init(){
		lmax = rmax = -_, sum = 0;
	}
} Ans;
struct HJT{
	int ls, rs;
	Mx v;
} T[_ * 20];

IL Mx Merge(RG Mx A, RG Mx B){
	RG Mx C;
	C.lmax = max(A.lmax, A.sum + B.lmax);
	C.rmax = max(B.rmax, A.rmax + B.sum);
	C.sum = A.sum + B.sum;
	return C;
}

IL void Build(RG int &x, RG int l, RG int r){
	x = ++tot;
	T[x].v.lmax = T[x].v.rmax = T[x].v.sum = r - l + 1;
	if(l == r) return;
	RG int mid = (l + r) >> 1;
	Build(T[x].ls, l, mid), Build(T[x].rs, mid + 1, r);
}


IL void Modify(RG int &x, RG int l, RG int r, RG int p){
	T[++tot] = T[x], x = tot;
	if(l == r){
		T[x].v.lmax = T[x].v.rmax = T[x].v.sum = -1;
		return;
	}
	RG int mid = (l + r) >> 1;
	if(p <= mid) Modify(T[x].ls, l, mid, p);
	else Modify(T[x].rs, mid + 1, r, p);
	T[x].v = Merge(T[T[x].ls].v, T[T[x].rs].v);
}

IL void Query(RG int x, RG int l, RG int r, RG int L, RG int R){
	if(L <= l && R >= r){
		Ans = Merge(Ans, T[x].v);
		return;
	}
	RG int mid = (l + r) >> 1;
	if(L <= mid) Query(T[x].ls, l, mid, L, R);
	if(R > mid) Query(T[x].rs, mid + 1, r, L, R);
}

IL int Check(RG int mid){
	RG int val = 0;
	if(q[1] + 1 <= q[2] - 1) Ans.Init(), Query(rt[mid], 1, n, q[1] + 1, q[2] - 1), val += Ans.sum;
	Ans.Init(), Query(rt[mid], 1, n, q[0], q[1]), val += Ans.rmax;
	Ans.Init(), Query(rt[mid], 1, n, q[2], q[3]), val += Ans.lmax;
	return val >= 0;
}

IL int Cmp(RG int x, RG int y){
	return a[x] < a[y];
}

int main(RG int argc, RG char* argv[]){
	n = Input(), Build(rt[1], 1, n), T[0].v.Init();
	for(RG int i = 1; i <= n; ++i) a[i] = Input(), id[i] = i;
	sort(id + 1, id + n + 1, Cmp);
	for(RG int i = 2; i <= n; ++i) rt[i] = rt[i - 1], Modify(rt[i], 1, n, id[i - 1]);
	for(RG int Q = Input(), ans = 0; Q; --Q){
		for(RG int i = 0; i < 4; ++i) q[i] = (Input() + ans) % n + 1;
		sort(q, q + 4);
		RG int l = 1, r = n;
		while(l <= r){
			RG int mid = (l + r) >> 1;
			if(Check(mid)) ans = a[id[mid]], l = mid + 1;
			else r = mid - 1;
		}
		printf("%d\n", ans);
	}
    return 0;
}