题意
一个长度为 $n$ 的序列 $a$ , 设其升序排序之后为 $b$ , 其中位数定义为 $b[n/2]$, 其中 $a,b$ 从 $0$ 开始标号,除法取下整.
给你一个长度为 $n$ 的序列 $s$. 回答 $q$ 个这样的询问: $s$ 的左端点在 $[a,b]$ 之间,右端点在 $[c,d]$ 之间的子序列中, 最大的中位数. 其中 $a<b<c<d$. 位置也从 $0$ 开始标号.
$n\le 2\times 10^4,q\le2.5\times 10^4$.
强制在线.
题解
题里面最坑人的大概就是那个下取整又从 $0$ 开始标号了…相当于取第 $\left \lfloor \frac n 2 \right \rfloor+1$ 个值. 也就是说偶数的情况下取靠后的那个值作为中位数.
顺便在这题里了解了一些中位数处理的操作.
首先对于一个查询我们二分一个答案 $k$, 问题转化为能否有一个合乎询问的区间中位数不小于 $k$. 我们如果把原数列中满足 $x\ge k$ 的看作 $+1$, $x<k$ 的看作 $-1$, 那么只要有一个区间的和非负就可以满足条件.
那么我们可以用线段树来维护一下区间和以及最大前后缀和. $[b,c]$ 部分是必然要选的, 再加上 $[a,b-1]$ 的最大后缀和以及 $[c+1,d]$ 的最大前缀和即可.
至于这些线段树, 我们可以发现相邻的值对应的线段树差别不大, 只差了值相等的几个地方. 所以我们可以可持久化一下解决.
代码不难写.
参考代码
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
133
|
#include <bits/stdc++.h>
const int MAXN=20010;
struct Node{
struct Data{
int sum;
int lsum;
int rsum;
Data(){}
Data(int a,int b,int c):sum(a),lsum(b),rsum(c){}
Data friend operator+(const Data& a,const Data& b){
return Data(
a.sum+b.sum,
std::max(a.lsum,a.sum+b.lsum),
std::max(b.rsum,a.rsum+b.sum)
);
}
};
int l;
int r;
Data v;
Node* lch;
Node* rch;
Node(Node*);
void Print();
Node(int,int);
void Negate(int);
Data Query(int,int);
};
Node* N[MAXN];
int n;
int q;
int cnt;
int a[MAXN];
int s[MAXN];
std::vector<int> pos[MAXN];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",a+i);
s[i]=a[i];
}
std::sort(s+1,s+n+1);
cnt=std::unique(s+1,s+n+1)-(s+1);
for(int i=0;i<n;i++){
a[i]=std::lower_bound(s+1,s+cnt+1,a[i])-s;
pos[a[i]].push_back(i);
}
N[1]=new Node(0,n-1);
for(int i=1;i<cnt;i++){
N[i+1]=new Node(N[i]);
for(auto p:pos[i])
N[i+1]->Negate(p);
}
scanf("%d",&q);
int lastans=0;
for(int i=0;i<q;i++){
int q[4];
for(int i=0;i<4;i++){
scanf("%d",q+i);
(q[i]+=lastans)%=n;
}
std::sort(q,q+4);
int l=1,r=cnt+1;
while(r-l>1){
int mid=(l+r)>>1;
int sum=0;
if(q[2]-q[1]>1)
sum+=N[mid]->Query(q[1]+1,q[2]-1).sum;
sum+=N[mid]->Query(q[0],q[1]).rsum+N[mid]->Query(q[2],q[3]).lsum;
if(sum>=0)
l=mid;
else
r=mid;
}
printf("%d\n",lastans=s[l]);
}
return 0;
}
Node::Node(Node* p){
*this=*p;
}
Node::Data Node::Query(int l,int r){
if(l<=this->l&&this->r<=r)
return this->v;
else{
if(r<=this->lch->r)
return this->lch->Query(l,r);
if(this->rch->l<=l)
return this->rch->Query(l,r);
return this->lch->Query(l,r)+this->rch->Query(l,r);
}
}
void Node::Negate(int x){
if(this->l==this->r)
this->v=Data(-1,-1,-1);
else{
if(x<=this->lch->r){
this->lch=new Node(this->lch);
this->lch->Negate(x);
}
else{
this->rch=new Node(this->rch);
this->rch->Negate(x);
}
this->v=this->lch->v+this->rch->v;
}
}
void Node::Print(){
if(this==NULL)
return;
printf("[%d,%d] {sum=%d,lsum=%d,rsum=%d}\n",l,r,v.sum,v.lsum,v.rsum);
this->lch->Print();
this->rch->Print();
}
Node::Node(int l,int r):l(l),r(r){
if(l==r)
this->v=Data(1,1,1);
else{
int mid=(l+r)>>1;
this->lch=new Node(l,mid);
this->rch=new Node(mid+1,r);
this->v=this->lch->v+this->rch->v;
}
}
|
