fork download
copy 
  1. /*
  2. Author : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5.  
  6. " when you are not practicing someone else is ,
  7.  and the day u meet them u will lose "
  8.  
  9. */
  10. #include<bits/stdc++.h>
  11. #include<stdio.h>
  12. using namespace std;
  13.  
  14. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  15. #define MAX 300050
  16.  
  17. #define ll long long
  18. #define ld long double
  19. #define lli  int
  20.  
  21. #define pb push_back
  22. #define INF 1000000000000
  23. #define mod 1000000007
  24.  
  25. // trignometric function always give value in Radians only
  26. #define PI acos(-1) //3.1415926535897932384626433832795028
  27. #define dsin(degree) sin(degree*(PI/180.0))
  28. #define dcos(degree) cos(degree*(PI/180.0))
  29. #define dtan(degree) tan(degree*(PI/180.0))
  30.  
  31. #define rsin(radian) sin(radian)
  32. #define rcos(radian) cos(radian)
  33. #define rtan(radian) tan(radian)
  34.  
  35. #define mem0(a) memset(a,0,sizeof(a))
  36. #define mem1(a) memset(a,-1,sizeof(a))
  37. #define memf(a) memset(a,false,sizeof(a))
  38.  
  39. #define loop(i,n)  for (lli i = 0; i < n; i++)
  40. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  41.  
  42. #define all(v) v.begin(),v.end()
  43. #define rall(v) v.rbegin(),v.rend()
  44. #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  45. #define sz(x) int(x.size())
  46. #define F first
  47. #define S second
  48.  
  49. #define mii map<lli,lli>
  50.  
  51. #define pii pair<lli,lli>
  52.  
  53. #define vi vector<lli>
  54. #define vvi vector<vi>
  55. #define vpi vector<pii>
  56. #define vbool vector<bool>
  57.  
  58. #define seti set<lli>
  59.  
  60. #define gcd(a,b) __gcd((a),(b))
  61. #define lcm(a,b) (a/gcd(a,b))*b
  62. #define abs(x) ((x < 0)?-(x):x)
  63.  
  64. #define endl '\n'
  65.  
  66. template <typename Head>
  67. void print(Head&& head)
  68. {
  69.     cout<<head<<endl;
  70. }
  71. template <typename Head, typename... Tail>
  72. void print(Head&& head, Tail... tail)
  73. {
  74.     cout<<head<<" ";
  75.     print(tail...);
  76. }
  77.  
  78. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  79. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  80.  
  81. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  82. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  83.  
  84. #define FD(N) fixed<<setprecision(N)
  85.  
  86. #define deb(x) cout<<#x<<" "<<x<<endl;
  87.  
  88. /*
  89. 1D vector -  vi dp(n,value);
  90. 2D vector -  vvi dp(n,vi(n,value));
  91. */
  92.  
  93. // chandan1,2
  94. void chandan1(){int y=1;return;}
  95. void chandan2(){
  96.         loop(i,10){
  97.         lli x=1;
  98.     }
  99.     return(chandan1());
  100. }
  101.  
  102. //---------------------------------------------------BIT----------------------------------------------------------------------
  103.  
  104. lli BIT[MAX], a[MAX], n;
  105. void update(lli x , lli val)
  106. {
  107.     while(x<=n)
  108.     {
  109.         BIT[x] += val;
  110.         x += (x&-x);
  111.     }
  112. }
  113.  
  114. lli query(lli x)
  115. {
  116.      lli sum = 0;
  117.      while(x>0)
  118.      {
  119.         sum += BIT[x];
  120.         x -= (x&-x);
  121.      }
  122.  
  123.      return sum;
  124. }
  125.  
  126. //--------------------------------------------------BIT------------------------------------------------------------------------
  127.  
  128. int main(){
  129. fastio
  130. lli t=1;
  131. //cin>>t;
  132. chandan2();
  133. while(t--) {
  134.     lli q;
  135.     cin>>n;
  136.     FOR(i,1,n+1)
  137.     {
  138.         cin>>a[i];
  139.     }
  140.  
  141.     cin>>q;
  142.     vpi queries;
  143.     map<pii, lli>pos;
  144.  
  145.      lli ans[q];
  146.      int last_index[1000005];
  147.      mem1(last_index);
  148.  
  149.     loop(i,q)
  150.     {
  151.         lli l,r;
  152.         cin>>l>>r;
  153.         queries.pb({r,l});
  154.         pos[{l,r}]=i;
  155.     }
  156.  
  157.     sort(all(queries));
  158.  
  159.     lli index = 0;
  160.  
  161.     FOR(i,1,n+1)
  162.     {
  163.         if(last_index[a[i]]!=-1)
  164.             update(last_index[a[i]],-1);
  165.  
  166.         last_index[a[i]]=i;
  167.         update(i,1);
  168.  
  169.         while(index<q and queries[index].F == i)
  170.         {
  171.             lli L = queries[index].S;
  172.             lli R = queries[index].F;
  173.             ans[pos[{L,R}]] = query(R)-query(L-1);
  174.  
  175.             index+=1;
  176.         }
  177.  
  178.     }
  179.     loop(i,q)
  180.         print(ans[i]);
  181.   }
  182. return 0;
  183. }
Success #stdin #stdout 0s 7468KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/TgvC5z
language:
C++14 (gcc 8.3)
created:
3 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!