一个长度为 n 的序列 a,设其升序排序之后为 b,那么序列 a 的中位数定义为 b_{\lfloor\frac{n}{2}\rfloor},其中 a,b 从 0 开始标号,除法取下整。
给你一个长度为 n 的序列 s。回答 Q 个这样的询问:s 的左端点在 [a,b] 之间,右端点在 [c,d] 之间的子序列中,最大的中位数。
其中 a<b<c<d0 开始标号。
强制在线。
1\leq n \leq 20000,1\leq Q\leq 25000。
首先对于每个询问,我们可以先二分答案。
考虑二分答案 mid 如何 check。
如果我们将序列中的所有小于 mid 的数字都标记为 -1,所有大于等于 mid 的数字都标记为 1,那么我们只需要查询是否存在合法的一个区间内的和大于等于 0 即可。
那么我们只需要先预处理建出选择所有 mid 的值域线段树,这样每次相邻两个权值实际上只改变了几个位置,所以主席树即可,维护以下几个值:
那么合法的区间的最大值就是 \max_{i=a}^{b+1}\sum_{i}^{b}+\sum_{b+1}^{c-1}{p_i}+\max_{i=c-1}^{d}\sum_{c}^{i}。
用线段树维护即 Rmax(a,b)+Sum(b+1,c-1)+Lmax(c,d)。
所以我们只需要维护一下主席树即可。
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e4,M=N+5e3;
int n,q,t[5],rt[N];
struct seq{int v,pos;}a[N];
I bool cmp(Cn seq& x,Cn seq& y){return x.v<y.v;}
class PresidentTree{
private:
int cnt;
struct node{int l,r,S,L,R;}T[N*30];
#define mid (l+r>>1)
#define ls T[x].l,l,mid
#define rs T[x].r,mid+1,r
#define PU(x) (T[x].S=T[T[x].l].S+T[T[x].r].S,T[x].L=max(T[T[x].l].L,T[T[x].l].S+T[T[x].r].L),T[x].R=max(T[T[x].r].R,T[T[x].r].S+T[T[x].l].R))
I int QS(CI x,CI l,CI r,CI L,CI R){
if(L<=l&&r<=R) return T[x].S;
RI S=0;return L<=mid&&(S+=QS(ls,L,R)),R>mid&&(S+=QS(rs,L,R)),S;
}
I int QL(CI x,CI l,CI r,CI L,CI R){
if(L<=l&&r<=R) return T[x].L;
if(R<=mid) return QL(ls,L,R);else if(L>mid) return QL(rs,L,R);
else return max(QL(ls,L,mid),QS(ls,L,mid)+QL(rs,mid+1,R));//前缀最大值
}
I int QR(CI x,CI l,CI r,CI L,CI R){
if(L<=l&&r<=R) return T[x].R;
if(R<=mid) return QR(ls,L,R);else if(L>mid) return QR(rs,L,R);
else return max(QR(rs,mid+1,R),QS(rs,mid+1,R)+QR(ls,L,mid));//后缀最大值
}
public:
I void B(int& x,CI l,CI r){
x=++cnt;T[x].S=T[x].L=T[x].R=r-l+1;if(l==r) return ;
B(ls),B(rs);
}
I void U(CI pre,int& x,CI l,CI r,CI p,CI v){
T[x=++cnt]=T[pre];if(l==r) return void(T[x].S=T[x].L=T[x].R=v);
p<=mid?U(T[pre].l,ls,p,v):U(T[pre].r,rs,p,v),PU(x);
}
I int check(CI k,CI a,CI b,CI c,CI d){
RI S=0;if(b+1<=c-1) S+=QS(rt[k],1,n,b+1,c-1);//查询[b+1,c-1]的和,注意特判区间不存在的情况
S+=QR(rt[k],1,n,a,b)+QL(rt[k],1,n,c,d);return S>=0;//如果大于等于0即合法
}
}S;
int main(){
RI i,j,l,r,p=0;for(read(n),i=1;i<=n;i++) read(a[i].v),a[i].pos=i;sort(a+1,a+n+1,cmp);
for(S.B(rt[1],1,n),i=2;i<=n+1;i++) S.U(rt[i-1],rt[i],1,n,a[i-1].pos,-1);for(read(q),i=1;i<=q;i++){//预处理,建树
for(j=0;j<4;j++) read(t[j]),t[j]+=p,t[j]%=n,t[j]++;
sort(t,t+4);l=0,r=n;W(l<=r) S.check(mid,t[0],t[1],t[2],t[3])?(p=mid,l=mid+1):r=mid-1;writeln(p=a[p].v);
}return 0;
}