「国家集训队」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;
}