fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ft first
  4. #define sc second
  5. #define el '\n'
  6. #define boost ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  7. #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout)
  8. #define pb push_back
  9. #define all(x) (x).begin(),(x).end()
  10. using namespace std;
  11. const ll N = 1e6;
  12. ll n, q, block, cnt = 0, a[N + 1], ans[N + 1], blockCnt[N + 1];
  13. vector<ll> b;
  14.  
  15. ll binary(ll k) {
  16.     ll l = 1, r = b.size() - 1, ans = 0;
  17.     while(l <= r) {
  18.         ll mid = (l + r) >> 1;
  19.         if(b[mid] <= k) {
  20.             l = mid + 1;
  21.             ans = mid;
  22.         } else {
  23.             r = mid - 1;
  24.         }
  25.     }
  26.  
  27.     return ans;
  28. }
  29.  
  30. struct QUERY {
  31.     ll x, y, z;
  32. };
  33.  
  34. vector<QUERY> query;
  35.  
  36. void read() {
  37.     cin >> n >> q;
  38.     block = sqrt(n);
  39.     b.pb(0);
  40.  
  41.     for(ll i = 1; i <= n; i ++) {
  42.         cin >> a[i];
  43.         b.pb(a[i]);
  44.     }
  45.  
  46.     sort(b.begin() + 1, b.end());
  47.     b.erase(unique(b.begin() + 1, b.end()), b.end());
  48.  
  49.     for(ll i = 1; i <= n; i ++) {
  50.         a[i] = binary(a[i]);
  51.     }
  52.  
  53.     for(ll i = 1; i <= q; i ++) {
  54.         ll l, r; cin >> l >> r;
  55.         query.pb({l, r, i});
  56.     }
  57.  
  58.     sort(all(query), [](QUERY &x, QUERY &y) {
  59.         ll rx = x.x / block;
  60.         ll ry = y.x / block;
  61.  
  62.         if(rx != ry) return rx < ry;
  63.         else {
  64.             if(rx % 2) return x.y < y.y;
  65.             return x.y > y.y;
  66.         }
  67.     });
  68.  
  69. }
  70.  
  71. void add(ll k) { 
  72.     blockCnt[a[k]] ++;
  73.     if(blockCnt[a[k]] == 2) cnt ++;
  74.     if(blockCnt[a[k]] == 3) cnt --;
  75. }
  76.  
  77. void remove(ll k) {
  78.     blockCnt[a[k]] --;
  79.     if(blockCnt[a[k]] == 2) cnt ++;
  80.     if(blockCnt[a[k]] == 1) cnt --;
  81. }
  82.  
  83. void solve() {
  84.     ll curL = 1, curR = 0;
  85.     for(auto [i, j, k] : query) {
  86.         while(curL > i) add(-- curL);
  87.         while(curL < i) remove(curL ++);
  88.         while(curR > j) remove(curR --);
  89.         while(curR < j) add(++ curR);
  90.  
  91.         ans[k] = cnt;
  92.     }
  93.  
  94.     for(ll i = 1; i <= q; i ++) cout << ans[i] << el;
  95. }
  96.  
  97. void write() {
  98.  
  99. }
  100.  
  101. int main() {
  102.     boost;
  103.     //file();
  104.     read();
  105.     solve();
  106.     write();
  107.     return 0;
  108. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7mQYe7
language:
C++14 (gcc 8.3)
created:
11 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!