fork download
copy 
  1. /*
  2. ███████  ██████  ███    ██ ██  ██████ ██   ██ ██   ██ ██   ██
  3. ██      ██    ██ ████   ██ ██ ██      ██   ██ ██   ██ ██   ██
  4. ███████ ██    ██ ██ ██  ██ ██ ██      ███████ ███████ ███████
  5.      ██ ██    ██ ██  ██ ██ ██ ██           ██      ██      ██
  6. ███████  ██████  ██   ████ ██  ██████      ██      ██      ██
  7. */
  8. #include <bits/stdc++.h>
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. #include <ext/pb_ds/tree_policy.hpp>
  11. using namespace __gnu_pbds;
  12. using namespace std;
  13. #define sonic ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  14. #define endl  "\n"
  15. #define gcd  __gcd
  16. #define all(v) v.begin(),v.end()
  17. #define allr(v) v.rbegin(),v.rend()
  18. #define acc(x) accumulate(all(x),0LL)
  19. #define fixed(n) fixed << setprecision(n)
  20. #define ll long long
  21. #define digits(n) ((int)log10(n) + 1)
  22. #define ull unsigned long long
  23. #define all(v) v.begin(),v.end()
  24. #define mod 1000000007
  25. #define mx(v) *max_element(all(v))
  26. #define mn(v) *min_element(all(v))
  27. #define mxi(v) max_element(all(v))-v.begin()
  28. #define mni(v) min_element(all(v))-v.begin()
  29. #define tolow(pp) transform(all(pp),pp.begin(),::tolower)
  30. #define toup(pp) transform(all(pp),pp.begin(),::toupper)
  31. #define cin(vec) for(auto &i : vec) cin >> i
  32. #define cout(vec) for(auto& i : vec) cout << i << " "; cout << '\n';
  33. bool isPowerOfTwo(ll n) {if (n==0)return 0;return !(n&(n-1));}
  34. ll fact(ll n){ll temp = 1;for (ll i = 2; i <= n; i++)temp = temp * i;return temp;}
  35. ll nCr(ll n, ll r){return fact(n) / (fact(r) * fact(n - r));}
  36. ll nPr(ll n,ll r){return fact(n)/ fact(n-r);}
  37. ll lcm(ll a,ll b){return (a/gcd(a,b))*b;}
  38. ll sumFrom1ToN(int n) { return (ll)n * (n + 1) / 2; }
  39. ll sumFromAtoB(ll a, ll b) { return (max(a, b) - min(a, b) + 1) * (a + b) / 2; }
  40. bool comparePairs(const pair<int, int>& a, const pair<int, int>& b) {return a.first < b.first;}
  41. #define ordered_set tree<int,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update>
  42. typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
  43. #define ll long long
  44. void myerase(ordered_set &t, int v){
  45.     int rank = t.order_of_key(v);//Number of elements that are less than v in t
  46.     ordered_set::iterator it = t.find_by_order(rank); //Iterator that points to the (rank+1)th element in t
  47.     t.erase(it);
  48. }
  49. /*
  50.  ██████╗ ██████╗ ██████╗ ███████╗    ███████╗████████╗ █████╗ ██████╗ ████████╗    ██╗  ██╗███████╗██████╗ ███████╗
  51. ██╔════╝██╔═══██╗██╔══██╗██╔════╝    ██╔════╝╚══██╔══╝██╔══██╗██╔══██╗╚══██╔══╝    ██║  ██║██╔════╝██╔══██╗██╔════╝
  52. ██║     ██║   ██║██║  ██║█████╗      ███████╗   ██║   ███████║██████╔╝   ██║       ███████║█████╗  ██████╔╝█████╗
  53. ██║     ██║   ██║██║  ██║██╔══╝      ╚════██║   ██║   ██╔══██║██╔══██╗   ██║       ██╔══██║██╔══╝  ██╔══██╗██╔══╝
  54. ╚██████╗╚██████╔╝██████╔╝███████╗    ███████║   ██║   ██║  ██║██║  ██║   ██║       ██║  ██║███████╗██║  ██║███████╗
  55.  ╚═════╝ ╚═════╝ ╚═════╝ ╚══════╝    ╚══════╝   ╚═╝   ╚═╝  ╚═╝╚═╝  ╚═╝   ╚═╝       ╚═╝  ╚═╝╚══════╝╚═╝  ╚═╝╚══════╝
  56. */
  57. const int N=200005;
  58. const int Q=200005;
  59. const int SQ=449;
  60. void compress(vector<ll>&a,int start)
  61. {
  62.     int n=a.size();
  63.     vector<pair<ll,ll>>pairs(n);
  64.     for(int i=0;i<n;i++)
  65.     {
  66.         pairs[i]={a[i],i};
  67.     }
  68.     sort(pairs.begin(),pairs.end());
  69.     int nxt=start;
  70.     for(int i=0;i<n;i++)
  71.     {
  72.         if(i>0&&pairs[i-1].first!=pairs[i].first)
  73.         {
  74.             nxt++;
  75.         }
  76.         a[pairs[i].second]=nxt;
  77.     }
  78. }
  79. struct query{
  80.     int l,r,q_idx,block_idx;
  81.     query(){}
  82.     query(int _l,int _r,int _q_idx)
  83.     {
  84.         l=_l-1,r=_r-1,q_idx=_q_idx,block_idx=_l/SQ;
  85.     }
  86.     bool operator<(const query&y)const{
  87.         if(block_idx!=y.block_idx)
  88.         {
  89.             return block_idx<y.block_idx;
  90.         }
  91.         return r<y.r;
  92.     }
  93. };
  94. ll n,q,s[N],res=0,q_ans[Q],f[N],ff[N];int mx=0;
  95.  
  96. vector<ll>arr(N);
  97. query queries[Q];
  98. void add(int i)
  99. {
  100.    f[arr[i]]++;
  101.    if(f[arr[i]]==1)res++;
  102. }
  103. void remove(int i)
  104. {
  105.    if(f[arr[i]]==1)res--;
  106.    f[arr[i]]--;
  107. }
  108. void MO_process()
  109. {
  110.     sort(queries,queries+q);
  111.     int l=1,r=0;
  112.     for(int i=0;i<q;i++)
  113.     {
  114.         while(r<queries[i].r)add(++r);
  115.         while(r>queries[i].r)remove(r--);
  116.         while(l<queries[i].l)remove(l++);
  117.         while(l>queries[i].l)add(--l);
  118.         q_ans[queries[i].q_idx]=res;
  119.     }
  120. }
  121. void sonic444() {
  122. //The stupidest code you will ever see
  123. //The stupidest code you will ever see
  124.  
  125.     cin>>n>>q;
  126.     arr.resize(n);
  127.     cin(arr);
  128.     compress(arr,0);
  129.     for (int i = 0; i < q; ++i) {
  130.         ll l,r;cin>>l>>r;
  131.         queries[i]=query(l,r,i);
  132.     }
  133.     MO_process();
  134.     for (int i = 0; i < q; ++i) {
  135.         cout<<q_ans[i]<<endl;
  136.     }
  137.  
  138. }
  139.  
  140. int main() {
  141.     // freopen("input1.txt", "r", stdin);
  142.     //    freopen("output.txt", "w", stdout);
  143.     sonic
  144.     //////////////////////////////////////////////
  145.  
  146.     int t=1;//cin>>t;
  147.     while (t--){
  148.         sonic444();
  149.     }
  150.     return 0;
  151. }
Success #stdin #stdout 0.01s 6616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DgUc64
language:
C++ (gcc 8.3)
created:
15 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!