判断中位数是否可行需要将当前的解作为分界，大于其的置为1，小于为-1，然后b-c必选，ab，cd可不选，这个用线段树判定就好
但不能每次跑，所以套主席树，按权值排序，构建主席树，更新时将上一个节点改为-1，能保证以上结论
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 20005
using namespace std;
int lon[32*N],ron[32*N],sum[32*N],maxl[32*N],maxr[32*N];
int n,m,sz,num[N],num_cnt,root[N];
template<typename _t>
inline _t read(){
_t x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-f;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
struct data{
int val,id;
bool operator <(const data &a)const{return a.val>val;}
}d[N];
void print(int x,int l,int r){
if(!x)return ;
printf("%4d %4d %4d %4d l=%4d r=%4d %4d %4d\n",x,l,r,sum[x],maxl[x],maxr[x],lon[x],ron[x]);
int mid=(l+r)>>1;
print(lon[x],l,mid);
print(ron[x],mid+1,r);
}
void pushup(int rt){
maxl[rt]=max(maxl[lon[rt]],sum[lon[rt]]+maxl[ron[rt]]);
maxr[rt]=max(maxr[ron[rt]],sum[ron[rt]]+maxr[lon[rt]]);
sum[rt]=sum[lon[rt]]+sum[ron[rt]];
}
void build (int &rt,int l,int r){
rt=++sz;
if(l==r){sum[rt]=maxl[rt]=maxr[rt]=1;return;}
int mid=(l+r)>>1;
build(lon[rt],l,mid);
build(ron[rt],mid+1,r);
pushup(rt);
}
void insert(int p,int &rt,int l,int r,int x,int y){
rt=++sz;
lon[rt]=lon[p]; ron[rt]=ron[p];
if(l==r){sum[rt]=maxl[rt]=maxr[rt]=y;return;}
int mid=(l+r)>>1;
if(x<=mid) insert(lon[p],lon[rt],l,mid,x,y);
else insert(ron[p],ron[rt],mid+1,r,x,y);
pushup(rt);
}
int query(int rt,int l,int r,int x,int y){
if(l>=x&&r<=y) return sum[rt];
int ans=0;
int mid=(l+r)>>1;
if(x<=mid) ans+=query(lon[rt],l,mid,x,y);
if(y>mid) ans+=query(ron[rt],mid+1,r,x,y);
return ans;
}
int getmaxr(int rt,int l,int r,int x,int y){
if(l==x&&r==y) return maxr[rt];
int mid=(l+r)>>1,ans=0;
if(y<=mid) return getmaxr(lon[rt],l,mid,x,y);
if(x>mid) return getmaxr(ron[rt],mid+1,r,x,y);
else return max(getmaxr(ron[rt],mid+1,r,mid+1,y),getmaxr(lon[rt],l,mid,x,mid)+query(ron[rt],mid+1,r,mid+1,y));
}
int getmaxl(int rt,int l,int r,int x,int y){
if(l==x&&r==y) return maxl[rt];
int mid=(l+r)>>1,ans=0;
if(y<=mid) return getmaxl(lon[rt],l,mid,x,y);
if(x>mid) return getmaxl(ron[rt],mid+1,r,x,y);
else return max(getmaxl(lon[rt],l,mid,x,mid),query(lon[rt],l,mid,x,mid)+getmaxl(ron[rt],mid+1,r,mid+1,y));
}
bool judge(int x,int a,int b,int c,int d){
int ans=0;
if(c>b+1)ans+=query(root[x],1,n,b+1,c-1);
ans+=getmaxr(root[x],1,n,a,b);
ans+=getmaxl(root[x],1,n,c,d);
if(ans>=0) return 1;
return 0;
}
int gy()
{
freopen("nt2012_middle.in","r",stdin);
freopen("nt2012_middle.out","w",stdout);
n=read<int>();
for(int i=1;i<=n;i++){
d[i].val=read<int>();
num[i]=d[i].val;
d[i].id=i;
}
sort(num+1,num+n+1);
for(int i=1;i<=n;i++)
d[i].val=lower_bound(num+1,num+n+1,d[i].val)-num;
sort(d+1,d+n+1);
/*for(int i=1;i<=n;i++)
printf("%d %d\n",i,d[i].val);*/
build(root[1],1,n);
for(int i=2;i<=n;i++)
insert(root[i-1],root[i],1,n,d[i-1].id,-1);
/*for(int i=1;i<=n;i++){
printf("i=========%d\n",i);
print(root[i],1,n);
}*/
scanf("%d",&m);
int a[4];
int ans=0;
while(m--){
for(int i=0;i<4;i++){a[i]=read<int>();a[i]=(a[i]+ans)%n+1;}
sort(a,a+4);
int L=1,R=n,mid;
while(L+1<R){
mid=(L+R)>>1;
if(judge(mid,a[0],a[1],a[2],a[3])) L=mid;
else R=mid;
}
if(judge(R,a[0],a[1],a[2],a[3])) ans=num[R];
else ans=num[L];
printf("%d\n",ans);
}
return 0;
}
int ryf=gy();
int main(){;}
转播
