fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int LL;
  4.  
  5. const int N=5*100005;
  6.  
  7. struct node{
  8.   int l;
  9.   int r;
  10.   int id;
  11. }u[N];
  12.  
  13. int z;
  14. bool cool(node a,node b)
  15. {
  16.      if(a.l/z<b.l/z)
  17.         return true;
  18.      if(a.l/z>b.l/z)
  19.         return false;
  20.      return a.r<b.r;
  21. }
  22. int cnt[N];
  23. int cp[N];
  24. int ans[N];
  25. int v[N];
  26.  
  27. map<int,int>cmp;
  28.  
  29. int main()
  30. {
  31.  
  32.      //ios_base:: sync_with_stdio(false); cin.tie(0);
  33.      //freopen("input.in","r",stdin);
  34.  
  35.         int n,q;cin>>n>>q;
  36.         int fuk=0;
  37.         z=sqrt(n);
  38.  
  39.         for(int i=0;i<n;i++)
  40.                 scanf("%d",&v[i]),cp[i]=v[i];
  41.  
  42.         sort(cp,cp+n);
  43.         for(int i=0;i<n;i++)if(cmp.find(cp[i])==cmp.end())cmp[cp[i]]=i+1;
  44.         for(int i=0;i<n;i++)v[i]=cmp[v[i]];
  45.  
  46.  
  47.  
  48.         for(int i=0;i<q;i++)
  49.         {
  50.              int l,r;
  51.              scanf("%d %d",&l,&r);
  52.              node tmp;
  53.              tmp.l=l-1;
  54.              tmp.r=r-1;
  55.              tmp.id=i;
  56.              u[i]=tmp;
  57.         }
  58.  
  59.          sort(u,u+q,cool);
  60.  
  61.          int st=0,e=0;fuk=0;cnt[v[0]]++;
  62.  
  63.         for(int i=0;i<q;i++)
  64.         {
  65.             int l=u[i].l;
  66.             int r=u[i].r;
  67.            // cout<<l<<" "<<r<<" "<<st<<" "<<e<<" "<<fuk<<endl;
  68.  
  69.             while(st<l)
  70.             {
  71.                 cnt[v[st]]--;
  72.                 int gg=cnt[v[st]];
  73.                 if(gg==1)
  74.                  {fuk--;}
  75.                 else if(gg==2){fuk++;}
  76.                  st++;
  77.             }
  78.             while(st>l)
  79.             {
  80.                  st--;
  81.                  cnt[v[st]]++;
  82.                  int gg=cnt[v[st]];
  83.                  if(gg==2)
  84.                  {
  85.                     fuk++;
  86.                  }
  87.                  else if(gg==3)
  88.                  {
  89.                     fuk--;
  90.                  }
  91.             }
  92.             while(e<r)
  93.             {
  94.                 e++;
  95.                 cnt[v[e]]++;
  96.                 int gg=cnt[v[e]];
  97.                 if(gg==2)
  98.                 {fuk++;}
  99.                else if(gg==3){fuk--;}
  100.             }
  101.             while(e>r)
  102.             {
  103.                cnt[v[e]]--;
  104.                int gg=cnt[v[e]];
  105.                if(gg==1)
  106.                {fuk--;}
  107.                else if(gg==2){fuk++;}
  108.                e--;
  109.             }            
  110.             ans[u[i].id]=fuk;
  111.         }
  112.  
  113.         for(int i=0;i<q;i++)
  114.             printf("%d\n",ans[i]);
  115.  
  116.      return 0;
  117. }
  118.  
  119.  
Runtime error #stdin #stdout 0.86s 17152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kLtIFH
language:
C++14 (gcc 8.3)
created:
7 years 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!