「清北学堂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]$与此类似，不再赘述。

---

代码

#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;
}