一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。其中a<b<c<d。位置也从0开始标号。我会使用一些方式强制你在线。
\(n \leq 20000,Q \leq 25000\)
分析对多个区间取中位数的最大值，但是这些区间都包含一个相同的区间[b+1,c-1]。
可以将[b+1,c-1]区间先排序，再考虑往左右两边扩展。
对于左右两边扩展的数x，扩展后能否更优其实是由x与[b+1,c-1]中位数M的大小决定的。
考虑数列长度对中位数的影响。
奇数：中间的数
偶数：中间靠后的数
那么相当于x=M时也会可能对中位数的变大造成贡献。
因此将大于等于M的x看作1，小于M的x看作-1
如果能在两端找一段和>0，那么M就可能可以变大。
但是两端是分开的，如果要连起来需要考虑中间的部分。
如果中间的一部分也按类似考虑，那么就是检验M是否可行了。
然后须要用到中间[b+1,b-1]部分的和，[a,b]的最大后缀和，[c,d]的最大前缀和，用线段树可以很好解决。
可能出现的M最多只有N种，离散化。然后就可以对于每个M都预处理一遍这个正负1线段树。
但是不可能开N颗线段树。
发现M时候的情况从M-1转移，所需要改变的只有M-1的值。
于是用可持久化线段树就可以解决了。
时间复杂度\(O(N \log N+Q \log^2 N)\)
代码 #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<ctime> #include<iostream> #include<string> #include<vector> #include<list> #include<deque> #include<stack> #include<queue> #include<map> #include<set> #include<bitset> #include<algorithm> #include<complex> #pragma GCC optimize ("O0") using namespace std; template<class T> inline T read(T&x) { T data=0; int w=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') w=-1; ch=getchar(); } while(isdigit(ch)) data=10*data+ch-'0',ch=getchar(); return x=data*w; } typedef long long ll; const int INF=0x7fffffff; const int MAXN=2e4+7,MAXT=MAXN*20; // 16+4 int n; struct node { int v,p; bool operator<(const node&rhs)const { return v<rhs.v; } }a[MAXN]; // basz 0 to simplify querying int sz,root[MAXN]; struct PreSegTree { int L[MAXT],R[MAXT]; int sum[MAXT],pre[MAXT],suf[MAXT]; void pushup(int now) { sum[now]=sum[L[now]]+sum[R[now]]; pre[now]=max(pre[L[now]],sum[L[now]]+pre[R[now]]); suf[now]=max(suf[R[now]],sum[R[now]]+suf[L[now]]); } void build(int&now,int l,int r) { now=++sz; if(l==r) { sum[now]=pre[now]=suf[now]=1; return; } int mid=(l+r)>>1; build(L[now],l,mid); build(R[now],mid+1,r); pushup(now); } int qsum(int now,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) { return sum[now]; } int mid=(l+r)>>1,ans=0; if(ql<=mid) ans+=qsum(L[now],l,mid,ql,qr); if(qr>=mid+1) ans+=qsum(R[now],mid+1,r,ql,qr); return ans; } int qpre(int now,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) { return pre[now]; } int mid=(l+r)>>1; if(qr<=mid) return qpre(L[now],l,mid,ql,qr); if(ql>=mid+1) return qpre(R[now],mid+1,r,ql,qr); return max(qpre(L[now],l,mid,ql,qr),qsum(L[now],l,mid,ql,qr)+qpre(R[now],mid+1,r,ql,qr)); } int qsuf(int now,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) { return suf[now]; } int mid=(l+r)>>1; if(qr<=mid) return qsuf(L[now],l,mid,ql,qr); if(ql>=mid+1) return qsuf(R[now],mid+1,r,ql,qr); return max(qsuf(R[now],mid+1,r,ql,qr),qsum(R[now],mid+1,r,ql,qr)+qsuf(L[now],l,mid,ql,qr)); } void change(int&now,int l,int r,int p,int v) { ++sz; L[sz]=L[now],R[sz]=R[now]; now=sz; if(l==r) { sum[now]=pre[now]=suf[now]=v; return; } int mid=(l+r)>>1; if(p<=mid) change(L[now],l,mid,p,v); else change(R[now],mid+1,r,p,v); pushup(now); } }T; int q[4]; bool judge(int rt,int a,int b,int c,int d) { int res=0; if(b+1<=c-1) res+=T.qsum(rt,0,n-1,b+1,c-1); res+=T.qsuf(rt,0,n-1,a,b); res+=T.qpre(rt,0,n-1,c,d); return res>=0; } int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); read(n); for(int i=0;i<n;++i) { read(a[i].v); a[i].p=i; } sort(a,a+n); // 特殊离散化，后面二分答案的排名 T.build(root[0],0,n-1); for(int i=1;i<n;++i) { root[i]=root[i-1]; T.change(root[i],0,n-1,a[i-1].p,-1); // change the one 1 smaller than it } int Q,ans=0; read(Q); while(Q--) { read(q[0]);read(q[1]); read(q[2]);read(q[3]); (q[0]+=ans)%=n,(q[1]+=ans)%=n, (q[2]+=ans)%=n,(q[3]+=ans)%=n; sort(q,q+4); int l=0,r=n-1,x; while(l<=r) { int mid=(l+r)>>1; if(judge(root[mid],q[0],q[1],q[2],q[3])) x=mid,l=mid+1; else r=mid-1; } ans=a[x].v; printf("%d\n",ans); } // fclose(stdin); // fclose(stdout); return 0; }