fork(1) download 
  1. // Hint: Don't look, No need, Let'em Play.
  2. #pragma GCC optimize("O2")
  3. #include <bits/stdc++.h>
  4. #include "bits/stdc++.h"
  5.  
  6. using namespace std;
  7.  
  8. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  9.  
  10. #ifndef bhupixb
  11.     #define var(...)
  12.     #define stl(...)
  13. #endif
  14.  
  15. #define single_test
  16.  
  17. using pi = pair<int,int>;
  18. vector<vector<pair<int,int>>> v;
  19.  
  20. int n, q;
  21. const int N = 1e5 + 3;
  22. const int mx = 320; // size of block
  23. vector<int> a, block;
  24.  
  25. void upd(int pos, int val) {
  26.     a[pos] = val;
  27.     int found = -1;
  28.     int cur_block = block[pos];
  29.     const int x = v[cur_block].size();
  30.     for (int i = 0; i < x; ++i) {
  31.         if (v[cur_block][i].second == pos) {
  32.             if (v[cur_block][i].first == val) {
  33.                 return;
  34.             }
  35.             found = i;
  36.             break;
  37.         }
  38.     }
  39.     assert(found != -1);
  40.     if (val > v[cur_block][found].first) {
  41.         v[cur_block][found].first = val;
  42.         while (found + 1 < x && val > v[cur_block][found + 1].first) {
  43.             swap(v[cur_block][found], v[cur_block][found + 1]);
  44.             ++found;
  45.         }
  46.     }
  47.     else {
  48.         v[cur_block][found].first = val;
  49.         while (found > 0 && val < v[cur_block][found - 1].first) {
  50.             swap(v[cur_block][found], v[cur_block][found - 1]);
  51.             --found;
  52.         }
  53.     }
  54. }
  55.  
  56. int query(int l, int r, int k) {
  57.     int ans = 0;
  58.     for (int i = l; i <= r; ++i) {
  59.         ans += a[i] <= k;
  60.     }
  61.     return ans;
  62. }
  63.  
  64. int query_bs(int l, int r, int k) {
  65.     int ans = 0;
  66.     for (int i = l; i <= r; ++i) {
  67.         assert(!v[i].empty());
  68.         int lo = 0, hi = (int)v[i].size() - 1, mid, c = 0;
  69.         while (lo <= hi) {
  70.             mid = (lo + hi) >> 1;
  71.             if (v[i][mid].first <= k) {
  72.                 lo = mid + 1;
  73.                 c = mid + 1;
  74.             }
  75.             else {
  76.                 hi = mid - 1;
  77.             }
  78.         }
  79.         ans += c;
  80.     }
  81.     return ans;
  82. }
  83.  
  84. void solve() {
  85.     cin >> n >> q;
  86.     a.resize(n + 1);
  87.     block.resize(n + 1);
  88.     for (int i = 1; i <= n; ++i) {
  89.         cin >> a[i];
  90.     }
  91.     int cur = 0, sz = 0;
  92.     for (int i = 1; i <= n; ++i) {
  93.         block[i] = cur;
  94.         ++sz;
  95.         if (sz == mx) sz = 0, ++cur;
  96.     }
  97.     v.resize(block[n] + 1);
  98.     for (int i = 1; i <= n; ) {
  99.         cur = i;
  100.         sz = 0;
  101.         while (i <= n && block[i] == block[cur]) {
  102.             ++i;
  103.             ++sz;
  104.         }
  105.         int cur_block = block[cur];
  106.         v[cur_block].resize(sz);
  107.         var(sz, cur_block);
  108.         int idx = 0;
  109.         while (sz--) {
  110.             v[cur_block][idx] = {a[cur], cur};
  111.             ++idx;
  112.             cur += 1;
  113.         }
  114.         sort(v[cur_block].begin(), v[cur_block].end());
  115.     }
  116.     for (int i = 0; i < (int)v.size(); ++i) {
  117.         stl(v[i]);
  118.     }
  119.     stl(a);
  120.     int l, r, k, pos, val;
  121.     while (q--) {
  122.         char type;
  123.         cin >> type;
  124.         if (type == 'C') {
  125.             cin >> l >> r >> k;
  126.             if (block[l] == block[r]) {
  127.                 cout << query(l, r, k) << '\n';
  128.             }
  129.             else {
  130.                 int ans = query_bs(block[l] + 1, block[r] - 1, k);
  131.                 int x = l;
  132.                 while (x <= n && block[x] == block[l]) {
  133.                     ans += a[x] <= k;
  134.                     ++x;
  135.                 }
  136.                 x = r;
  137.                 while (x > 0 && block[x] == block[r]) {
  138.                     ans += a[x] <= k;
  139.                     --x;
  140.                 }
  141.                 cout << ans << '\n';
  142.             }
  143.         }
  144.         else {
  145.             cin >> pos >> val;
  146.             upd(pos, val);
  147.         }
  148.     }
  149. }
  150.  
  151. signed main() {
  152.     fast;
  153.     int t = 1;
  154.     #ifndef single_test
  155.         cin >> t;
  156.     #endif
  157.     while (t--) {
  158.         solve();
  159.     }
  160.  
  161.     return 0;
  162. }
Success #stdin #stdout 0s 4468KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/J64Vpd
language:
C++14 (gcc 8.3)
created:
4 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!