题目描述一个长度为 n 的序列 a设其排过序之后为 b其中位数定义为 bn/2其中 a,b 从 0 开始标号除法下取整。给你一个长度为 n 的序列 s。回答 Q 个这样的询问s 的左端点在 [a,b] 之间右端点在 [c,d] 之间的子区间中最大的中位数。其中 abcd。位置也从 0 开始标号。我会使用一些方式强制你在线。输入格式第一行序列长度 n。接下来 n 行按顺序给出 a 中的数。接下来一行 Q。然后 Q 行每行 a,b,c,d我们令上个询问的答案是 x如果这是第一个询问则 x0。令数组 q{(ax)modn,(bx)modn,(cx)modn,(dx)modn}。将 q 从小到大排序之后令真正的要询问的 aq0bq1cq2dq3。输入保证满足条件。输出格式Q 行依次给出询问的答案。输入输出样例输入 #1复制5 170337785 271451044 22430280 969056313 206452321 3 3 1 0 2 2 3 1 4 3 1 4 0输出 #1复制271451044 271451044 969056313说明/提示对于 5% 的数据n,Q≤100对于另 25% 的数据n≤2000对于 100% 的数据1≤n≤200001≤Q≤250001≤ai≤109。#includecstdio #includealgorithm #includevector using namespace std; #define lc(p) (seg[p].lc) #define rc(p) (seg[p].rc) #define sum(p) (seg[p].s) #define lmax(p) (seg[p].lm) #define rmax(p) (seg[p].rm) const int N20010; int n,m,tot,last,a,b,c,d;; int val[N],id[N],rt[N]; vectorintpos[N]; struct Seg { int lc,rc; int s,lm,rm; }seg[N*60]; inline bool cmp(int x,int y){return val[x]val[y];} inline void up(int p) { sum(p)sum(lc(p))sum(rc(p)); lmax(p)max(lmax(lc(p)),sum(lc(p))lmax(rc(p))); rmax(p)max(rmax(rc(p)),sum(rc(p))rmax(lc(p))); } void build(int p,int l,int r) { ptot; if(lr){sum(p)lmax(p)rmax(p)-1;return;} int mid(lr)1; build(lc(p),l,mid);build(rc(p),mid1,r); up(p); } void insert(int pre,int p,int L,int R,int pos) { if(!p)ptot; if(LR){sum(p)lmax(p)rmax(p)1;return;} int mid(LR)1; if(posmid)rc(p)rc(pre),insert(lc(pre),lc(p),L,mid,pos); else lc(p)lc(pre),insert(rc(pre),rc(p),mid1,R,pos); up(p); } Seg query(int p,int L,int R,int l,int r) { if(LlRr)return seg[p]; int mid(LR)1; if(lmid)return query(rc(p),mid1,R,l,r); else if(rmid)return query(lc(p),L,mid,l,r); else { Seg ans,lsonquery(lc(p),L,mid,l,r),rsonquery(rc(p),mid1,R,l,r); ans.s(lson.srson.s); ans.lmmax(lson.lm,lson.srson.lm); ans.rmmax(rson.rm,rson.slson.rm); return ans; } } inline bool check(int mid) { //printf(test::%d %d %d %d %d\n,a,b,c,d,id[mid]); int res0;Seg ans; ansquery(rt[mid],1,n,a,b);resans.rm; //printf(rmax::%d ,ans.rm); if(b1c-1)ansquery(rt[mid],1,n,b1,c-1),resans.s; ansquery(rt[mid],1,n,c,d);resans.lm; //printf(lmax::%d \n,ans.lm); return res0; } int main() { scanf(%d,n); for(int i1;in;i)scanf(%d,val[i]),id[i]i; sort(id1,idn1,cmp);//int cntunique(id1,idcnt1)-(id1); build(rt[n1],1,n); for(int in;i;i--)insert(rt[i1],rt[i],1,n,id[i]); scanf(%d,m); for(int i1;im;i) { scanf(%d%d%d%d,a,b,c,d); a(alast)%n1;b(blast)%n1; c(clast)%n1;d(dlast)%n1; int tmp[5]{0,a,b,c,d}; sort(tmp1,tmp41); atmp[1],btmp[2],ctmp[3],dtmp[4]; int l1,rn,ans; while(lr) { //puts(!!); int mid(lr)1; if(check(mid))ansmid,lmid1; else rmid-1; } printf(%d\n,lastval[id[ans]]); } return 0; }