fork(12) download
copy 
  1. #include<bits/stdc++.h>
  2. #define LL long long int
  3. #define s(a) scanf("%d",&a)
  4. #define sl(a) scanf("%lld",&a)
  5. #define ss(a) scanf("%s",a)
  6. #define w(t) while(t--)
  7. #define f(i,n) for(i=0;i<n;i++)
  8. #define fd(i,n) for(i=n-1;i>=0;i--)
  9. #define p(a) printf("%d",a)
  10. #define pl(a) printf("%lld",a)
  11. #define ps(a) printf("%s",a)
  12. #define pc(a) printf("%c",a)
  13. #define ent printf("\n")
  14. #define mod 1000000007
  15. #define PI 3.14159265
  16. #define gs getline(cin,s)
  17. #define pb push_back
  18. #define mp make_pair
  19. #define INF 1e18
  20.  
  21. using namespace std;
  22.  
  23. unordered_map<int,int> pos;
  24. int ar[300005];
  25. int tree[16*300000+5];
  26. int lft[16*300000+5];
  27. int rht[16*300000+5];
  28. int root[600005];
  29. int rt[300005];
  30. int idx;
  31.  
  32. inline void build(int node,int start,int end)
  33. {
  34.     if(start==end)
  35.         {
  36.             tree[node]=0;
  37.             return;
  38.         }
  39.         lft[node]=idx++;
  40.         rht[node]=idx++;
  41.         int mid=(start+end)/2;
  42.         build(lft[node],start,mid);
  43.         build(rht[node],mid+1,end);
  44.         tree[node]=0;
  45. }
  46.  
  47. inline int update(int node,int start,int end,int pos,int val)
  48. {
  49.     int x;
  50.     x=idx++;
  51.     if(start==end)
  52.     {
  53.         tree[x]=val;
  54.         return x;
  55.     }
  56.     lft[x]=lft[node];
  57.     rht[x]=rht[node];
  58.     int mid=(start+end)/2;
  59.     if(pos<=mid)
  60.         lft[x]=update(lft[x],start,mid,pos,val);
  61.     else
  62.         rht[x]=update(rht[x],mid+1,end,pos,val);
  63.  
  64.     tree[x]=tree[lft[x]]+tree[rht[x]];
  65.  
  66.     return x;
  67. }
  68.  
  69. inline int query(int node,int start,int end,int l,int r)
  70. {
  71.     if(start>r || end<l)
  72.         return 0;
  73.     else if(start>=l && end<=r)
  74.         return tree[node];
  75.     int mid=(start+end)/2;
  76.     int q1=query(lft[node],start,mid,l,r);
  77.     int q2=query(rht[node],mid+1,end,l,r);
  78.  
  79.     return (q1+q2);
  80. }
  81.  
  82.  
  83. int main()
  84. {
  85.     std:ios_base::sync_with_stdio(false);
  86.     int n;
  87.     s(n);
  88.  
  89.     int i;
  90.  
  91.       idx=0;
  92.        root[0]=0;
  93.         build(0,1,n);
  94.  
  95.     int t=1;
  96.     for(i=1;i<=n;i++)
  97.     {
  98.         s(ar[i]);
  99.         int k=pos[ar[i]];
  100.         if(k!=0)
  101.         {
  102.             root[t]=update(root[t-1],1,n,k,0);
  103.             t++;
  104.             root[t]=update(root[t-1],1,n,i,1);
  105.             t++;
  106.         }
  107.         else
  108.         {
  109.             root[t]=update(root[t-1],1,n,i,1);
  110.             t++;
  111.         }
  112.  
  113.         rt[i]=t-1;
  114.         pos[ar[i]]=i;
  115.     }
  116.  
  117.     int m;
  118.     s(m);
  119.  
  120.     while(m--)
  121.     {
  122.         int a,b;
  123.         s(a);
  124.         s(b);
  125.  
  126.         p(query(root[rt[b]],1,n,a,b));
  127.         ent;
  128.     }
  129.  
  130.  return 0;
  131.  
  132. }
Runtime error #stdin #stdout 0.01s 76992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ccc8wc
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!