求助（关于空间）

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133#include <bits/stdc++.h>
using namespace std;
const int N = 20005, V = 800005;
int n,q,lsh[N],rt[N];
int l1,r1,l2,r2,tot;
int inp[5],ans;
struct node
{
	int id,val;
}a[N];
bool cmp(node x,node y)
{
	return x.val < y.val;
}
#define mid ((l+r)>>1)
#define ls (t[p].l)
#define rs (t[p].r)
struct segtree
{
	int l,r,sum;
	int lsum,rsum;
}t[V];
void update(int p)
{
	t[p].sum = t[ls].sum + t[rs].sum;
	t[p].lsum = max(t[ls].sum + t[rs].lsum,t[ls].lsum);
	t[p].rsum = max(t[rs].rsum,t[ls].rsum + t[rs].sum);
	return;
}
int change(int p,int l,int r,int x,int d)
{
	t[++tot] = t[p];
	p = tot;
	if (l == r)
	{
		t[p].sum += d;
		t[p].lsum = max(0,t[p].sum);
		t[p].rsum = max(0,t[p].sum);
		return p;
	}
	if (x <= mid) ls = change(ls,l,mid,x,d);
	else rs = change(rs,mid+1,r,x,d);
	update(p);
	return p;
}
int query_sum(int p,int l,int r,int ql,int qr)
{
	if (ql <= l && r <= qr) return t[p].sum;
	int res = 0;
	if (ql <= mid) res += query_sum(ls,l,mid,ql,qr);
	if (qr > mid) res += query_sum(rs,mid+1,r,ql,qr);
	return res;
}
pair<int,int> query_lsum(int p,int l,int r,int ql,int qr)
{
	if (ql <= l && r <= qr) return make_pair(t[p].lsum,t[p].sum);
	if (ql <= mid && qr > mid)
	{
		pair<int,int> sl = query_lsum(ls,l,mid,ql,qr);
		pair<int,int> sr = query_lsum(rs,mid+1,r,ql,qr);
		int res1 = max(sl.first,sl.second+sr.first);
		int res2 = sl.second + sr.second;
		return make_pair(res1,res2);
	}
	if (ql <= mid) return query_lsum(ls,l,mid,ql,qr);
 	return query_lsum(rs,mid+1,r,ql,qr);
}
pair<int,int> query_rsum(int p,int l,int r,int ql,int qr)
{
	if (ql <= l && r <= qr) return make_pair(t[p].rsum,t[p].sum);
	if (ql <= mid && qr > mid)
	{
		pair<int,int> sl = query_rsum(ls,l,mid,ql,qr);
		pair<int,int> sr = query_rsum(rs,mid+1,r,ql,qr);
		int res1 = max(sr.first,sr.second+sl.first);
		int res2 = sl.second + sr.second;
		return make_pair(res1,res2);
	}
	if (ql <= mid) return query_rsum(ls,l,mid,ql,qr);
 	return query_rsum(rs,mid+1,r,ql,qr);
}
bool check(int x)
{
	int res = 0;
	pair<int,int> s;
	res = query_sum(rt[x],1,n,r1,l2);
	s = query_rsum(rt[x],1,n,l1,r1-1);
	res += s.first;
	s = query_lsum(rt[x],1,n,l2+1,r2);
	res += s.first;
	return res >= 0;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].val);
		lsh[i] = a[i].val;
	}
	sort(lsh+1,lsh+n+1);
	for (int i=1;i<=n;i++)
	{
		a[i].val = lower_bound(lsh+1,lsh+n+1,a[i].val) - lsh;
		a[i].id = i;
	}
	for (int i=1;i<=n;i++)
	{
		rt[1] = change(rt[1],1,n,a[i].id,1);
	}
	sort(a+1,a+n+1,cmp);
	for (int i=1;i<=n;i++)
	{
		rt[i+1] = change(rt[i],1,n,a[i].id,-2);
	}
	scanf("%d",&q);
	while (q--)
	{
		for (int i=0;i<4;i++) 
		{
			scanf("%d",&inp[i]);
			inp[i] = (inp[i] + ans) % n + 1; 
		}
		sort(inp,inp+4);
		l1 = inp[0]; r1 = inp[1];
		l2 = inp[2]; r2 = inp[3];
		int l = 1, r = n;
		ans = 1;
		while (l <= r)
		{
			if (check(mid))
			{
				ans = lsh[mid];
				l = mid + 1;
			}
			else r = mid - 1;
		}
		printf("%d\n",ans);
	}
	return 0;
}