洛谷题目链接
做法
首先，看到中位数就应该会想到一个经典做法，二分一个(mid)，把小于(mid)的数值为(-1)，大于(mid)的数值为(1)，如果这个区间的和(>=0)的话中位数可以更大，否则要更小
而题目中要求中位数最大，所以自然这个区间的和要越大越好，自然要多取(1)
我们知道([b,c])这个区间是肯定会取到的，所以只要求和，而([a,b-1],[c+1,d])这两个区间一个取最大后缀，一个取最大前缀，这样就保证了中位数最大
但是每二分一个(mid)就要重新把整个序列用(-1,1)代替，复杂度肯定承受不起，那怎么办呢，我们可以预处理每一个数做(mid)时，每一个区间最大前缀，最大后缀，区间和，用线段树来实现
但是对于每一个数开一棵线段树也是承受不起的，但是我们考虑到，如果我们按顺序来枚举(mid)的时候（先排序离散），(mid)这个位置的线段树，与(mid+1)这个位置的线段树唯一的区别，就是离散后在(mid)这个位置的数由(-1)变为了(1)，也就是说相邻两棵线段树之间可以共用很多部分
立刻想到主席树！
至于后缀前缀烂大街的操作就不讲了
下面是美滋滋的代码时间~~~
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 20007
using namespace std;
struct Tree
{
int lsum,rsum,sum,ls,rs;
}tr[N<<7];
int n,m,q,len,last,cnt;
int val1[N],val2[N],rt[N],qq[4];
vector<int> pos[N];
void Pushup(int x)
{
tr[x].lsum=max(tr[tr[x].ls].lsum,tr[tr[x].ls].sum+tr[tr[x].rs].lsum);
tr[x].rsum=max(tr[tr[x].rs].rsum,tr[tr[x].rs].sum+tr[tr[x].ls].rsum);
tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum;
}
void Update(int &x,int l,int r,int p,int v)
{
tr[++cnt]=tr[x];x=cnt;
if(l==r&&l==p)
{
tr[x].sum=v;
if(v>0)
tr[x].lsum=tr[x].rsum=v;
return;
}
if(p<l||p>r)
return;
int mid=l+((r-l)>>1);
Update(tr[x].ls,l,mid,p,v);
Update(tr[x].rs,mid+1,r,p,v);
Pushup(x);
//printf("ls:%d rs:%d
",tr[x].sum,tr[x].lsum);
}
int Ask_sum(int x,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr)
return tr[x].sum;
if(rr<l||ll>r)
return 0;
int mid=l+((r-l)>>1);
return Ask_sum(tr[x].ls,l,mid,ll,rr)+Ask_sum(tr[x].rs,mid+1,r,ll,rr);
}
int Ask_lsum(int x,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr)
return tr[x].lsum;
if(rr<l||ll>r)
return 0;
int mid=l+((r-l)>>1);
return max(Ask_lsum(tr[x].ls,l,mid,ll,rr),Ask_lsum(tr[x].rs,mid+1,r,ll,rr)+Ask_sum(tr[x].ls,l,mid,ll,rr));
}
int Ask_rsum(int x,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr)
return tr[x].rsum;
if(rr<l||ll>r)
return 0;
int mid=l+((r-l)>>1);
return max(Ask_rsum(tr[x].rs,mid+1,r,ll,rr),Ask_rsum(tr[x].ls,l,mid,ll,rr)+Ask_sum(tr[x].rs,mid+1,r,ll,rr));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&val1[i]),val2[i]=val1[i];
sort(val2+1,val2+n+1);
len=unique(val2+1,val2+1+n)-1-val2;
for(int i=1;i<=n;++i)
{
val1[i]=lower_bound(val2+1,val2+1+len,val1[i])-val2;
pos[val1[i]].push_back(i);
}
for(int i=1;i<=n;++i)
Update(rt[len+1],1,n,i,-1);
for(int i=len;i;--i)
{
rt[i]=rt[i+1];
for(int j=0;j<pos[i].size();++j)
Update(rt[i],1,n,pos[i][j],1);
}
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
qq[0]=(a+last)%n;qq[1]=(b+last)%n;qq[2]=(c+last)%n;qq[3]=(d+last)%n;
sort(qq,qq+4);
a=qq[0]+1;b=qq[1]+1;c=qq[2]+1;d=qq[3]+1;
//printf("%d %d %d %d
",a,b,c,d);
int l=1,r=len+1;
while(l+1<r)
{
int mid=l+((r-l)>>1);
int ans1,ans2,ans3;
ans1=Ask_sum(rt[mid],1,n,b,c);
ans2=Ask_rsum(rt[mid],1,n,a,b-1);
ans3=Ask_lsum(rt[mid],1,n,c+1,d);
//printf("%d %d %d
",ans1,ans2,ans3);
if(ans1+ans2+ans3>=0)
l=mid;
else
r=mid;
}
last=val2[l];
printf("%d
",last);
}
return 0;
}