fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define N 100005
  4. typedef pair<int,int> ii;
  5. int n,m,a[N],ans[N],res=0,ts[N],bl;
  6. int cnt[N];
  7. struct que
  8. {
  9.     int l,r,x,vt;
  10. };
  11. que q[N];
  12. bool cmp(que a, que b) {
  13.     int block_a = a.l / bl;
  14.     int block_b = b.l / bl;
  15.     if (block_a != block_b)
  16.         return block_a < block_b;
  17.     if (block_a % 2 == 0)
  18.         return a.r < b.r;
  19.     else
  20.         return a.r > b.r;
  21. }
  22. void add(int x)
  23. {
  24.     x=a[x];
  25.     ts[cnt[x]]--;
  26.     cnt[x]++;
  27.     ts[cnt[x]]++;
  28. }
  29. void del(int x)
  30. {
  31.     x=a[x];
  32.     ts[cnt[x]]--;
  33.     cnt[x]--;
  34.     ts[cnt[x]]++;
  35. }
  36. signed main() {
  37.     if(fopen("w.inp","r"))
  38.     {
  39.         freopen("w.inp","r",stdin);
  40.         freopen("w.out","w",stdout);
  41.     }
  42.     ios_base::sync_with_stdio(0);
  43.   cin.tie(0); cout.tie(0);
  44.   cin>>n>>m;
  45.   bl=sqrt(n);
  46.   for(int i=1;i<=n;i++)
  47.     cin>>a[i];
  48.   for(int i=1;i<=m;i++)
  49.   {
  50.       cin>>q[i].l>>q[i].r>>q[i].x;
  51.       q[i].vt=i;
  52.   }
  53.   sort(q+1,q+1+m,cmp);
  54.   int l1=q[1].l;
  55.   int r1=q[1].r;
  56.   for(int i=q[1].l;i<=q[1].r;i++)
  57.     add(i);
  58.   ans[q[1].vt]=ts[q[1].x];
  59.   for(int i=2;i<=m;i++)
  60.   {
  61.       while(l1<q[i].l) del(l1++);
  62.       while(l1>q[i].l) add(--l1);
  63.       while(r1<q[i].r) add(++r1);
  64.       while(r1>q[i].r) del(r1--);
  65.       ans[q[i].vt]=ts[q[i].x];
  66.   }
  67.   for(int i=1;i<=m;i++)
  68.     cout<<ans[i]<<"\n";
  69.     return 0;
  70. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bqLY96
language:
C++14 (clang 8.0)
created:
4 days 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!