Sereja and Suffixes

https://codeforces.com/problemset/problem/368/B

题意：给定一个数组，查询 l 到 n 这个区间内一共有多少个不同的数字

思路：首先我们计算出从1到 n 一共有多少个不同的数字，并用两个 map 来存储每个数字出现的次数，然后我们定义一个 sum 数组，sum[i] 表示 从i 到 n 一共有多少个不同的数字，这样，我们就可以完成O(1)的查询，那么，如何计算sum值呢？我们知道，sum[1] = cnt ，那么，对于 2<=i<=n 来说，a[i-1] 出现的次数会少一，也就是说，每次将数组往前移一位时，mp[a[i-1]]--，那么，我们就能够据此判断出 sum 的值该如何计算

if mp1[ a[i-1] ] == 0     sum[i] = sum[i-1] -1  因为此时a[i-1] 没有在接下来的区间中出现

else if mp1[ a[i-1] ] < mp[ a[i-1] ]   sum[i] = sum [i-1]  因为 a[i-1] 在接下来的区间中还会出现，那么我们直接继承 sum[i-1] 即可

以下是代码实现：

#include<iostream>
#include<map>
using namespace std;
const int N=1e5+10;
int a[N],sum[N];//sum[i] 表示 从i 到 n 一共有多少个不同的
map<int,int>mp,mp1;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,m;
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(mp[a[i]]==0)
{
cnt++;
}
mp[a[i]]++;
mp1[a[i]]++;
}
mp1[a[1]]--;
sum[1]=cnt;
for(int i=2;i<=n;i++)
{
if(mp1[a[i-1]]==0)
{
sum[i]=sum[i-1]-1;
mp1[a[i]]--;
}
else if(mp1[a[i-1]]<mp[a[i-1]])
{
sum[i]=sum[i-1];
mp1[a[i]]--;
}
}
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
cout<<sum[x]<<endl;
}
return 0;
}

最后

以上就是魁梧乌龟为你收集整理的Sereja and Suffixes的全部内容，希望文章能够帮你解决Sereja and Suffixes所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。