求中位数的套路：二分，大于等于的设为1，小于的设为-1

于是可以从小到大排序后依次加入可持久化线段树，这样每次只会变化一个位置

那左右端点是区间怎么办？

先把中间的算上，然后维护每个区间左右两侧最大子段和，左右和右左拼起来即可

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 const int N=20005,M=1e7+70,inf=1e9;  6 int num[N],root[N],son[M][2],sum[M],lsum[M],rsum[M],qry[10];  7 int n,m,t1,t2,t3,t4,rd,tot,ans; pair
         
           mem[N];  8 void Pushup(int nde)  9 { 10     int ls=son[nde][0],rs=son[nde][1]; 11     sum[nde]=sum[ls]+sum[rs]; 12     lsum[nde]=max(lsum[ls],sum[ls]+lsum[rs]); 13     rsum[nde]=max(rsum[rs],sum[rs]+rsum[ls]); 14 } 15 int Pre(int l,int r) 16 { 17     int nde=++tot; 18     if(l==r) 19         sum[nde]=lsum[nde]=rsum[nde]=1; 20     else 21     { 22         int mid=(l+r)>>1; 23         son[nde][0]=Pre(l,mid); 24         son[nde][1]=Pre(mid+1,r); 25         Pushup(nde);  26     } 27     return nde; 28 } 29 int Insert(int pre,int l,int r,int pos,int tsk) 30 { 31     int nde=++tot; 32     son[nde][0]=son[pre][0]; 33     son[nde][1]=son[pre][1]; 34     if(l==r) 35         sum[nde]=lsum[nde]=rsum[nde]=tsk; 36     else 37     { 38         int mid=(l+r)>>1; 39         if(pos<=mid) son[nde][0]=Insert(son[pre][0],l,mid,pos,tsk); 40         else son[nde][1]=Insert(son[pre][1],mid+1,r,pos,tsk); Pushup(nde); 41     } 42     return nde; 43 } 44 int Query1(int nde,int l,int r,int ll,int rr) 45 { 46     if(l==ll&&r==rr) 47         return sum[nde]; 48     else 49     { 50         int mid=(l+r)>>1; 51         if(mid>=rr) return Query1(son[nde][0],l,mid,ll,rr); 52         else if(mid
          
           >1; 63         if(mid>=rr) return Query2(son[nde][0],l,mid,ll,rr); 64         else if(mid
           
            >1; 75 if(mid>=rr) return Query3(son[nde][0],l,mid,ll,rr); 76 else if(mid
            
             =0; 86 } 87 int main() 88 { 89 scanf("%d",&n); 90 for(int i=1;i<=n;i++) 91 scanf("%d",&num[i]),mem[i]=make_pair(num[i],i); 92 sort(mem+1,mem+1+n),root[1]=Pre(1,n); 93 for(int i=2;i<=n;i++) 94 root[i]=Insert(root[i-1],1,n,mem[i-1].second,-1); 95 scanf("%d",&m); 96 for(int i=1;i<=m;i++) 97 { 98 for(int j=1;j<=4;j++) 99 scanf("%d",&rd),qry[j]=(rd+ans)%n+1;100 sort(qry+1,qry+5);101 int l=1,r=n,lst=1;102 while(l<=r)103 {104 int mid=(l+r)>>1;105 if(Check(mid)) l=mid+1,lst=mid;106 else r=mid-1;107 }108 printf("%d\n",ans=mem[lst].first);109 }110 return 0;111 }