Evanyou Blog 彩带

　　题目传送门

题目描述

现有数列 $A_1,A_2,cdots,A_NA1,A2,⋯,AN ，Q 个询问 (L_i,R_i)(Li,Ri) ， A_{Li} ,A_{Li+1},cdots,A_{Ri}ALi,ALi+1,⋯,ARi 是否互不相同$

输入输出格式

输入格式：

第1 行，2 个整数

第2 行，N 个整数 $A_{Li} ,A_{Li+1},cdots,A_{Ri}ALi,ALi+1,⋯,ARi$

Q 行，每行2 个整数 $L_i,R_iLi,Ri$

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

Yes
No

说明

• 对于50% 的数据， $10^3N,Q≤103$

• 对于100% 的数据， $10^5, 1 le A_i le N, 1 le L_i le R_i le N1≤N,Q≤105,1≤Ai≤N,1≤Li≤Ri≤N$

#include<bits/stdc++.h>
#define Fi(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e5+7;
int n,m,s,num=0,d[N],pos[N],sum[N];bool ans[N];
struct Node{int l,r,id;}a[N];
inline bool cmp(Node x,Node y)
{return pos[x.l]==pos[y.l]?x.r<y.r:x.l<y.l;}
inline void change(int i,bool f)
{
  if(f){sum[d[i]]++;if(sum[d[i]]==1)num++;}
  else {sum[d[i]]--;if(sum[d[i]]==0)num--;}
}
int main()
{
  ios::sync_with_stdio(false);
  cin>>n>>m;s=int(sqrt(n));
  memset(ans,false,sizeof(ans));
  Fi(i,1,n){cin>>d[i];pos[i]=(i-1)/s+1;}
  Fi(i,1,m){cin>>a[i].l>>a[i].r;a[i].id=i;}
  sort(a+1,a+1+m,cmp);int l=1,r=0;
  Fi(i,1,m){
    while(l<a[i].l)change(l++,0);
    while(l>a[i].l)change(--l,1);
    while(r<a[i].r)change(++r,1);
    while(r>a[i].r)change(r--,0);
    if(num==a[i].r-a[i].l+1)ans[a[i].id]=true;}
  Fi(i,1,m)if(ans[i])printf("Yes
");else printf("No
");
  return 0;
}