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\n") : printf("No\n");
        }
        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\n"):printf("Yes\n");
    return 0;
}