隐藏
「清北学堂1」摆摊 - 离线处理+线段树 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「清北学堂1」摆摊 - 离线处理+线段树

题目大意

给你一个长度为$m$的序列$a_1,a_2,\ldots,a_m$,每次给出一段区间$[L,R]$,表示$aL,a{L+1},\ldots,a_R$被占用,对于每一个询问,回答编号最小的连续两个空位。


题目分析

这道题好像可以用莫队水过去。
当然我们可以使用左端点排序,右端点用线段树维护。
具体方法如下:
首先将两个点映射为一段区间,如果两个点都是空位,那么就压缩为一个点放进线段树维护。
对于每一个询问按照左端点排序,那么我们将答案维护在线段树中右端点的位置处。
接着我们考虑当前的Left向右移动。

如图,这可能导致新增两个满足题目要求的位置。

以空出$a[Left-1],a[Left]$为例:

若Left-1所在$a$序列的位置比$Left$靠前,那么当$Left$位置空出时,$Left-1$的位置必定已经空出,那么只需将右端点在$[Left+1,m]$中的询问答案与$a[Left]-1$取min即可。
若Left-1所在$a$序列的位置比$Left$靠后,那么当$Left$位置空出时,$Left-1$的位置还未空出,那么只要覆盖了$Left-1$的询问都无法更新答案,故对右端点在$[Left+1,pos[a[Left]-1]-1$中的询问答案与$a[Left]-1$取min即可。
空出$a[Left],a[Left+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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#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=200005;
struct Tree {
int left,right,min;
Tree(int l=0,int r=0,int v=0x7fffffff/2):left(l),right(r),min(v) {}
};
struct Segment_Tree {
Tree tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right,int* a) {
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index].min=a[Left];
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid,a);
build(rs,mid+1,Right,a);
}
void push_down(int index) {
tree[ls].min=min(tree[ls].min,tree[index].min);
tree[rs].min=min(tree[rs].min,tree[index].min);
}
void modify(int index,int Left,int Right,int val) {
if(Left>tree[index].right||Right<tree[index].left)return;
if(Left<=tree[index].left&&Right>=tree[index].right) {
tree[index].min=min(tree[index].min,val);
return;
}
push_down(index);
modify(ls,Left,Right,val);
modify(rs,Left,Right,val);
}
int query(int index,int target) {
if(target>tree[index].right||target<tree[index].left)return 0x7fffffff/2;
push_down(index);
if(tree[index].left==tree[index].right)return tree[index].min;
return min(query(ls,target),query(rs,target));
}
} st;
struct Ask {
int left,right,pos;
bool operator < (const Ask& b) const {
return left<b.left||(left==b.left&&right<b.right);
}
} Q[maxn];
int n,m,q,a[maxn],Hash[maxn],First[maxn],Last[maxn],M[maxn],tmp[maxn],ans[maxn];
int main() {
n=Get_Int();
m=Get_Int();
q=Get_Int();
for(int i=1; i<=m; i++)a[i]=Get_Int(),M[a[i]]=i;
int j=1;
for(int i=1; i<=m; i++) {
Hash[a[i]]=Hash[a[i]-1]=1;
while(j<=n-1&&Hash[j])j++;
if(j<=n-1)tmp[i]=j;
else tmp[i]=0x7fffffff/2;
}
for(int i=1; i<=q; i++) {
Q[i].left=Get_Int();
Q[i].right=Get_Int();
Q[i].pos=i;
}
sort(Q+1,Q+q+1);
st.build(1,1,n,tmp);
int now=1;
for(int i=1; i<=m; i++) {
while(now<=q&&Q[now].left==i) {
ans[Q[now].pos]=st.query(1,Q[now].right);
now++;
}
if(a[i]>1) {
if(M[a[i]-1]>=i+1)st.modify(1,i+1,M[a[i]-1]-1,a[i]-1);
else st.modify(1,i+1,m,a[i]-1);
}
if(a[i]<n) {
if(M[a[i]+1]>=i+1)st.modify(1,i+1,M[a[i]+1]-1,a[i]);
else st.modify(1,i+1,m,a[i]);
}
}
for(int i=1; i<=q; i++) {
if(ans[i]==0x7fffffff/2)puts("-1 -1");
else printf("%d %d\n",ans[i],ans[i]+1);
}
return 0;
}
姥爷们赏瓶冰阔落吧~