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
1 2 3 4 3 5
3
1 2
3 5
2 6
Sample Output
2
2
4
2
4
題解:額,莫隊入門題,真的非常好理解,學會以后只能orz莫隊,實在是太暴力了,正因為暴力,莫隊可以做很多只有暴力才能搞的區間查詢,整個代碼難度主要在一些細節上,但其實實在不行可以背啊~
代碼如下:
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;struct node {int l,r,id; }q[200020];int a[50050],cnt[1000010],n,m,sz,sum,ans[200020];int block(int x) {return (x+1)/sz; }int cmp(node a,node b) {if(block(a.l)==block(b.l)){return a.r<b.r;}return a.l<b.l; }void add(int x) {if(!cnt[a[x]]){sum++;}cnt[a[x]]++; }void del(int x) {if(cnt[a[x]]==1){sum--;}cnt[a[x]]--; }int main() {scanf("%d",&n);sz=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+m+1,cmp);int nowl=1,nowr=0;for(int i=1;i<=m;i++){while(nowl<q[i].l) del(nowl++);while(nowl>q[i].l) add(--nowl);while(nowr<q[i].r) add(++nowr);while(nowr>q[i].r) del(nowr--);ans[q[i].id]=sum;}for(int i=1;i<=m;i++){printf("%d\n",ans[i]);} }
?