本来想做这道题的。。。后来发现根本搞不懂
于是又滚回了BZOJ 1878搞了搞。。。
发现这道题和1878差不多，只是要注意update的时候要加个next
其实我们可以推广到3个、4个、5个（貌似可以用倍增？感觉可以出一道题呢、、、）
然后就没有然后啦~，不要问我为什么用了fread。。。只是无聊了≥v≤~
1 /************************************************************** 2 Problem: 2743 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:3940 ms 7 Memory:56472 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 #define lowbit(x) x & -x 14 using namespace std; 15 const int N = 1000005; 16 const int Maxlen = 25 * N; 17 struct data{ 18 int l, r, w; 19 inline bool operator < (const data &x) const { 20 return l == x.l ? r < x.r : l < x.l; 21 } 22 } q[N]; 23 24 int n, m, c; 25 int a[N], next[N], first[N]; 26 int BIT[N]; 27 int ans[N]; 28 29 char buf[Maxlen], *C = buf; 30 int Len; 31 inline int read() { 32 int x = 0; 33 while (*C < '0' || '9' < *C) ++C; 34 while ('0' <= *C && *C <= '9') 35 x = x * 10 + *C - '0', ++C; 36 return x; 37 } 38 39 int L, pr[10]; 40 void print(int x) { 41 if (!x) { 42 puts("0"); 43 return; 44 } 45 while (x) 46 pr[++L] = x % 10, x /= 10; 47 while (L) 48 putchar(pr[L--] + '0'); 49 putchar(' '); 50 } 51 52 void update(int x, int v) { 53 if (!x) return; 54 while (x <= n) 55 BIT[x] += v, x += lowbit(x); 56 } 57 58 int query(int x) { 59 int res = 0; 60 while (x) 61 res += BIT[x], x -= lowbit(x); 62 return res; 63 } 64 65 int main() { 66 int i, l; 67 Len = fread(C, 1, Maxlen, stdin); 68 buf[Len] = ' '; 69 n = read(), c = read(), m = read(); 70 for (i = 1; i <= n; ++i) 71 a[i] = read(); 72 for (i = n; i; --i) 73 next[i] = first[a[i]], first[a[i]] = i; 74 for (i = 1; i <= c; ++i) 75 update(next[first[i]], 1); 76 77 for (i = 1; i <= m; ++i) 78 q[i].l = read(), q[i].r = read(), q[i].w = i; 79 sort(q + 1, q + m + 1); 80 for (i = l = 1; i <= m; ++i) { 81 for (; l < q[i].l; ++l) 82 update(next[l], -1), update(next[next[l]], 1); 83 ans[q[i].w] = query(q[i].r) - query(q[i].l - 1); 84 } 85 for (i = 1; i <= m; ++i) 86 print(ans[i]); 87 return 0; 88 }