fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mx = 1e5 + 5;
  5. const int S = 320;
  6. //
  7. struct query
  8. {
  9.     int l, r, x, id;
  10.     //
  11.     bool operator < (const query &other)
  12.     {
  13.         if (l / S != other.l / S)
  14.             return l < other.l;
  15.         return l / S & 1 ? r < other.r : r > other.r;
  16.     }
  17. };
  18. //
  19. int n, q, A[mx];
  20. int cnt[mx], orz[mx], ans[mx];
  21. query Q[mx];
  22. //
  23. void calc (void)
  24. {
  25.     int l = 0, r = 0;
  26.     //
  27.     for (int i = 1; i <= q; ++i)
  28.     {
  29.         while (l < Q[i].l)
  30.         {
  31.             --orz[cnt[A[l]]];
  32.             --cnt[A[l]];
  33.             ++orz[cnt[A[l]]];
  34.             ++l;
  35.         }
  36.         while (l > Q[i].l)
  37.         {
  38.             --l;
  39.             --orz[cnt[A[l]]];
  40.             ++cnt[A[l]];
  41.             ++orz[cnt[A[l]]];
  42.         }
  43.         while (r < Q[i].r)
  44.         {
  45.             ++r;
  46.             --orz[cnt[A[r]]];
  47.             ++cnt[A[r]];
  48.             ++orz[cnt[A[r]]];
  49.         }
  50.         while (r > Q[i].r)
  51.         {
  52.             --orz[cnt[A[r]]];
  53.             --cnt[A[r]];
  54.             ++orz[cnt[A[r]]];
  55.             --r;
  56.         }
  57.         ans[Q[i].id] = orz[Q[i].x];
  58.     }
  59. }
  60. //
  61. void process (void)
  62. {
  63.     cin >> n >> q;
  64.     for (int i = 1; i <= n; ++i)
  65.         cin >> A[i];
  66.     for (int i = 1; i <= q; ++i)
  67.         cin >> Q[i].l >> Q[i].r >> Q[i].x,
  68.         Q[i].id = i;
  69.  
  70.     sort(Q + 1, Q + q + 1);
  71.     calc();
  72.  
  73.     for (int i = 1; i <= q; ++i)
  74.         cout << ans[i] << '\n';
  75. }
  76. //
  77. signed main (void)
  78. {
  79.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  80.     process();
  81. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/t8O0YS
https://m...content-available-to-author-only...j.com/problem/261
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!