Luogu P2839 [国家集训队]middle

首先 [b,c] 是必选的， 然后选一段 [a,b) 的后缀和一段 (c,d] 的前缀（都可空）。

对于中位数（这里中位数采用这道题的定义）有个常见的处理方式： 二分 mid， 将 <mid 的设为 -1， 其余设为 1， 求总和， 若总和 >0， 则说明 ≥mid 的占到了一半以上， 即中位数 ≥mid。

采用这种处理方式， 二分中位数， 由于要中位数尽量大， 所以要贪心， 选后缀和前缀使得大于等于 mid 的减去小于等于 mid 的最大。

可以用可持久化线段树， 具体地， 类似笛卡尔树， 从小到大插入元素， 找出最大的前缀和后缀， 是可并信息， 可做。

#include<bits/stdc++.h>

using namespace std;

const int N = 2e4 + 23, SZ = 17 * 2e4 + 233;

int n;
struct Seq { int i, a; } seq[N];
bool cmp(Seq s1, Seq s2) { return s1.a > s2.a; }

struct dat {
	int siz, all, mxpre, mxsuf;
	dat(int sz, int a, int p, int s) : siz(sz), all(a), mxpre(p), mxsuf(s) {
	}
	dat() {
	}
} t[SZ];
dat mg(dat lef, dat rig) {
	return dat(  lef.siz + rig.siz, lef.all + rig.all, max(lef.mxpre, lef.all + rig.mxpre), max(rig.mxsuf, rig.all + lef.mxsuf)  );
}

int tot, Root[N], ls[SZ], rs[SZ];

void ins(int p, int &q, int l, int r, int x) {
	q = ++tot;
	if(l == r)
		{ t[q] = dat(1, 1, 1, 1); return;}
	ls[q] = ls[p], rs[q] = rs[p];
	int mid = (l+r) >> 1;
		if(x<=mid)
			ins(ls[p], ls[q], l, mid, x);
		else
			ins(rs[p], rs[q], mid+1, r, x);
	t[q] = mg((ls[q]?t[ls[q]]:dat(mid-l+1,-(mid-l+1),0,0)), (rs[q]?t[rs[q]]:dat(r-mid,-(r-mid),0,0)));
}

dat ask(int me, int l, int r, int x, int y) {
	if(x<=l && r<=y) return (me ? t[me] : dat(r-l+1, -(r-l+1), 0, 0));
		int mid = (l+r) >> 1;
	if(x<=mid && y>mid) return mg(ask(ls[me], l, mid, x, y), ask(rs[me], mid+1, r, x, y));
	if(x<=mid) return ask(ls[me], l, mid, x, y);
	if(y>mid) return ask(rs[me], mid+1, r, x, y);
}

bool chk(int mid, int a, int b, int c, int d) {
	int base = ask(Root[mid], 1, n, b, c).all + ask(Root[mid], 1, n, a, b-1).mxsuf + ask(Root[mid], 1, n, c+1, d).mxpre;
	return base >= 0;
}

int sol(int a, int b, int c, int d) {
	int l=1, r=n;
	while(l!=r) {
		int mid = (l+r) >> 1;
		chk(mid, a, b, c, d) ? r=mid : l=mid+1;
	}
	return seq[l].a;
}

int main()
{
	scanf("%d", &n);
	for(int i=1; i<=n; ++i) scanf("%d", &seq[i].a), seq[i].i = i;
	sort(seq+1, seq+1+n, cmp);
	for(int i=1; i<=n; ++i) ins(Root[i-1], Root[i], 1, n, seq[i].i);
	int Q;
	scanf("%d", &Q);
	int q[4] = {0}, las = 0;
	while(Q--)
	{
		for(int i=0; i<4; ++i) { scanf("%d", &q[i]); q[i] = (q[i] + las) % n + 1; }
		sort(q, q+4);
		las = sol(q[0], q[1], q[2], q[3]);
		cout << las << '
';
	}
	return 0;
}