BZOJ 1878 [SDOI2009]HH的項鍊 莫隊

Description

HH有一串由各種漂亮的貝殼組成的項鍊。HH相信不同的貝殼會帶來好運，是以每次散步 完後，他都會随意取出一

段貝殼，思考它們所表達的含義。HH不斷地收集新的貝殼，是以他的項鍊變得越來越長。有一天，他突然提出了一

個問題：某一段貝殼中，包含了多少種不同的貝殼？這個問題很難回答。。。因為項鍊實在是太長了。于是，他隻

好求助睿智的你，來解決這個問題。

Input

第一行：一個整數N，表示項鍊的長度。 

第二行：N個整數，表示依次表示項鍊中貝殼的編号（編号為0到1000000之間的整數）。 

第三行：一個整數M，表示HH詢問的個數。 

接下來M行：每行兩個整數，L和R（1 ≤ L ≤ R ≤ N），表示詢問的區間。

N ≤ 50000，M ≤ 200000。

Output

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

Sample Input

6

1 2 3 4 3 5

3

1 2

3 5

2 6

Sample Output

2

2

4

HINT

Source

​​題目連結​​

今天比較煩躁……沒什麼精神。。

早上起來很晚了…結果下午又睡到傍晚……感覺很累。。

晚上也不知道該幹什麼……

決定切切水題把…………

不知道要寫什麼類型的題目。。

可能太水無益，略有複雜我又沒什麼力氣。

快要期末考了，，這麼頹廢真的好嗎？？

最後決定看看莫隊的題目。。

回到正題。

這題的話……說實話有點水了，就是莫隊的基礎題目了。。

當然其它的強大做法也是可以的……

莫隊算法給所有詢問一個基礎的順序，使得時間複雜度降為Q*根号Q

具體可以看我的blog裡的講述 ​​ ​​

題目好像連個坑都不設的……連離散化也不需要……

好吧，水題做了，心中至少快活了一些。。

#include<bits/stdc++.h>
using namespace std; 
int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int 
    N=50005,
    M=200005,
    MAXNUM=1000005,
    Block=230;
int n,Q,ans;
int a[N],p[MAXNUM],Ans[M];
struct Query{
    int L,R,id;
}q[M];
bool cmp(Query x,Query y){
    if (x.L/Block!=y.L/Block)
        return x.L<y.L;
    return x.R<y.R;
}
void add(int x){
    p[a[x]]++;
    if (p[a[x]]==1) ans++;
}
void remove(int x){
    p[a[x]]--;
    if (!p[a[x]]) ans--;
}
int main(){
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    Q=read();
    for (int i=1;i<=Q;i++)
        q[i].L=read(),q[i].R=read(),
        q[i].id=i;
    sort(q+1,q+1+Q,cmp);
    int L=0,R=0; ans=0;
    for (int i=1;i<=Q;i++){
        while (L<q[i].L) remove(L++);
        while (L>q[i].L) add(--L);
        while (R<q[i].R) add(++R);
        while (R>q[i].R) remove(R--);
        Ans[q[i].id]=ans;
    }
    for (int i=1;i<=Q;i++)
        printf("%d\n",Ans[i]);
    return 0;
}