題目背景

無

題目描述

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

輸入輸出格式

輸入格式：
第一行：一個整數N，表示項鏈的長度。

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

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

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

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

輸入輸出樣例

輸入樣例#1：
6
1 2 3 4 3 5
3
1 2
3 5
2 6
輸出樣例#1：
2
2
4
說明

數據范圍：

對于100%的數據，N <= 50000，M <= 200000。

考慮一下離線來寫這道題。對每一種貝殼，都只記錄它第一次出現的位置。
如：{2,3,3,3,6,6,8,6,6}
記：{1,1,0,0,1,0,1,0,0}
可以注意到這時記錄的數組元素之和為[1,n]的答案。受此啟發，現將詢問按照l,r排序。
上面的例子，若l=3，r=n，答案顯然少了1.也就是說，當l變大時，要修改記錄數組的值。
如：{2,3,3,3,6,6,8,6,6}
l=3:{0,0,1,0,1,0,1,0,0}
注意到3以前的數都是0，反正不會再用到了。
所以每次l向右推進時都要更新記錄數組，方法就是將l處值改為0（其實隨便），把下一個相同的數記錄值改為1.用樹狀數組實現。
Orz莫隊大佬
樹狀數組+離線=常數巨大......

#include <cstdio>
#include <algorithm>
using namespace std;
#define lowbit(o) (o&(-o))
int tree[50001];
struct pa {int l,r,id,ans;
} Ask[200001];
int nxt[50001];
int fir[1000001];
bool comp_l(const pa &a,const pa &b) {return a.l<b.l;
}
bool comp_id(const pa &a,const pa &b) {return a.id<b.id;
}
int n;
inline int gi() {int p=0;char c=getchar();while(c<'0'||c>'9')c=getchar();for(; c>='0'&&c<='9'; c=getchar())p=p*10+c-'0';return p;
}
inline int ask(int i) {int sum=0;while(i)sum+=tree[i],i-=lowbit(i);return sum;
}
void add(int i,int num) {while(i<=n)tree[i]+=num,i+=lowbit(i);
}
int main() {n=gi();int data,iiii;for(int i=1; i<=n; i++) {data=gi();if(!fir[data])fir[data]=i,add(i,1);else {for(iiii=fir[data]; nxt[iiii]; iiii=nxt[iiii]);nxt[iiii]=i;}}int m=gi();for(int i=0; i<m; i++)Ask[i].l=gi(),Ask[i].r=gi(),Ask[i].id=i;std::sort(Ask,Ask+m,comp_l);int l=1;for(int i=0; i<m; i++) { //左端點while(Ask[i].l>l){if(nxt[l])add(nxt[l],1);l++;}Ask[i].ans=ask(Ask[i].r)-ask(l-1);}std::sort(Ask,Ask+m,comp_id);for(int i=0; i<m; i++)printf("%d\n",Ask[i].ans);return 0;
}

睡覺！

轉載于:https://www.cnblogs.com/xzz_233/p/7296336.html

總結

以上是生活随笔為你收集整理的[SDOI2009]HH的项链的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。