@[toc]

题目链接:[SDOI2009]HH的项链

时间限制: C/C++ 1秒,其他语言2秒
空间限制: C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
HH有一串由各种漂亮的贝壳组成的项链。
HH相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一 段贝壳,思考它们所表达的含义。
HH不断地收集新的贝壳,因此他的项链变得越来越长。
有一天,他突然提出了一 个问题:某一段贝壳中,包含了多少种不同的贝壳?
这个问题很难回答。。。因为项链实在是太长了。于是,他只 好求助睿智的你,来解决这个问题。
输入描述:
第一行:一个整数N,表示项链的长度。
第二行:N个整数,表示依次表示项链中贝壳的编号(编号为0到1000000之间的整数)。
第三行:一个整数M,表示HH询问的个数。
接下来M行:每行两个整数,L和R(1 ≤ L ≤ R ≤ N),表示询问的区间。
N ≤ 50000,M ≤ 200000。
输出描述:
M行,每行一个整数,依次表示询问对应的答案。
示例1
输入

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

输出

2
2
4

题目大意

求区间不相同的数字有几个

解题思路

本菜鸡使用了离线的树状数组的做法,将要求需要查询的区间按照右边值按照从小到大的排列方式,进行查找,然后进行查找,我们可以既然按照有边界从小到大查询,我们可以用一个数组边标记这个值是否之前出来过,如果没出来那么就把这个值标记为当前的位置,如果出来过那么就从标记的位置开始向上减,最后再在这个位置以后向上加。这样我们就可以按照树状数组求区间和来解决了。
比如说123425,这个数组,第五个位置的2出现时标记数组pos[2]=2记录的是上个位置;所以add(2,-1);然后add(5,1);如果没有标记过就直接add(5,1),我们这样操作就不会影响求后面的了,当求区间(3,5)那么就是sum(5)-sum(3-1);

代码

#include<bits/stdc++.h>
using namespace std;
int a[1000100];//存输入数值
int f[1000100];//记录是否出现
int c[1000100];//树状数组维护前缀和
int pos[1000100];//标记每个值对应的位置
int ans[1000100];//记录答案用的
int n,m;
struct node{
    int l,r;
    int id;//标记这个区间是第几次输入进来的
    //这个是用于告诉sort如何排序
    //按照右边界从小到大排序
    bool operator < (const node &x) const{
            return r<x.r;
    }
}tre[1000100];
//树状数组的更新操作
void add(int x,int k){
    for(int i=x;i<=n;i+=(i&-i)) c[i]+=k;
}
int sum(int x){//树状数组的求和操作
    int an=0;
    for(int i=x;i;i-=(i&-i)) an+=c[i];
    return an;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>tre[i].l>>tre[i].r;tre[i].id=i;
    }
    sort(tre+1,tre+1+m);
    int k=1;
    for(int i=1;i<=m;i++)
    {
        for(k;k<=tre[i].r;k++)
        {
            if(f[a[k]])//如果这个值出现
            {
                add(f[a[k]],-1);//就从上次出现的位置开始减
            }
            add(k,1);//这个位置再重新加
            f[a[k]]=k;//记录这次出现的位置
        }
        ans[tre[i].id]=sum(tre[i].r)-sum(tre[i].l-1);//求答案
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}