「国家集训队」middle

发表于 | 分类于 | | 浏览量： 次

丽洁姐的题目，不错不错。

传送门

洛谷P2839

BZOJ2653

题解

这题还是挺好玩的。

首先可以二分枚举答案。设当前枚举到的答案为$mid$，那么就把大于等于当前答案的数标为1，小于的标为-1。如果两个端点分别在指定区间内的加和最大的区间的加和大于等于0，那么当前二分到的值可以再大一些，否则就应该小一些。

由于最后的区间必然包括$[b+1,c-1]$，所以需要求出区间$[a,b]$的最大后缀和以及区间$[c,d]$的最大前缀和。

先对原序列离散化，这样最后可能二分到的答案就只剩下$n$个。然以后对于每一个可能二分到的答案，将以它为基准构造出的由1和-1组成的序列预处理出来，用线段树就可以维护一个区间的加和、最大前缀和、最大后缀和。但是这样复杂度是爆炸的。所以可以先排序，然后由于每次按顺序修改基准数只会将一个位置的值由1改为-1，所以用主席树维护就好了。

原序列中可能有相同元数字，注意细节即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=20005,LOG=16;
int n,Q,cnt,A[maxn],id[maxn],q[10],ans;map<int,int> CR;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct ChairmanTree
{
	int tot,R[maxn];
	struct Node{int L,R,Sum,FMS,BMS;}Tree[maxn*2*LOG];
	inline void PushUp(int rt)
	{
		Tree[rt].Sum=Tree[Tree[rt].L].Sum+Tree[Tree[rt].R].Sum;
		Tree[rt].FMS=max(Tree[Tree[rt].L].FMS,Tree[Tree[rt].L].Sum+Tree[Tree[rt].R].FMS);
		Tree[rt].BMS=max(Tree[Tree[rt].R].BMS,Tree[Tree[rt].R].Sum+Tree[Tree[rt].L].BMS);
	}
	inline int New(){return ++tot;}
	void Build(int rt,int L=1,int R=n)
	{
		if(L==R){Tree[rt].Sum=Tree[rt].FMS=Tree[rt].BMS=1;return;}
		Tree[rt].L=New();
		Tree[rt].R=New();
		int M=(L+R)>>1;
		Build(Tree[rt].L,L,M);
		Build(Tree[rt].R,M+1,R);
		PushUp(rt);
	}
	void Update(int rt,int pre,int p,int L=1,int R=n)
	{
		if(L==R){Tree[rt].Sum=Tree[rt].FMS=Tree[rt].BMS=-1;return;}
		Tree[rt]=Tree[pre];
		int M=(L+R)>>1;
		if(p<=M)
		{
			Tree[rt].L=New();
			Update(Tree[rt].L,Tree[pre].L,p,L,M);
		}
		if(M<p)
		{
			Tree[rt].R=New();
			Update(Tree[rt].R,Tree[pre].R,p,M+1,R);
		}
		PushUp(rt);
	}
	Node Query(int rt,int LL,int RR,int L=1,int R=n)
	{
		if(LL>RR){return (Node){0,0,0,0,0};}
		if(LL<=L&&R<=RR) return Tree[rt];
		int M=(L+R)>>1;Node IL,IR,ret;
		if(LL<=M) IL=Query(Tree[rt].L,LL,RR,L,M);
		if(M<RR) IR=Query(Tree[rt].R,LL,RR,M+1,R);
		if(LL<=M&&M>=RR) return IL;
		if(LL>M&&M<RR) return IR;
		ret.Sum=IL.Sum+IR.Sum;
		ret.FMS=max(IL.FMS,IL.Sum+IR.FMS);
		ret.BMS=max(IR.BMS,IR.Sum+IL.BMS);
		return ret;
	}
}CT;
inline bool cmp(int x,int y){return A[x]<A[y];}
inline void Solve(int a,int b,int c,int d)
{
	int L=1,R=n,mid;
	while(L<=R)
	{
		mid=(L+R)>>1;
		ChairmanTree::Node IL=CT.Query(CT.R[CR[A[id[mid]]]],a,b),IM=CT.Query(CT.R[CR[A[id[mid]]]],b+1,c-1),IR=CT.Query(CT.R[CR[A[id[mid]]]],c,d);
		IL.BMS+IM.Sum+IR.FMS>=0?L=mid+1:R=mid-1;
	}
	ans=A[id[R]];
	printf("%d\n",ans);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++) A[i]=read();
	for(int i=1;i<=n;i++) id[i]=i;
	sort(id+1,id+1+n,cmp);
	CT.R[1]=CT.New();CT.Build(1);CR[A[id[1]]]=1;
	for(int i=2;i<=n;i++)
	{
		CT.R[i]=CT.New();
		if(!CR[A[id[i]]]) CR[A[id[i]]]=i;
		CT.Update(CT.R[i],CT.R[i-1],id[i-1]);
	}
	Q=read();
	while(Q--)
	{
		q[1]=(read()+ans)%n+1;q[2]=(read()+ans)%n+1;q[3]=(read()+ans)%n+1;q[4]=(read()+ans)%n+1;
		sort(q+1,q+1+4);
		Solve(q[1],q[2],q[3],q[4]);
	}
	return 0;
}