《P2839 [国家集训队] middle》

题目描述

一个长度为 n 的序列 a，设其排过序之后为 b，其中位数定义为 bn/2​，其中 a,b 从 0 开始标号，除法下取整。

给你一个长度为 n 的序列 s。

回答 Q 个这样的询问：s 的左端点在 [a,b] 之间，右端点在 [c,d] 之间的子区间中，最大的中位数。

其中 a<b<c<d。

位置也从 0 开始标号。

我会使用一些方式强制你在线。

输入格式

第一行序列长度 n。

接下来 n 行按顺序给出 a 中的数。

接下来一行 Q。

然后 Q 行每行 a,b,c,d，我们令上个询问的答案是 x（如果这是第一个询问则 x=0）。

令数组 q={(a+x)modn,(b+x)modn,(c+x)modn,(d+x)modn}。

将 q 从小到大排序之后，令真正的要询问的 a=q0​，b=q1​，c=q2​，d=q3​。

输入保证满足条件。

输出格式

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≤20000，1≤Q≤25000，1≤ai​≤109。

#include<cstdio> #include<algorithm> #include<vector> 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 N=20010; int n,m,tot,last,a,b,c,d;; int val[N],id[N],rt[N]; vector<int>pos[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) { p=++tot; if(l==r){sum(p)=lmax(p)=rmax(p)=-1;return;} int mid=(l+r)>>1; build(lc(p),l,mid);build(rc(p),mid+1,r); up(p); } void insert(int pre,int &p,int L,int R,int pos) { if(!p)p=++tot; if(L==R){sum(p)=lmax(p)=rmax(p)=1;return;} int mid=(L+R)>>1; if(pos<=mid)rc(p)=rc(pre),insert(lc(pre),lc(p),L,mid,pos); else lc(p)=lc(pre),insert(rc(pre),rc(p),mid+1,R,pos); up(p); } Seg query(int p,int L,int R,int l,int r) { if(L>=l&&R<=r)return seg[p]; int mid=(L+R)>>1; if(l>mid)return query(rc(p),mid+1,R,l,r); else if(r<=mid)return query(lc(p),L,mid,l,r); else { Seg ans,lson=query(lc(p),L,mid,l,r),rson=query(rc(p),mid+1,R,l,r); ans.s=(lson.s+rson.s); ans.lm=max(lson.lm,lson.s+rson.lm); ans.rm=max(rson.rm,rson.s+lson.rm); return ans; } } inline bool check(int mid) { //printf("test::%d %d %d %d %d\n",a,b,c,d,id[mid]); int res=0;Seg ans; ans=query(rt[mid],1,n,a,b);res+=ans.rm; //printf("rmax::%d ",ans.rm); if(b+1<=c-1)ans=query(rt[mid],1,n,b+1,c-1),res+=ans.s; ans=query(rt[mid],1,n,c,d);res+=ans.lm; //printf("lmax::%d \n",ans.lm); return res>=0; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&val[i]),id[i]=i; sort(id+1,id+n+1,cmp);//int cnt=unique(id+1,id+cnt+1)-(id+1); build(rt[n+1],1,n); for(int i=n;i;i--)insert(rt[i+1],rt[i],1,n,id[i]); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); a=(a+last)%n+1;b=(b+last)%n+1; c=(c+last)%n+1;d=(d+last)%n+1; int tmp[5]={0,a,b,c,d}; sort(tmp+1,tmp+4+1); a=tmp[1],b=tmp[2],c=tmp[3],d=tmp[4]; int l=1,r=n,ans; while(l<=r) { //puts("!!"); int mid=(l+r)>>1; if(check(mid))ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",last=val[id[ans]]); } return 0; }