BZOJ 3585 mex 莫隊算法+分塊

BZOJ 3585 mex 莫隊算法+分塊

題目大意：給定一個長度為n的數組，m次詢問某個區間內的mex值

怒寫莫隊233

將權值分成√n塊，記錄每個權值的出現次數以及每塊內有多少權值出現過

修改O(1)即可完成 查詢時首先掃一遍找到第一個塊內有沒有覆蓋的點的塊 然後在塊內暴力查找 時間復雜度O(√n)

套個莫隊 總時間復雜度O(m√n)

#include 
#include 
#include 
#include 
#include 
#define M 200200
using namespace std;
struct abcd{
	int l,r,id;
	bool operator < (const abcd &x) const;
}queries[M];
int n,m,b;
int a[M],belong[M],l[M],r[M];
int L=1,R=0,f[M],block_ans[M],ans[M];
bool abcd :: operator < (const abcd &x) const
{
	if(belong[l]!=belong[x.l])
		return ln) return ;
	if(!f[x]++)
		block_ans[belong[x]]++;
}
void Downdate(int x)
{
	if(x>n) return ;
	if(!--f[x])
		block_ans[belong[x]]--;
}
int Query()
{
	int i;
	if(!f[0]) return 0;
	for(i=1;l[i];i++)
		if(block_ans[i]!=r[i]-l[i]+1)
			break;
	int temp=i;
	for(i=l[temp];i<=r[temp];i++)
		if(!f[i])
			return i;
	return n;
}
int main()
{
	int i;
	cin>>n>>m;
	b=int(sqrt(n)+1e-7);
	for(i=1;i<=n;i++)
		belong[i]=(i-1)/b+1;
	for(i=1;(i-1)*b+1<=n;i++)
		l[i]=(i-1)*b+1,r[i]=min(i*b,n);

	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=m;i++)
		scanf("%d%d",&queries[i].l,&queries[i].r),queries[i].id=i;
	sort(queries+1,queries+n+1);
	for(i=1;i<=m;i++)
	{
		while(Rqueries[i].l)
			Update(a[--L]);
		while(R>queries[i].r)
			Downdate(a[R--]);
		while(L