Advertisement
Guest User

Untitled

a guest
Jun 10th, 2014
2,061
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.75 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement