luogu 3901 Difference

Difference

题目描述

现有数列A_1,A_2,cdots,A_NA​1​​,A​2​​,⋯,A​N​​，Q 个询问(L_i,R_i)(L​i​​,R​i​​)，A_{Li} ,A_{Li+1},cdots,A_{Ri}A​Li​​,A​Li+1​​,⋯,A​Ri​​ 是否互不相同

输入输出格式

输入格式：

第1 行，2 个整数N,QN,Q

第2 行，N 个整数A_{Li} ,A_{Li+1},cdots,A_{Ri}A​Li​​,A​Li+1​​,⋯,A​Ri​​

Q 行，每行2 个整数L_i,R_iL​i​​,R​i​​

输出格式：

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

输入输出样例

输入样例#1：

4 2
1 2 3 2
1 3
2 4

输出样例#1：

Yes
No

说明

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

• 对于100% 的数据，1 le N,Q le 10^5, 1 le A_i le N, 1 le L_i le R_i le N1≤N,Q≤10​5​​,1≤A​i​​≤N,1≤L​i​​≤R​i​​≤N

题解：

裸的莫队，真的很简单。
按询问排序，按左端点位置分成sqrt(n)份，每份按右端点从小到大排序即可。
然后尺取法就可以了：
代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,a[100001],vis[100001],tot,lim,ans[100001];
struct ask
{
    int l,r,id;
}b[100001];
bool cmp(const ask a,const ask b)
{
    if(a.l/lim!=b.l/lim)return a.l/lim<b.l/lim;else return a.r<b.r;
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    lim=sqrt(n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&b[i].l,&b[i].r);
        b[i].id=i;
    }
    sort(b+1,b+m+1,cmp);
    int left=1,right=0;
    for(i=1;i<=m;i++)
    {
        while(left<b[i].l){if(--vis[a[left]]==0)tot--;left++;}
        while(left>b[i].l){left--;if(++vis[a[left]]==1)tot++;}
        while(right<b[i].r){right++;if(++vis[a[right]]==1)tot++;}
        while(right>b[i].r){if(--vis[a[right]]==0)tot--;right--;}
        ans[b[i].id]=tot==b[i].r-b[i].l+1;
    }
    for(i=1;i<=m;i++)
    {
        if(ans[i])printf("Yes
");
        else printf("No
");
    }
    return 0;
}