BZOJ2653 middle 【二分 + 主席树】

题目

一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/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)%n,(b+x)%n,(c+x)%n,(d+x)%n}。

将q从小到大排序之后,令真正的

要询问的a=q[0],b=q[1],c=q[2],d=q[3]。  

输入保证满足条件。

第一行所谓“排过序”指的是从大到小排序!

输出格式

Q行依次给出询问的答案。

输入样例

5

170337785

271451044

22430280

969056313

206452321

3

3 1 0 2

2 3 1 4

3 1 4 0

输出样例

271451044

271451044

969056313

提示

  0:n,Q<=100

1,...,5:n<=2000

0,...,19:n<=20000,Q<=25000

题解

首先我们理解一下题意:

从0开始的序列降序排序,取b[n / 2]向下取整为中位数,实际上就是一个往大取的中位数

比如说有偶数个【比如6个】,那么中位数就是第3大而不是第4大

奇数个自然就是取中位数,这些模拟一下就可以推出

怎么求?

假设我们指定一个数x,将大于等于x的设为1,小于x的设为-1

如果一个区间和非负,那么这个区间的中位数至少为x,因为比x大的个数不少于比x小的个数

可以发现这样的x具有单调性,可以二分x

所以我们只要二分x,检验选取左右端点能取出的最大区间和是否非负

现在问题就转化成了:

对每个x,建立一个1,-1序列,并求出最大区间和

当x增大时序列只会有一个元素改变,而又需要维护动态信息

很自然可以想到主席树

所以我们将原序列排个序,按顺序建树,二分 + 主席树就可以解决了

检验左区间最大后缀和 + 中间区间和 + 右区间最大前缀和 是否非负,如果是就可行

否则偏大

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
using namespace std;
const int maxn = 20005,maxm = 3000005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}
return out * flag;
}
int ms[maxm],ml[maxm],mr[maxm],sum[maxm],ls[maxm],rs[maxm],cnt,rt[maxn];
int id[maxn],A[maxn],tot = 1,n,Q,q[6],lans;
inline bool cmp(const int& a,const int& b){return A[a] < A[b];}
void copy(int u,int pre){
ms[u] = ms[pre]; ml[u] = ml[pre]; mr[u] = mr[pre];
ls[u] = ls[pre]; rs[u] = rs[pre]; sum[u] = sum[pre];
}
void upd(int u){
sum[u] = sum[ls[u]] + sum[rs[u]];
ms[u] = max(max(ms[ls[u]],ms[rs[u]]),mr[ls[u]] + ml[rs[u]]);
ml[u] = max(ml[ls[u]],sum[ls[u]] + ml[rs[u]]);
mr[u] = max(mr[rs[u]],sum[rs[u]] + mr[ls[u]]);
}
void build(int& u,int l,int r){
u = ++cnt;
if (l == r){
sum[u] = ms[u] = ml[u] = mr[u] = 1;
return;
}
int mid = l + r >> 1;
build(ls[u],l,mid);
build(rs[u],mid + 1,r);
upd(u);
}
void modify(int& u,int pre,int l,int r,int pos,int v){
u = ++cnt; copy(u,pre);
if (l == r){sum[u] = v; ms[u] = ml[u] = mr[u] = v; return;}
int mid = l + r >> 1;
if (mid >= pos) modify(ls[u],ls[pre],l,mid,pos,v);
else modify(rs[u],rs[pre],mid + 1,r,pos,v);
upd(u);
}
struct node{int l,r,s,v;};
node query(int u,int l,int r,int L,int R){
if (l >= L && r <= R) return (node){ml[u],mr[u],ms[u],sum[u]};
int mid = l + r >> 1;
if (mid >= R) return query(ls[u],l,mid,L,R);
else if (mid < L) return query(rs[u],mid + 1,r,L,R);
else {
node a = query(ls[u],l,mid,L,R),b = query(rs[u],mid + 1,r,L,R);
return (node){max(a.l,a.v + b.l),max(b.r,b.v + a.r),
max(max(a.s,b.s),a.r + b.l),a.v + b.v};
}
}
void solve(int x,int y,int xx,int yy){
int l = 1,r = n,mid,t;
while (l < r){
mid = l + r + 1 >> 1;
t = query(rt[mid],1,n,x,y).r
+ (y + 1 <= xx - 1 ? query(rt[mid],1,n,y + 1,xx - 1).v : 0)
+ query(rt[mid],1,n,xx,yy).l;
if (t >= 0) l = mid;
else r = mid - 1;
}
printf("%d\n",lans = A[id[l]]);
}
int main(){
n = read();
REP(i,n) A[i] = read(),id[i] = i;
sort(id + 1,id + 1 + n,cmp);
build(rt[0],1,n);
for (int i = 1; i <= n; i++){
rt[i] = rt[i - 1];
if (i > 1) modify(rt[i],rt[i],1,n,id[i - 1],-1);
}
Q = read();
while (Q--){
for (int i = 0; i < 4; i++) q[i] = (read() + lans) % n;
sort(q,q + 4);
solve(q[0] + 1,q[1] + 1,q[2] + 1,q[3] + 1);
}
return 0;
}
上一篇:【BZOJ2653】middle(主席树,二分)


下一篇:【洛谷2839/BZOJ2653】middle(主席树)