[bzoj1878] [SDOI2009]HH的項鏈(樹狀數組+離線) - Pumbit-Legion－IT工程師數位筆記本

文章出處

1878: [SDOI2009]HH的項鏈

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 3210 Solved: 1619
[Submit][Status][Discuss]

Description

HH有一串由各種漂亮的貝殼組成的項鏈。HH相信不同的貝殼會帶來好運，所以每次散步完后，他都會隨意取出一段貝殼，思考它們所表達的含義。HH不斷地收集新的貝殼，因此，他的項鏈變得越來越長。有一天，他突然提出了一個問題：某一段貝殼中，包含了多少種不同的貝殼？這個問題很難回答。。。因為項鏈實在是太長了。于是，他只好求助睿智的你，來解決這個問題。

Input

第一行：一個整數N，表示項鏈的長度。第二行：N個整數，表示依次表示項鏈中貝殼的編號（編號為0到1000000之間的整數）。第三行：一個整數M，表示HH詢問的個數。接下來M行：每行兩個整數，L和R（1 ≤ L ≤ R ≤ N），表示詢問的區間。

Output

M行，每行一個整數，依次表示詢問對應的答案。

Sample Input

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

Sample Output

2
2
4

HINT

對于20%的數據，N ≤ 100，M ≤ 1000；
對于40%的數據，N ≤ 3000，M ≤ 200000；
對于100%的數據，N ≤ 50000，M ≤ 200000。

Source

Day2

頭一次離線做這種題

一個顯然錯誤的做法：直接算有幾個貝殼，sb地用樹狀數組求01區間的前綴和

但這什么時候正確呢？

當且僅當詢問的區間一種顏色只出現了一次

那么我們不妨先讀進來要求的區間，按左端點排序

一個一個處理詢問，這樣相當于在模擬一個類似滑動窗口的東西，

當滑動窗口左邊掃到一種顏色時，即這種顏色不再計算時，我們再添加下一個和它顏色相同的元素

因為同色元素位置關系是唯一的，所以在給答案加一時，詢問窗口內僅存在一個一種顏色的元素

處理下一個顏色可以預處理出來，初始化時要添加每種顏色的第一個元素

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL long long
using namespace std;
typedef struct{
    int l,r;
    int ans;
    int pos;
}qry;
qry qr[200010];
int a[50050];
int now[1001000],next[50050];
int bit[50050],n;
int cmp1(const qry a,const qry b){
    if(a.l<b.l)return 1;
    else if(a.l==b.l)return a.r<b.r;
    else return 0;
}
int cmp2(const qry a,const qry b){
    return a.pos<b.pos;
}
int lb(int x){
    return x&(-x);
}
int c(int x){
    while(x<=n){
        bit[x]++;
        x+=lb(x);
    }
    return 0;
}
int q(int x){
    int ans=0;
    while(x){
        ans+=bit[x];
        x-=lb(x);
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i]++;//0
        if(!now[a[i]])c(i);
        next[now[a[i]]]=i;
        now[a[i]]=i;
    }    
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d",&qr[i].l,&qr[i].r);
        qr[i].pos=i;
    }
    sort(qr+1,qr+m+1,cmp1);
    int l=1;
    for(int i=1;i<=m;i++){
        //?????
        while(l<qr[i].l){
            if(next[l])c(next[l]);
            l++;
        } 
        qr[i].ans=q(qr[i].r)-q(qr[i].l-1);
    }
    sort(qr+1,qr+m+1,cmp2);
    for(int i=1;i<=m;i++)printf("%d\n",qr[i].ans);
    return 0;
}