(65 + 0 + 0 + 0 = 65pts)。
菜得起飞
(T1) 思维题，漏掉一个情况 + 打错一个情况
(T2) 模拟打挂
(T3) 博弈论白送的dp, (max)打成(min) , (70) to (0)
(T4) 主席树，没动
经验教训：
- 码力是真的差，2k的模拟都写不对.
- 小细节小错误太多.
- 写代码不一气呵成，思维不连贯.
前三题题解不动了，等T4写出来写题解
顺便 % cnyz 神 (rk1).
以后遇到自己不情愿写的题也得写.
T4题解
题目链接：middle，主席树好题
题意简述：
给定一个长度为(n)的序列(s)和(q)个询问，
每个询问包括(a,b,c,d)四个参数，求序列(s)中(l)~(r)中可能的最大中位数，强制在线。
其中(a) (leqslant) (l) (leqslant) (b)且 (c) (leqslant) (r) (leqslant) (d)。
题解
关于中位数有个二分答案的技巧，
二分一个值 (mid)，
大于等于(mid)的位置为(1)，否则为(-1)，
求一下最大子序和，便知道(mid)是否可以更大，
至此我们得到了一个做法：
对于每个询问，二分(mid)，(O(n))扫描得出最大子序和，
并且保证子序左右端点满足(a) (leqslant) (l) (leqslant) (b)且 (c) (leqslant) (r) (leqslant) (d).
时间复杂度(O(Qnlogn))，不能接受。
我们转换一下思路，用数据结构维护最大子序和，线段树可以做到。
我们先建好(n)棵线段树，这样查询复杂度降低到了(O(Qlog_2n))
但是空间复杂度过高，预建时间也过高。
我们自然的想到了专门为解决这两个问题而生的数据结构——可持久化线段树。
最终的做法：
- 先将每个(s_i)排序,然后从小到大建主席树，如何求最大子序和还有维护的信息参见这个。
(~~~~)为什么排序呢？
这样每一次建树才能继承上一次((-1)，(1)值只浮动一个). - 然后进行上述的二分做法
- 最大子序和求法：(b+1) 至 (c-1)之间必须选，(a) ~ (b)选最大后缀，(c)~(d)选最大前缀。
时间复杂度(O(NlogN+Qlog^2N)).
Code：
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
int n,m,a[N],rk[N],b[N],cnt;
int rt[N<<6],ls[N<<6],rs[N<<6];
int lmx[N<<6],rmx[N<<6],sum[N<<6];
bool cmp(int X,int Y){return a[X]<a[Y];}
void updata(int p){
sum[p]=sum[ls[p]]+sum[rs[p]];
lmx[p]=max(lmx[ls[p]],sum[ls[p]]+lmx[rs[p]]);
rmx[p]=max(rmx[rs[p]],sum[rs[p]]+rmx[ls[p]]);
}
int build(int l,int r){
int p=++cnt;
if(l==r){
sum[p]=lmx[p]=rmx[p]=1;
return p;
}
int mid=l+r>>1;
ls[p]=build(l,mid);
rs[p]=build(mid+1,r);
updata(p);
return p;
}
int copy(int x,int y){
ls[x]=ls[y];
rs[x]=rs[y];
sum[x]=sum[y];
lmx[x]=lmx[y];
rmx[x]=rmx[y];
}
int insert(int pre,int l,int r,int x,int val){
int p=++cnt;
copy(p,pre);
if(l==r){
lmx[p]=rmx[p]=-1;
sum[p]+=val;
return p;
}
int mid=l+r>>1;
if(x<=mid)ls[p]=insert(ls[pre],l,mid,x,val);
else rs[p]=insert(rs[pre],mid+1,r,x,val);
updata(p);
return p;
}
int querysum(int p,int l,int r,int x,int y){
if(x<=l&&y>=r)return sum[p];
int mid=l+r>>1,ret=0;
if(x<=mid)ret+=querysum(ls[p],l,mid,x,y);
if(y>mid)ret+=querysum(rs[p],mid+1,r,x,y);
return ret;
}
int querylmx(int p,int l,int r,int x,int y){
if(x<=l&&y>=r)return lmx[p];
int mid=l+r>>1,ret;
if(x<=mid&&!(y>mid))ret=querylmx(ls[p],l,mid,x,y);
if(!(x<=mid)&&y>mid)ret=querylmx(rs[p],mid+1,r,x,y);
if(x<=mid&&y>mid)ret=max(querylmx(ls[p],l,mid,x,mid),querysum(ls[p],l,mid,x,mid)+querylmx(rs[p],mid+1,r,mid+1,y));
return ret;
}
int queryrmx(int p,int l,int r,int x,int y){
if(x<=l&&y>=r)return rmx[p];
int mid=l+r>>1,ret;
if(x<=mid&&!(y>mid))ret=queryrmx(ls[p],l,mid,x,y);
if(!(x<=mid)&&y>mid)ret=queryrmx(rs[p],mid+1,r,x,y);
if(x<=mid&&y>mid)ret=max(queryrmx(rs[p],mid+1,r,mid+1,y),querysum(rs[p],mid+1,r,mid+1,y)+queryrmx(ls[p],l,mid,x,mid));
return ret;
}
bool check(int t,int a,int b,int c,int d){
int sum=0;
if(b+1<=c-1)sum+=querysum(rt[t],1,n,b+1,c-1);
sum+=queryrmx(rt[t],1,n,a,b);
sum+=querylmx(rt[t],1,n,c,d);
return sum>=0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
rk[i]=i;b[i]=a[i];
}
sort(b+1,b+n+1);
sort(rk+1,rk+n+1,cmp);
rt[1]=build(1,n);
for(int i=2;i<=n+1;i++)
rt[i]=insert(rt[i-1],1,n,rk[i-1],-2);
int T,Ans=0;
scanf("%d",&T);
while(T--){
int Q[4],A,B,C,D;
scanf("%d%d%d%d",&A,&B,&C,&D);
Q[0]=(A+Ans)%n;Q[1]=(B+Ans)%n;
Q[2]=(C+Ans)%n;Q[3]=(D+Ans)%n;
sort(Q,Q+4);
A=Q[0]+1;B=Q[1]+1;C=Q[2]+1;D=Q[3]+1;
int l=1,r=n;
while(l<=r){
int mid=l+r>>1;
if(check(mid,A,B,C,D))l=mid+1;
else r=mid-1;
}
Ans=b[r];
printf("%d
",Ans);
}
return 0;
}