题目：

洛谷2839

分析：

记\(s_i\)表示原序列中第\(i\)大的数。

考虑对于任意一个区间\([a,b]\)，设它的中位数为\(s_m\)，那么这个区间内大于等于\(s_m\)的数和小于\(s_m\)的数的数量要么相等，要么小于比大于等于多一个。后一种情况当且仅当\(s_m\in [a,b]\)且序列长度为奇数。

考虑如果已知一个数\(s_i\)，如何判断是否存在区间\([e,f]\)（\(e\in [a,b],f\in [c,d]\)）使\([e,f]\)的中位数大于等于\(s_i\)呢（显然满足条件的\(i\)是单调的，可以二分）？

对于\(s_i\)，记所有小于它的数为\(-1\)，大于等于它的数为\(1\)，那么如果能找到一个符合条件的区间\([e,f]\)使这段区间的和大于等于\(0\)说明最大中位数大于等于\(s_i\)，记录答案并尝试更大的\(i\)；否则不符合条件，需要调小\(i\)。

此时问题变成了已知一个\(1\)和\(-1\)组成的序列，求一个\([e,f]\)使它的区间和最大。把\([e,f]\)拆成三部分：必选的\((b,c)\)，在\([a,b]\)中选一段后缀的\([e,b]\)和在\([c,d]\)中选一段前缀的\([c,f]\)。这个可以用线段树解决，方法类似【Vijos1083/BZOJ1756】小白逛公园（线段树），查询\((b,c)\)的\(val\)，\([a,b]\)的\(rm\)和\([c,d]\)的\(lm\)。

\(s_i\)对应的线段树和\(s_{i-1}\)对应的线段树的区别仅仅是把\((i-1)\)位置的\(1\)变成了\(-1\)，因此可以用主席树维护节省空间。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

namespace zyt

{

	const int N = 2e4 + 10, Q = 2.5e4 + 10;

	int n, q, tmp[N], head[N];

	pair<int, int> arr[N];

	namespace Chairman_Tree

	{

		const int SUM = 0, SUML = 1, SUMR = 2;

		struct node

		{

			int sum, suml, sumr, s[2];

			node(): sum(0), suml(0), sumr(0)

			{

				s[0] = s[1] = 0;

			}

		}tree[N * 20];

		int cnt;

		inline void update(node &now, const node &lt, const node &rt)

		{

			now.suml = now.sumr = 0;

			now.sum = lt.sum + rt.sum;

			now.suml = max(lt.suml, lt.sum + rt.suml);

			now.sumr = max(rt.sumr, rt.sum + lt.sumr);

		}

		inline void update(const int rot)

		{

			update(tree[rot], tree[tree[rot].s[0]], tree[tree[rot].s[1]]);

		}

		int build(const int lt, const int rt, const int val)

		{

			int rot = ++cnt;

			if (lt == rt)

			{

				tree[rot].sum = tree[rot].suml = tree[rot].sumr = -1 + 2 * (tmp[lt] >= val);

				return rot;

			}

			int mid = (lt + rt) >> 1;

			tree[rot].s[0] = build(lt, mid, val);

			tree[rot].s[1] = build(mid + 1, rt, val);

			update(rot);

			return rot;

		}

		int change(const int pre, const int lt, const int rt, const int pos, const int x)

		{

			int rot = ++cnt;

			tree[rot] = tree[pre];

			if (lt == rt)

			{

				tree[rot].sum = x;

				tree[rot].suml = x;

				tree[rot].sumr = x;

				return rot;

			}

			int mid = (lt + rt) >> 1;

			if (pos <= mid)

				tree[rot].s[0] = change(tree[pre].s[0], lt, mid, pos, x);

			else

				tree[rot].s[1] = change(tree[pre].s[1], mid + 1, rt, pos, x);

			update(rot);

			return rot;

		}

		node query(const int rot, const int lt, const int rt, const int ls, const int rs)

		{

			if (ls <= lt && rt <= rs)

				return tree[rot];

			int mid = (lt + rt) >> 1;

			if (rs <= mid)

				return query(tree[rot].s[0], lt, mid, ls, rs);

			else if (ls > mid)

				return query(tree[rot].s[1], mid + 1, rt, ls, rs);

			else

			{

				node tmp[2] = {query(tree[rot].s[0], lt, mid, ls, rs),

				   				query(tree[rot].s[1], mid + 1, rt, ls, rs)};

				node ans;

				update(ans, tmp[0], tmp[1]);

				return ans;

			}

		}

		int query(const int rot, const int ls, const int rs, const int type)

		{

			node ans = query(rot, 0, n - 1, ls, rs);

			switch (type)

			{

			case SUM:

				return ans.sum;

			case SUML:

				return ans.suml;

			case SUMR:

				return ans.sumr;

			}

		}

	}

	int work()

	{

		using namespace Chairman_Tree;

		ios::sync_with_stdio(false);

		cin.tie(0);

		cin >> n;

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

			cin >> arr[i].first, arr[i].second = i, tmp[i] = arr[i].first;

		sort(arr, arr + n);

		head[0] = build(0, n - 1, arr[0].first);

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

			head[i] = change(head[i - 1], 0, n - 1, arr[i - 1].second, -1);

		cin >> q;

		int x = 0;

		while (q--)

		{

			int in[4];

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

				cin >> in[i], in[i] = (in[i] + x) % n;

			sort(in, in + 4);

			int l = 0, r = n - 1, ans;

			while (l <= r)

			{

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

				int tmp = query(head[mid], in[0], in[1], SUMR) + query(head[mid], in[2], in[3], SUML);

				if (in[1] + 1 <= in[2] - 1)

					tmp += query(head[mid], in[1] + 1, in[2] - 1, SUM);

				if (tmp >= 0)

					l = mid + 1, ans = mid;

				else

					r = mid - 1;

			}

			cout << arr[ans].first << '\n';

			x = arr[ans].first;

		}

		return 0;

	}

}

int main()

{

	return zyt::work();

}