1033 [SDOI2009]HH的项链 树状数组 离线操作 每个区间出现多少种不同的数

标签：le 贝壳 int 离线 cin HH 区间 1033

链接：https://ac.nowcoder.com/acm/contest/26896/1033
来源：牛客网

题目描述

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

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

输出

复制 2 2 4

2
2
4

备注:

对于20%的数据，1≤n,m≤50001\le n,m\leq 50001≤n,m≤5000；
对于40%的数据，1≤n,m≤1051\le n,m\leq 10^51≤n,m≤105；
对于60%的数据，1≤n,m≤5×1051\le n,m\leq 5\times 10^51≤n,m≤5×105；
对于100%的数据，1≤n,m,ai≤106，1≤l≤r≤n1\le n,m,a_i \leq 10^6，1\le l \le r \le n1≤n,m,ai​≤106，1≤l≤r≤n。

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

分析

题意是查询每个区间有多少种不同的数

区间操作，考虑树状数组，

一开始考虑离线操作，按右端点递增顺序排序区间，然后 遍历所有位置，以右端点为顶点，求所有区间内的数的种数。然后就卡在求区间内的种数怎么求这个问题上了

思路是对的，但遍历所有位置并没有意义，因为对于所有不同的左端点，没办法确定区间内的数的种数，除非临时更改，但这样复杂度又变成了n^2。而且最关键的是，当时想的是将数组的值放到树状数组上，而不是位置。

其实可以考虑到了当前区间右端点，将所有该右端点之前已经出现的数都考虑到数组上，并且对于同种大小的数只记录它最后出现的位置。

取一个last数组，就可以实现，如果last数组已经存了这个数上一次出现的位置，就把上一次出现的位置删除，并加入这一次出现的位置。

//-------------------------代码----------------------------

//#define int ll
const int N = 1e6+10;
int n,m;
int a[N],ans[N],last[N],tr[N];
struct node {
    int id,l,r;
    bool operator<(node &w){
        return r<w.r;
    }
}p[N];
void add(int x,int c) {for(int i=x;i<N;i+=lowbit(i))tr[i]+=c;}
int sum(int x) {int res = 0;for(int i = x;i;i-=lowbit(i))res += tr[i];return res;}
void solve()
{
//    cin>>n>>m;
    cin>>n;
    fo(i,1,n) {
        cin>>a[i];        
    }
    cin>>m;
    fo(i,1,m) {
        int l,r;cin>>l>>r;
        p[i] = {i,l,r};
    }
    sort(p+1,p+1+m);int j = 1;
    fo(i,1,m) {
        while(j <= p[i].r) {
            if(last[a[j]]) add(last[a[j]],-1);
            add(j,1);
            last[a[j]] = j;
            j ++ ;
        }
        ans[p[i].id] = sum(p[i].r) - sum(p[i].l-1);
    }
    fo(i,1,m) cout<<ans[i]<<endl;
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

标签：le,贝壳,int,离线,cin,HH,区间,1033
From： https://www.cnblogs.com/er007/p/16581856.html