【题解】Luogu P3901【数列找不同】

分析

这里可以将原问题转化为求:区间内不同数个数,并且这个数是否等于区间元素个数;这样就将问题转换成了某题:$SDOI2009$【HH的项链】,于是直接跑个莫队就好了

代码

#include<cstdio>
#include<cmath>
#include<algorithm>

const int MAXN = 1000000 + 6;
int A[MAXN],LEFT[MAXN],RIGHT[MAXN],pos[MAXN],num[MAXN],ans;

class Query{
    public:int l,r,id,ans;
};Query Q[MAXN];

inline bool cmp(Query q1,Query q2){return pos[q1.l] == pos[q2.l] ? q1.r < q2.r : q1.l < q2.l;}
inline bool cmp1(Query q1,Query q2){return q1.id < q2.id;}
inline void add(int x){if(++num[A[x]] == 1) ++ans;}
inline void sub(int x){if(--num[A[x]] == 0) --ans;}

int main(){
    int n,m;scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%d",&A[i]);

    int sqr = sqrt(n);
    if(RIGHT[sqr] < n) sqr++,LEFT[sqr] = RIGHT[sqr - 1] + 1,RIGHT[sqr] = n;
    for(int i = 1;i <= sqr;i++){
        LEFT[i] = (i - 1) * sqr + 1;RIGHT[i] = i * sqr;
        for(int j = LEFT[i];j <= RIGHT[i];j++) pos[j] = i;
    } 

    for(int i = 1;i <= m;i++) scanf("%d %d",&Q[i].l,&Q[i].r),Q[i].id = i;
    std::sort(Q + 1,Q + 1 + m,cmp);
    int l = 0,r = 0;
    for(int i = 1;i <= m;i++){
        while(r < Q[i].r) add(++r);
        while(r > Q[i].r) sub(r--);
        while(l < Q[i].l) sub(l++);
        while(l > Q[i].l) add(--l);
        Q[i].ans = ans;
    }

    std::sort(Q + 1,Q + 1 + m,cmp1);
    for(int i = 1;i <= m;i++){
        if(Q[i].ans == Q[i].r - Q[i].l + 1) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注