# Untitled

a guest
Jun 10th, 2014
2,061
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <algorithm>
3. #include <cstdio>
4. #define f first
5. #define s second
6.
7. using namespace std;
8.
9. pair <int, pair <int, int> > q[200001];
10. int n, m, a[100001], ans[200001];
11. int st[5*100001], used[1000001];
12. int cmp(pair <int, pair <int, int> > a, pair <int, pair <int, int> > b)
13. {
14. if (a.s.f != b.s.f)
15. return a.s.f < b.s.f;
16. return a.f < b.f;
17. }
18. void update(int v, int l, int r, int x, int d)
19. {
20. if (l == r)
21. {
22. st[v] = d;
23. return;
24. }
25. int mid = (l + r) / 2;
26. if (x <= mid)
27. update(v * 2, l, mid, x, d);
28. else
29. update(v * 2 + 1, mid + 1, r, x, d);
30. st[v] = st[v * 2] + st[v * 2 + 1];
31. }
32. int Find(int v, int A, int B, int l, int r)
33. {
34. if (l > B || r < A)
35. return 0;
36. if (A == l && B == r)
37. return st[v];
38. int mid = (A + B) / 2;
39. return Find(v * 2, A, mid, l, min(mid, r)) + Find(v * 2 + 1, mid + 1, B, max(mid + 1, l), r);
40. }
41.
42. int main()
43. {
44. scanf("%d", &n);
45. for (int i = 1; i <= n; i++)
46. scanf("%d", &a[i]);
47. scanf("%d", &m);
48. for (int i = 1; i <= m; i++)
49. scanf("%d %d", &q[i].f, &q[i].s.f), q[i].s.s = i;
50. sort(q + 1, q + m + 1, cmp);
51. int j = 1;
52. for (int i = 1; i <= m; i++)
53. {
54. while(j <= q[i].s.f)
55. {
56. if (!used[a[j]])
57. {
58. update(1, 1, n, j, 1);
59. used[a[j]] = j;
60. }
61. else
62. {
63. update(1, 1, n, used[a[j]], 0);
64. update(1, 1, n, j, 1);
65. used[a[j]] = j;
66. }
67. j++;
68. }
69. ans[q[i].s.s] = Find(1, 1, n, q[i].f, q[i].s.f);
70. }
71. for (int i = 1; i <= m; i++)
72. printf("%d\n", ans[i]);
73.
74. return 0;
75. }