fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl     '\n' 
  4. #define ff        first
  5. #define ss        second
  6. #define ins      insert
  7. #define pb       push_back
  8. #define eb       emplace_back
  9. #define sz(x)    int((x).size())
  10. #define all(x)   begin(x), end(x)
  11. typedef long long ll;
  12. typedef unsigned long long ull;
  13. #define forn(i, n) for (int i = 0; i < n; ++i)
  14. #define each(i, x) for (auto &&i : x)
  15. #define forne(i,x,n) for (int i = x; i < n; ++i)
  16. #define show(x) for (auto &&i : x) {cerr << i <<' ';} cerr<< endl;
  17.  
  18.  
  19. void dbg_out() { cerr << ']' << endl; }
  20. template<typename Head, typename... Tail>
  21. void dbg_out(Head H, Tail... T) { cerr << H;if (sizeof...(T)) cerr << ',' << ' '; dbg_out(T...); }
  22. #ifdef LOCAL 
  23. #define dbg(...) cerr << '|' << __LINE__ << '|'<< '{' << #__VA_ARGS__ << '}'<<':'<<' '<<'[', dbg_out(__VA_ARGS__)
  24. #else
  25. #define dbg(...)
  26. #endif
  27. #define int int64_t
  28. #define ii pair<int,int>
  29.  
  30. constexpr int mxN = 2 * 1e5 + 100;
  31. int n, m, ans;
  32. vector<int>nums;
  33. int cnt[mxN];
  34.  
  35. void add(int x) {
  36.     if (++cnt[nums[x]] == 1) ans++;
  37. }
  38. void del(int x) {
  39.     if (--cnt[nums[x]] == 0) ans--;
  40. }
  41. int get_ans() {
  42.     return ans;
  43. }
  44.  
  45. vector<int> mo(const vector<ii>& q) {
  46.     int l = 0, r = -1, blk = 350; // sqrt(n)
  47.     vector<int> inx(sz(q)), ans(sz(q));
  48.     auto K = [&](const ii& x) -> ii {
  49.         return ii(x.ff / blk, x.ss ^ -(x.ff / blk & 1));
  50.         };
  51.     iota(all(inx), 0);
  52.     sort(all(inx), [&](int a, int b) -> bool {
  53.         return K(q[a]) < K(q[b]);
  54.         });
  55.     for (int nxt : inx) {
  56.         ii it = q[nxt];
  57.         while (r < it.ss) add(++r);
  58.         while (l > it.ff) add(--l);
  59.         while (r > it.ss) del(r--);
  60.         while (l < it.ff) del(l++);
  61.         ans[nxt] = get_ans();
  62.     }
  63.     return ans;
  64. }
  65.  
  66. template<typename T>
  67. struct COO_COMPRESS {
  68.     vector<T> nums;
  69.     bool is_compress = true;
  70.  
  71.     int size() {
  72.         if (!is_compress) compress();
  73.         return sz(nums);
  74.     }
  75.  
  76.     void clear() {
  77.         nums.clear();
  78.         is_compress = true;
  79.     }
  80.  
  81.     void insert(T x) {
  82.         nums.pb(x);
  83.         is_compress = false;
  84.     }
  85.  
  86.     void compress() {
  87.         sort(all(nums));
  88.         nums.resize(unique(all(nums)) - nums.begin());
  89.         is_compress = true;
  90.     }
  91.  
  92.     vector<T> compress_offline(vector<T> nums) {
  93.         if (!sz(nums))return nums;
  94.         vector<pair<T, int>> vvv;
  95.         forn(i, sz(nums)) vvv.pb({ nums[i],i });
  96.         sort(all(vvv));
  97.         int cont = 0;
  98.         T last = vvv[0].first;
  99.         nums[vvv[0].second] = 0;
  100.         forne(i, 1, sz(vvv)) {
  101.             if (vvv[i].first != last) cont++, last = vvv[i].first;
  102.             nums[vvv[i].second] = cont;
  103.         }
  104.         return nums;
  105.     }
  106.  
  107.     int get(T x) {
  108.         if (!is_compress) compress();
  109.         int pos = lower_bound(all(nums), x) - nums.begin();
  110.         assert(pos != sz(nums) && nums[pos] == x);
  111.         return pos;
  112.     }
  113.  
  114.     T iget(int x) {
  115.         if (!is_compress) compress();
  116.         assert(0 <= x && x < sz(nums));
  117.         return nums[x];
  118.     }
  119. };
  120.  
  121.  
  122. main() {
  123.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  124.  
  125.     cin >> n >> m;
  126.     nums = vector<int>(n);
  127.     COO_COMPRESS<int>com;
  128.     forn(i, n) cin >> nums[i], com.insert(nums[i]);
  129.  
  130.     vector<ii> qry(m);
  131.     forn(i, m) {
  132.         int x, y; cin >> x >> y;
  133.         x--, y--;
  134.         qry[i] = { x,y };
  135.     }
  136.  
  137.     forn(i, n) nums[i] = com.get(nums[i]);
  138.     // show(nums);
  139.  
  140.     auto ans = mo(qry);
  141.  
  142.     each(i, ans) cout << i << endl;
  143.  
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.     cout << flush;
  157.     return 0;
  158. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RXZHHy
language:
C++14 (gcc 8.3)
created:
6 days 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!