[bzoj3585]-mex

发布于 2018-02-27  27 次阅读



题目(BZOJ) *权限
 
主席树裸题......
貌似莫队也可以过?

#include <bits/stdc++.h>
using namespace std;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=200050;
int n,m;
int a[N];
int ls[N*30],rs[N*30],rt[N],mn[N*30],tsz;
inline void pushup(int x){mn[x]=min(mn[ls[x]],mn[rs[x]]);}
void insert(int l,int r,int x,int &y,int pos,int v){
	y=++tsz;mn[y]=mn[x];
	if(l==r){mn[y]=v;return;}
	int mid=(l+r)>>1;
	if(pos<=mid)rs[y]=rs[x],insert(l,mid,ls[x],ls[y],pos,v);
	else ls[y]=ls[x],insert(mid+1,r,rs[x],rs[y],pos,v);
	pushup(y);
}
int query(int l,int r,int x,int pos){
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(mn[ls[x]]<pos)return query(l,mid,ls[x],pos);
	else return query(mid+1,r,rs[x],pos);
}
int pos[N];
int main(){
	read(n),read(m);
	for(int i=1;i<=n;++i){
		int x;read(x);
		insert(0,200000,rt[i-1],rt[i],x,i);
	}
	while(m--){
		int l,r;read(l),read(r);
		int ans=query(0,200000,rt[r],l);
		printf(
	}
	return 0;
}