luogu P3901 数列找不同 莫队+分块

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],belong[N];
int n,q;
inline int read()
{
    int k=0;
    char c;
    c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c)){k=(k<<3)+(k<<1)+c-'0';c=getchar();}
    return k;
}
struct node
{
    int l,r;
    int id;
} e[N];
int cnt[N];
int Ans;
int ans[N];
inline bool cmp(node a,node b)
{
    if(belong[a.l]==belong[b.l])
        return belong[a.r]<belong[b.r];
    return belong[a.l]<belong[b.l];
}
inline void add(int x)
{
    if(!cnt[a[x]])
        ++ Ans;
    ++ cnt[a[x]];
}
inline void del(int x)
{
    if(cnt[a[x]] == 1)
        -- Ans;
    -- cnt[a[x]];
}
int main()
{
    n=read(),q=read();
    int block = pow(n,0.5);
    for(register int i = 1; i <= n; ++ i)
    {
        a[i]=read();
        belong[i] = (i - 1) / block + 1;
    }
    for(register int i=1; i<=q; i++)
    {
        e[i].l=read();
        e[i].r=read();
        e[i].id=i;
    }
    sort(e+1,e+1+q,cmp);
    int l = 1,r = 0;
    for(register int i = 1; i <= q; ++ i)
    {
        while(l < e[i].l)
            del(l ++);
        while(l > e[i].l)
            add(-- l);
        while(r < e[i].r)
            add(++ r);
        while(r > e[i].r)
            del(r --);
        if(Ans==(e[i].r-e[i].l+1))
            ans[e[i].id] = 1;
    }
    for(register int i = 1; i <= q; ++ i)
        if(ans[i]==1)
            printf("Yes
");
        else
            printf("No
");
    return 0;
}