2653: middle
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 2042 Solved: 1123
[Submit][Status][Discuss]
Description
一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个
长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
其中a<b<c<d。位置也从0开始标号。我会使用一些方式强制你在线。
Input
第一行序列长度n。接下来n行按顺序给出a中的数。
接下来一行Q。然后Q行每行a,b,c,d，我们令上个询问的答案是
x(如果这是第一个询问则x=0)。
令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。
将q从小到大排序之后，令真正的
要询问的a=q[0],b=q[1],c=q[2],d=q[3]。
输入保证满足条件。
第一行所谓“排过序”指的是从大到小排序！
Output
Q行依次给出询问的答案。
Sample Input
5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
271451044
271451044
969056313
Sample Output
HINT
0:n,Q<=100
1,...,5:n<=2000
0,...,19:n<=20000,Q<=25000
Source
我们二分中位数，对于大于mid的数赋值为1，小于mid的数为-1。若最大的区间和大于0则可行。
考虑建一颗主席树（维护权值线段树），root[i]为中位数为i时的前缀树。
二分查询即可。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn 20005
#define ls(i) t[i].s[0]
#define rs(i) t[i].s[1]
using namespace std;
int read() {
int x=,f=;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;
for(;isdigit(ch);ch=getchar()) x=x*+ch-'';
return x*f;
}
struct tmp {
int v,id;
bool operator <(const tmp tt) const {return v<tt.v;}
}a[maxn];
struct data {
int lm,rm,sum,s[];
}t[maxn*];
int n,q,sz;
int root[maxn];
void pushup(int x) {
t[x].lm=max(t[ls(x)].lm,t[ls(x)].sum+t[rs(x)].lm);
t[x].rm=max(t[rs(x)].rm,t[rs(x)].sum+t[ls(x)].rm);
t[x].sum=t[rs(x)].sum+t[ls(x)].sum;
}
void build(int &rt,int l,int r) {
rt=++sz;
if(l==r) {t[rt].sum=t[rt].lm=t[rt].rm=;return;}
int mid=l+r>>;
build(ls(rt),l,mid);build(rs(rt),mid+,r);
pushup(rt); }
void update(int p,int &rt,int l,int r,int x) {
rt=++sz;
t[rt]=t[p];
if(l==r) {t[rt].sum=-;t[rt].lm=t[rt].rm=;return;}
int mid=l+r>>;
if(x<=mid) update(ls(p),ls(rt),l,mid,x);
else update(rs(p),rs(rt),mid+,r,x);
pushup(rt);
}
int qs(int rt,int l,int r,int x,int y) {
if(x>y) return ;
if(l>=x&&r<=y) return t[rt].sum;
int mid=l+r>>,ans=;
if(x<=mid) ans+=qs(ls(rt),l,mid,x,y);
if(y>mid) ans+=qs(rs(rt),mid+,r,x,y);
return ans;
}
int ql(int rt,int l,int r,int x,int y) {
if(x>y) return ;
if(l>=x&&r<=y) return t[rt].lm;
int mid=l+r>>,ans=;
if(x<=mid) ans=max(ql(ls(rt),l,mid,x,y),ans);
if(y>mid) ans=max(qs(ls(rt),l,mid,x,mid)+ql(rs(rt),mid+,r,x,y),ans);
return ans;
}
int qr(int rt,int l,int r,int x,int y) {
if(x>y) return ;
if(l>=x&&r<=y) return t[rt].rm;
int mid=l+r>>,ans=;
if(x<=mid) ans=max(qs(rs(rt),mid+,r,mid+,y)+qr(ls(rt),l,mid,x,y),ans);
if(y>mid) ans=max(qr(rs(rt),mid+,r,x,y),ans);
return ans;
}
bool check(int x,int q1,int q2,int q3,int q4) {
int s=qs(root[x],,n-,q2,q3)+ql(root[x],,n-,q3+,q4)+qr(root[x],,n-,q1,q2-);
return s>=;
}
int main() {
t[].sum=t[].lm=t[].rm=;
n=read();
for(int i=;i<n;i++) a[i].v=read(),a[i].id=i;
sort(a,a+n);
build(root[],,n-);
for(int i=;i<n;i++) update(root[i-],root[i],,n-,a[i-].id);
int ans=;
q=read();
for(int i=;i<=q;i++) {
int ask[];
for(int j=;j<=;j++) ask[j]=(read()+ans)%n;
sort(ask+,ask+);
int L=,R=n-;
while(L<=R) {
int mid=L+R>>;
if(check(mid,ask[],ask[],ask[],ask[])) L=mid+;
else R=mid-;
}
ans=a[L-].v;
printf("%d\n",ans);
}
}