来自FallDream的博客，未经允许，请勿转载，谢谢

---

ditoly太强了 随便切  我被d飞了

-------------------------------

由n个数ai，每次询问，给定四个数a,b,c,d，求一个左端点在[a,b]，右端点在[c,d]的子序列(原题这么写，但是实际上是子串)，使得它的中位数最大。强制在线

n<=20000 q<=25000

题解：考虑二分一个答案，然后check一下是否能够取到。

怎么check呢？假设要check一个数X，那么我们把大等于X的数字看成1，小于的看成-1，如果存在一个子序列的和大等于0，那么这个数字就是合法的。

所以我们可以维护一棵线段树，直接把每一位看成1或者-1，维护前缀和数组的最大最小值，然后数字从小到大把线段树可持久化一下，每次一个数字从1变成-1就是把一段区间-2，这个我们通过标记永久化实现。

复杂度$qlog^{2}n$

#include
     
      #include
      
       #include
       
        #define MN 20000#define pa pair
        
         #define mp(x,y) make_pair(x,y)#define INF 2000000000using namespace std;inline int read(){    int x = 0 , f = 1; char ch = getchar();    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1;  ch = getchar();}    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}int n,m,last=0,num[10],a[MN+5],cnt=0,l[MN+5],rt[MN+5];pa p[MN+5];struct data{    int mx,mn;    data(int x=0):mx(x),mn(x){}    data(int x,int y):mx(x),mn(y){}    data operator*(const data&b){
   return data(max(mx,b.mx),min(mn,b.mn));}     data operator+(int y){
   return data(mx+y,mn+y);}};struct node{
   int l,r,val;data x;}T[MN*60+5];inline int mark(int x,int k){    int nx=++cnt;T[nx].l=T[x].l;T[nx].r=T[x].r;    T[nx].x=T[x].x+k;T[nx].val=T[x].val+k;        return nx;}void pushdown(int x){    T[x].l=mark(T[x].l,T[x].val);    T[x].r=mark(T[x].r,T[x].val);    T[x].val=0;}int ins(int x,int l,int r,int ad,int lt=0,int rt=n){    if(l==lt&&rt==r){
   return mark(x,ad);}    int nx=mark(x,0);pushdown(nx);    int mid=lt+rt>>1;    if(r<=mid)         T[nx].l=ins(T[nx].l,l,r,ad,lt,mid);    else if(l>mid)        T[nx].r=ins(T[nx].r,l,r,ad,mid+1,rt);    else         T[nx].l=ins(T[nx].l,l,mid,ad,lt,mid),T[nx].r=ins(T[nx].r,mid+1,r,ad,mid+1,rt);    T[nx].x=T[T[nx].l].x*T[T[nx].r].x;    return nx;}int build(int l,int r){    int x=++cnt,mid=l+r>>1;    if(l==r) {T[x].x=data(l);return x;}    T[x].l=build(l,mid);T[x].r=build(mid+1,r);    T[x].x=T[T[x].l].x*T[T[x].r].x;    return x;}data query(int x,int l,int r,int lt=0,int rt=n){    if(l==lt&&rt==r) return T[x].x;    int mid=lt+rt>>1;    if(r<=mid) return query(T[x].l,l,r,lt,mid)+T[x].val;    else if(l>mid) return query(T[x].r,l,r,mid+1,rt)+T[x].val;    else return query(T[x].l,l,mid,lt,mid)*query(T[x].r,mid+1,r,mid+1,rt)+T[x].val;}int main(){        n=read();    for(int i=1;i<=n;i++) a[i]=read();    for(int i=1;i<=n;i++) p[i]=mp(a[i],i);    sort(p+1,p+n+1);rt[1]=build(0,n);    for(int i=2;i<=n;i++)        rt[i]=ins(rt[i-1],p[i-1].second,n,-2);    m=read();    for(int i=1;i<=m;i++)    {        for(int j=1;j<=4;j++) num[j]=(read()+last)%n+1;        sort(num+1,num+5);        int a=num[1],b=num[2],c=num[3],d=num[4];        int L=1,R=n,mid,ans=0;        while(L<=R)        {            mid=L+R>>1;                if(query(rt[mid],c,d).mx-query(rt[mid],a-1,b-1).mn>=0) ans=mid,L=mid+1;            else R=mid-1;        }        printf("%d\n",last=p[ans].first);    }    return 0;}