CF368B Sereja and Suffixes 题解

CF368B Sereja and Suffixes题面

题面描述

给出一个长度为 n 的序列 a，有 m 个查询,对于每个查询，给出一个数 l ,输出 [l,n] 的区间内不同的数的个数。

分析

我们发现题目需要求的答案是从 l 到 n 的，很自然的想到我们从后往前维护一个数组 sum , sum[i] 表示从 i 到 n 区间中不同的数的个数。

①如果当前位置的 a[i] 在 [i+1,n] 中出现过了，那么 sum[i]=sum[i+1] 。

②如果在后面都没有出现此数，那么 sum[i]=sum[i+1]+1。

于是，现在我们考虑如何判断在 [i+1,n] 中是否出现过此数，因为 1<=a[i]<=10
^5 ,所以我们可以直接用一个桶来维护。
但是出于某些原因，我的代码中使用了 map ,来储存（简单对不懂 map 的同学们解释一下，我们可以将 map 当成一个下表可以是任意数的数组，是我们编写 c++程序的有利助手（没学过的同学们可以去其他渠道学习一下））。

AC记录

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
ll read() 
{
    ll res=0,f=1;
    char c=getchar();
    while(!isdigit(c) && c!='-') c=getchar();
    if(c=='-') f=-1,c=getchar();
    while(isdigit(c)) res=(res<<1)+(res<<3)+c-48,c=getchar();
    return res*f;
}
int n,m;
int a[maxn],sum[maxn];
map<int,int> mp;
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=n;i;i--) 
        if(!mp[a[i]]) 
        {
            mp[a[i]]=1;
            sum[i]=sum[i+1]+1;
        }
        else 
            sum[i]=sum[i+1];
    for(int i=1;i<=m;i++)
    {
        int l=read();
        printf("%d\n",sum[l]);
    }
    return 0;
}

有问题欢迎在评论区提出awa