P3901 数列找不同

P3901 数列找不同

题目描述

现有数列 (A_1,A_2,cdots,A_N) ，Q 个询问 ((L_i,R_i)) ， (A_{Li} ,A_{Li+1},cdots,A_{Ri}) 是否互不相同

输入输出格式

输入格式：

第1 行，2 个整数 (N,Q)
第2 行，N 个整数 (A_{Li} ,A_{Li+1},cdots,A_{Ri})
Q 行，每行2 个整数 (L_i,R_i)

输出格式：

对每个询问输出一行，“Yes” 或者“No”

输入输出样例

输入样例#1：
4 2
1 2 3 2
1 3
2 4
输出样例#1：
Yes
No

说明

• 对于50% 的数据， (N,Q le 10^3)
• 对于100% 的数据， (1 le N,Q le 10^5, 1 le A_i le N, 1 le L_i le R_i le N)

思路
很明显，暴力分 傻逼分 50
AC的话，用普通莫队即可

代码

//*******************************
//begin 15.30
//user 要好
//end   16.16 
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define maxn 100010
using namespace std;
int n,m,now,k;
int a[maxn];
int ans[maxn];
int belong[maxn];
struct node{
	int x,y,id;
}q[maxn];
int dsr[maxn];
int operator < (const node &a,const node &b)
{
	return belong[a.x]==belong[b.x] ? a.y<b.y : a.x<b.x;
}
int vis[1100];
void Delet(int x)
{
	--dsr[x];
	if(dsr[x]==1) now--;
}
void Add(int x)
{
	++dsr[x];
	if(dsr[x]==2) now++;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	if(n<=1000&&m<=1000)
	{
		while(m--)
		{
			int blx,bly;
			memset(vis,0,sizeof(vis));
			scanf("%d%d",&blx,&bly);
			int i;
			for(i=blx;i<=bly;++i)
			{
				if(!vis[a[i]]) vis[a[i]]=1;
				else break;
			}
			i==bly+1 ? printf("Yes
") : printf("No
");
		}
		return 0;
	}
	k=sqrt(n);
	for(int i=1;i<=n;++i)
		belong[i]=(i-1)/k-1;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&q[i].x,&q[i].y);
		q[i].id=i;
	}
	sort(q+1,q+1+m);
	int l=1,r=0;
	for(int i=1;i<=m;++i)
	{
		while(l > q[i].x) Add(a[--l]);
		while(l < q[i].x) Delet(a[l++]);
		while(r < q[i].y) Add(a[++r]);
		while(r > q[i].y) Delet(a[r--]);
		ans[q[i].id]=now;
	}
	for(int i=1;i<=m;++i)
		ans[i]?printf("No
"):printf("Yes
");
	return 0;
}