fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7. #define fc first
  8. #define sc second
  9. #define endl '\n'
  10. #define ll long long
  11. #define forn(i, n) for(int i = 0; i < (int) (n); i++)
  12. #define all(x) x.begin(), x.end()
  13. #define rall(x) x.rbegin(), x.rend()
  14.  
  15. const int MAXN = (int) 3e5 + 7, MAXK = (int) 1e6 + 7;
  16. const int MAXQ = (int) 2e5 + 7;
  17. int ans[MAXN], a[MAXN], cnt[MAXK];
  18. const int SZ = 555;
  19.  
  20. struct ev {
  21. int i, l, r;
  22. ev() {}
  23. };
  24.  
  25. ev q[MAXQ];
  26.  
  27. bool cmp(ev a, ev b) {
  28. if (a.l / SZ != b.l / SZ) {
  29. return a.l / SZ < b.l / SZ;
  30. } else {
  31. return a.r < b.r;
  32. }
  33. }
  34.  
  35. int cur_ans = 0;
  36.  
  37. void add(int x) {
  38. cnt[x]++;
  39. if (cnt[x] == 1) {
  40. cur_ans++;
  41. }
  42. }
  43.  
  44. void rem(int x) {
  45. cnt[x]--;
  46. if (cnt[x] == 0) {
  47. cur_ans--;
  48. }
  49. }
  50.  
  51.  
  52. int main() {
  53. int n, m, l, r, nl, nr;
  54. scanf("%d", &n);
  55. forn (i, n) {
  56. scanf("%d", &a[i]);
  57. }
  58. scanf("%d", &m);
  59. forn (i, m) {
  60. scanf("%d%d", &q[i].l, &q[i].r);
  61. q[i].i = i;
  62. }
  63. sort(q, q + m, cmp);
  64. l = r = 0;
  65. add(a[0]);
  66. forn (i, m) {
  67. nl = q[i].l, nr = q[i].r;
  68. nl--, nr--;
  69. while (nl < l) {
  70. l--;
  71. add(a[l]);
  72. }
  73. while (nr > r) {
  74. r++;
  75. add(a[r]);
  76. }
  77. while (nl > l) {
  78. rem(a[l]);
  79. l++;
  80. }
  81. while (nr < r) {
  82. rem(a[r]);
  83. r--;
  84. }
  85. ans[q[i].i] = cur_ans;
  86. }
  87. forn (i, m) {
  88. printf("%d\n", ans[i]);
  89. }
  90. }
  91.  
Time limit exceeded #stdin #stdout 5s 12064KB
stdin
Standard input is empty
stdout
Standard output is empty