【题解】Luogu P3901 数列找不同

我博客中对莫队的详细介绍

原题传送门

不错的莫队练手题

块数就直接取sqrt（n）

对所有询问进行排序

排序第一关键词：l所在第几块，第二关键词：r的位置

考虑Ai不大，暴力开数组

add时如果加之后的数量是1

总数就加1

del时如果减之后的数量是0

总数就减1

每次比较总数和该次查询区间的长度

相等的话就把 ans[q[i].id]设为真

最后如果ans[i]为真就输出Yes，否则输出No

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

#define N 100005

using namespace std;

inline int read()

{

	register int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return x*f;

}

int v[N],blocksize=0;

struct query{

	int l,r,id,bl;

}q[N];

int sum[N];

bool ans[N];

int cnt=0;

inline void add(register int x)

{

	if(++sum[v[x]]==1)

		++cnt;

}

inline void del(register int x)

{

	if(--sum[v[x]]==0)

		--cnt;

}

inline bool cmp(register query a,register query b)

{

	return a.bl==b.bl?a.r<b.r:a.bl<b.bl;

}

int main()

{

	memset(sum,0,sizeof(sum));

	int n=read(),m=read();

	blocksize=sqrt(n);

	for(register int i=1;i<=n;++i)

		v[i]=read();

	for(register int i=1;i<=m;++i)

	{

		int l=read(),r=read();

		q[i]=(query){l,r,i,(l-1)/blocksize+1};

	}

	sort(q+1,q+m+1,cmp);

	int l=1,r=0;

	for(register int i=1;i<=m;++i)

	{

		int ll=q[i].l,rr=q[i].r;

		while(l<ll)

			del(l++);

		while(l>ll)

			add(--l);

		while(r<rr)

			add(++r);

		while(r>rr)

			del(r--);

		ans[q[i].id]=(cnt==rr-ll+1)?1:0;

	}

	for(register int i=1;i<=m;++i)

		if(ans[i])

			puts("Yes");

		else

			puts("No");

	return 0;

 }

巴特西

【题解】Luogu P3901 数列找不同

我博客中对莫队的详细介绍

原题传送门

不错的莫队练手题

块数就直接取sqrt（n）

对所有询问进行排序

排序第一关键词：l所在第几块，第二关键词：r的位置

考虑Ai不大，暴力开数组

add时如果加之后的数量是1

总数就加1

del时如果减之后的数量是0

总数就减1

每次比较总数和该次查询区间的长度

相等的话就把 ans[q[i].id]设为真

最后如果ans[i]为真就输出Yes，否则输出No

最新文章

热门文章