P1972 [SDOI2009] HH的项链

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入格式

一行一个正整数 n，表示项链长度。
第二行 nn 个正整数 ai​，表示项链中第 ii 个贝壳的种类。

第三行一个整数 m，表示 HH 询问的个数。
接下来 m 行，每行两个整数 l,rl,r，表示询问的区间。

输出格式

输出 mm 行，每行一个整数，依次表示询问对应的答案。

输入输出样例

输入 #1复制

6
1 2 3 4 3 5
3
1 2
3 5
2 6

输出 #1复制

2
2
4

说明/提示

【数据范围】

对于20% 的数据，1≤n,m≤5000；
对于 40% 的数据，1≤n,m≤10^5；
对于60% 的数据，1≤n,m≤5×10^5；
对于 100% 的数据，1≤n,m,ai​≤10^6，1≤l≤r≤n。

本题可能需要较快的读入方式，最大数据点读入数据约 20MB

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2000005;
int pre[MAXN],tot,a[MAXN],m,c[MAXN],n,l,r,ans[MAXN];
struct node
{
	int id;
	int pos;
};
vector<node>q[MAXN];
int lowbit(int x)
{
	return x&-x;
}
void change(int x,int y)
{
	while(x<=n)
	{
		c[x]+=y;
		x+=lowbit(x);
	}
	return;
}
int sum(int x)
{
	int ans=0;
	while(x)
	{
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&l,&r);
        q[r].push_back(node{i,l});
    }
    for(int i=1;i<=n;++i)
    {
        if(pre[a[i]])
        {
            change(pre[a[i]],-1);
            change(i,1);
            pre[a[i]]=i;
        }
        else
        {
            change(i,1);
            pre[a[i]]=i;
        }
        for(auto &j:q[i])
        {
            ans[j.id]=sum(i)-sum(j.pos-1);
        }
    }
    for(int i=1;i<=m;++i)
    {
        printf("%d\n",ans[i]);
    }
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2000005;
int pre[MAXN],tot,a[MAXN],m,c[MAXN],n,l,r,ans[MAXN];
struct query_node
{
	int id;
	int pos;
	query_node(){}
	query_node(int _id,int _pos)
	{
		id=_id;
		pos=_pos;
	}
};
vector<query_node>q[MAXN];
int lowbit(int x)
{
	return x&-x;
}
void change(int x,int y)
{
	while(x<=n)
	{
		c[x]+=y;
		x+=lowbit(x);
	}
	return;
}
int sum(int x)
{
	int ans=0;
	while(x)
	{
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&l,&r);
        q[r].push_back(query_node(i,l));
    }
    for(int i=1;i<=n;++i)
    {
        if(pre[a[i]])
        {
            change(pre[a[i]],-1);
            change(i,1);
            pre[a[i]]=i;
        }
        else
        {
            change(i,1);
            pre[a[i]]=i;
        }
        for(auto &j:q[i])
        {
            ans[j.id]=sum(i)-sum(j.pos-1);
        }
    }
    for(int i=1;i<=m;++i)
    {
        printf("%d\n",ans[i]);
    }
	return 0;
}