1878: [SDOI2009]HH的項鏈
Time Limit:?4 Sec??Memory Limit:?64 MBSubmit:?3548??Solved:?1757
[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
1 2 3 4 3 5
3
1 2
3 5
2 6
Sample Output
2
2
4
2
4
HINT
對于20%的數據，N ≤ 100，M ≤ 1000；
對于40%的數據，N ≤ 3000，M ≤ 200000；
對于100%的數據，N ≤ 50000，M ≤ 200000。
Source
Day2
?
OTZ NEIGHTHORN
樹狀數組O(NlogN) 或 莫隊算法O(N^1.5)
1 #include <bits/stdc++.h> 2 3 /* SCANNER */ 4 5 #define siz 1024 6 7 inline int get_c(void) 8 { 9 static char buf[siz]; 10 static char *head = buf + siz; 11 static char *tail = buf + siz; 12 13 if (head == tail) 14 fread(head = buf, 1, siz, stdin); 15 16 return *head++; 17 } 18 19 inline int get_i(void) 20 { 21 register int ret = 0; 22 register int neg = false; 23 register int bit = get_c(); 24 25 for (; bit < 48; bit = get_c()) 26 if (bit == '-')neg ^= true; 27 28 for (; bit > 47; bit = get_c()) 29 ret = ret * 10 + bit - 48; 30 31 return neg ? -ret : ret; 32 } 33 34 #define N 50005 35 #define M 200005 36 #define V 1000005 37 38 int n, m; 39 int num[N]; 40 41 /* PREWORK */ 42 43 int nxt[N]; 44 int lst[V]; 45 int fst[V]; 46 47 /* QUERY */ 48 49 int lt[M]; 50 int rt[M]; 51 int ans[M]; 52 int ord[M]; 53 54 inline bool cmp(int a, int b) 55 { 56 return lt[a] < lt[b]; 57 } 58 59 /* B I T */ 60 61 int tree[N]; 62 63 inline void add(int p, int k) 64 { 65 for (; p <= n; p += p&-p) 66 tree[p] += k; 67 } 68 69 inline int ask(int p) 70 { 71 int ret = 0; 72 for (; p >= 1; p -= p&-p) 73 ret += tree[p]; 74 return ret; 75 } 76 77 /* MAIN */ 78 79 signed main(void) 80 { 81 n = get_i(); 82 83 for (int i = 1; i <= n; ++i) 84 num[i] = get_i(); 85 86 for (int i = 0; i < V; ++i) 87 lst[i] = n + 1; 88 89 for (int i = n; i >= 1; --i) 90 nxt[i] = lst[num[i]], lst[num[i]] = i; 91 92 for (int i = 1; i <= n; ++i) 93 if (!fst[num[i]]) 94 { 95 add(i, 1); 96 fst[num[i]] = 1; 97 } 98 99 m = get_i(); 100 101 for (int i = 1; i <= m; ++i) 102 { 103 ord[i] = i; 104 lt[i] = get_i(); 105 rt[i] = get_i(); 106 } 107 108 std::sort(ord + 1, ord + 1 + m, cmp); 109 110 int left = 1; 111 112 for (int i = 1; i <= m; ++i) 113 { 114 while (left < lt[ord[i]]) 115 { 116 add(left, -1); 117 add(nxt[left], 1); 118 ++left; 119 } 120 121 ans[ord[i]] = ask(rt[ord[i]]); 122 } 123 124 for (int i = 1; i <= m; ++i) 125 printf("%d\n", ans[i]); 126 }
?
@Author: YouSiki
