「bzoj2653」middle(陈立杰) - 二分+主席树 | Bill Yang's Blog
0%

「bzoj2653」middle(陈立杰) - 二分+主席树

题目大意

    一个长度为$n$的序列$a$,设其排过序之后为$b$,其中位数定义为$b[n/2]$,其中$a,b$从$0$开始标号,除法取下整。
    给你一个长度为$n$的序列$s$。
    回答$Q$个这样的询问:$s$的左端点在$[a,b]$之间,右端点在$[c,d]$之间的子序列中,最大的中位数。
    其中$a\lt b\lt c\lt d$。
    位置也从$0$开始标号。
    我会使用一些方式强制你在线。


题目分析

对于一个询问$(a,b,c,d)$,显然$[b+1,c-1]$是必选区间,现在我们要尽量得添加较大的数使得答案变大。

不妨假设答案为$p$,若我们统计出有$num_1$个数比$p$小,有$num_2$个数比$p$大,若$num_1\ge num_2$,则说明答案$p$可以变大,否则需要变小。

那么现在问题转化为了,对于一个数$v$,在区间$[a,b]$求出最大的右区间$[l,b]$,满足$num_1-num_2$尽量地大,对$[c,d]$则要求左区间。

不妨将比数$v$大的记为$+1$,比$v$小的记为$-1$,则我们仅需要求出$[a,b]$的靠右最大子段和与$[c,d]$的靠左最大子段和。

对这些$+1,-1$位置建立线段树,那么我们就可以方便地统计出最大子段和了,目前的问题是如何快速、省空间地对每一个数都建立线段树。

注意到仅有$n$个数,每个数的$+1,-1$标记只可能从比其小的数所建立的线段树上更改一处,因此我们可以使用可持久化线段树维护。

对位置建立按数可持久化的线段树,每次询问二分猜测答案,并用对应的线段树验证即可。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=20005;

struct Tree {
int l,r;
int sum,lmax,rmax;
};

struct President_Tree {
Tree tree[maxn*50];
int size;
#define lm(x) tree[x].lmax
#define rm(x) tree[x].rmax
#define sum(x) tree[x].sum
void push_up(int index) {
int l=tree[index].l,r=tree[index].r;
sum(index)=sum(l)+sum(r);
lm(index)=max(lm(l),sum(l)+lm(r));
rm(index)=max(rm(r),rm(l)+sum(r));
}
int build(int Left,int Right) {
int now=++size;
if(Left==Right) {
sum(now)=lm(now)=rm(now)=1;
return now;
}
int mid=(Left+Right)>>1;
tree[now].l=build(Left,mid);
tree[now].r=build(mid+1,Right);
push_up(now);
return now;
}
int insert(int Left,int Right,int pre,int v) {
int now=++size;
tree[now]=tree[pre];
if(Left==Right) {
sum(now)=lm(now)=rm(now)=-1;
return now;
}
int mid=(Left+Right)>>1;
if(v<=mid)tree[now].l=insert(Left,mid,tree[pre].l,v);
else tree[now].r=insert(mid+1,Right,tree[pre].r,v);
push_up(now);
return now;
}
int query_sum(int root,int Left,int Right,int left,int right) {
if(right<Left||left>Right)return 0;
if(left<=Left&&right>=Right)return sum(root);
int mid=(Left+Right)>>1;
return query_sum(tree[root].l,Left,mid,left,right)+query_sum(tree[root].r,mid+1,Right,left,right);
}
int query_left(int root,int Left,int Right,int left,int right) {
if(right<Left||left>Right)return -INT_MAX/2;
if(left<=Left&&right>=Right)return lm(root);
int mid=(Left+Right)>>1;
return max(query_left(tree[root].l,Left,mid,left,right),query_sum(tree[root].l,Left,mid,left,right)+query_left(tree[root].r,mid+1,Right,left,right));
}
int query_right(int root,int Left,int Right,int left,int right) {
if(right<Left||left>Right)return -INT_MAX/2;
if(left<=Left&&right>=Right)return rm(root);
int mid=(Left+Right)>>1;
return max(query_right(tree[root].r,mid+1,Right,left,right),query_sum(tree[root].r,mid+1,Right,left,right)+query_right(tree[root].l,Left,mid,left,right));
}
} pt;

int n,q,root[maxn],lastans;

struct node {
int v,pos;
bool operator < (const node& b) const {
return v<b.v;
}
} a[maxn];

bool Check(int v,int a,int b,int c,int d) {
int ans=0;
if(c-b>1)ans=pt.query_sum(root[v],1,n,b+1,c-1);
ans+=pt.query_right(root[v],1,n,a,b)+pt.query_left(root[v],1,n,c,d);
return ans>=0;
}

int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i].v=Get_Int();
a[i].pos=i;
}
sort(a+1,a+n+1);
root[1]=pt.build(1,n);
for(int i=2; i<=n; i++)root[i]=pt.insert(1,n,root[i-1],a[i-1].pos);
q=Get_Int();
while(q--) {
int tmp[4];
tmp[0]=Get_Int(),tmp[1]=Get_Int(),tmp[2]=Get_Int(),tmp[3]=Get_Int();
for(int i=0; i<4; i++)tmp[i]=(tmp[i]+lastans)%n+1;
sort(tmp,tmp+4);
int Left=1,Right=n;
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(Check(mid,tmp[0],tmp[1],tmp[2],tmp[3]))Left=mid+1;
else Right=mid-1;
}
lastans=a[Right].v;
printf("%d\n",lastans);
}
return 0;
}
姥爷们赏瓶冰阔落吧~