一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。
给你一个长度为n的序列s。
回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
其中a<b<c<d。
位置也从0开始标号。
我会使用一些方式强制你在线。
Q行依次给出询问的答案。
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 20010
#define MAX 999999999
using namespace std;
int n,m;
int val[MAXN],id[MAXN];
int size=0,root[MAXN];
struct Chairman_Tree{
int lsum,rsum,sum,lson,rson;
Chairman_Tree(){
lsum=rsum=-MAX;
sum=0;
}
friend Chairman_Tree operator +(const Chairman_Tree p,const Chairman_Tree q){
Chairman_Tree x;
x.lsum=max(p.lsum,p.sum+q.lsum);
x.rsum=max(q.rsum,p.rsum+q.sum);
x.sum=p.sum+q.sum;
return x;
}
}a[MAXN*22];
inline int read(){
int date=0,w=1;char c=0;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
return date*w;
}
inline bool cmp(const int &p,const int &q){
return val[p]<val[q];
}
inline void pushup(int rt){
a[rt].lsum=max(a[a[rt].lson].lsum,a[a[rt].lson].sum+a[a[rt].rson].lsum);
a[rt].rsum=max(a[a[rt].rson].rsum,a[a[rt].lson].rsum+a[a[rt].rson].sum);
a[rt].sum=a[a[rt].lson].sum+a[a[rt].rson].sum;
}
int buildtree(int l,int r){
int rt=++size;
if(l==r){
a[rt].sum=a[rt].lsum=a[rt].rsum=r-l+1;
return rt;
}
int mid=l+r>>1;
a[rt].lson=buildtree(l,mid);
a[rt].rson=buildtree(mid+1,r);
pushup(rt);
return rt;
}
void insert(int k,int l,int r,int &rt){
a[++size]=a[rt];rt=size;
if(l==r){
a[rt].sum=a[rt].lsum=a[rt].rsum=-1;
return;
}
int mid=l+r>>1;
if(k<=mid)insert(k,l,mid,a[rt].lson);
else insert(k,mid+1,r,a[rt].rson);
pushup(rt);
}
Chairman_Tree query(int lside,int rside,int l,int r,int rt){
if(lside<=l&&r<=rside)return a[rt];
int mid=l+r>>1;
Chairman_Tree lson,rson;
if(lside<=mid)lson=query(lside,rside,l,mid,a[rt].lson);
if(mid<rside)rson=query(lside,rside,mid+1,r,a[rt].rson);
return (lson+rson);
}
inline bool check(int l1,int r1,int l2,int r2,int x){
int s=0;
Chairman_Tree ans;
if(r1+1<=l2-1){
ans=query(r1+1,l2-1,1,n,root[x]);
s+=ans.sum;
}
ans=query(l1,r1,1,n,root[x]);
s+=ans.rsum;
ans=query(l2,r2,1,n,root[x]);
s+=ans.lsum;
return (s>=0);
}
int solve(int l1,int r1,int l2,int r2){
int l=1,r=n,ans;
while(l<=r){
int mid=l+r>>1;
if(check(l1,r1,l2,r2,mid)){
ans=val[id[mid]];
l=mid+1;
}
else r=mid-1;
}
return ans;
}
void work(){
int l1,r1,l2,r2,last=0,q[4];
while(m--){
for(int i=0;i<4;i++)q[i]=(read()+last)%n;
sort(q,q+4);
l1=q[0]+1;r1=q[1]+1;l2=q[2]+1;r2=q[3]+1;
last=solve(l1,r1,l2,r2);
printf("%d\n",last);
}
}
void init(){
n=read();
for(int i=1;i<=n;i++){
val[i]=read();
id[i]=i;
}
sort(id+1,id+n+1,cmp);
root[1]=buildtree(1,n);
for(int i=2;i<=n;i++){
root[i]=root[i-1];
insert(id[i-1],1,n,root[i]);
}
m=read();
}
int main(){
init();
work();
return 0;
}
原文：https://www.cnblogs.com/Yangrui-Blog/p/10632109.html