fork download 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3. /*
  4. Time complexity:
  5. BS = ?
  6. cntB = n / BS
  7.  
  8. GET: O = cntB * log2(1e4) + BS;
  9. UPDATE: log(1e4) + 1;
  10. minimize GET:
  11. (a + b >= 2√(ab))
  12. ->  O >= 2√(cntB * log2(1e4) * BS)
  13. -> cntB * log2(1e4) = BS
  14. -> n/BS * log2(1e4) = BS
  15. -> n * log2(1e4) = BS ^ 2;
  16.  
  17. Vì vậy BS = √(n * log2(1e4))
  18. */
  19. #define ft first
  20. #define sc second
  21. const int N = 1e5 + 5;
  22. const int LIM = 1e4 + 5;
  23. const int BS = 1153;
  24. int n, a[N], q;
  25. int bit[N / BS + 1][LIM];
  26. int blockId[N];
  27. void updateBit(int i, int id, int t) {
  28.     for (; id > 0; id -= id &- id) bit[i][id] += t;
  29. }
  30. void process() {
  31.     for (int i = 1; i <= n; i++) blockId[i] = (i - 1) / BS;
  32.     for (int i = 1; i <= n; i++) updateBit(blockId[i], a[i], 1);
  33. }
  34. int getBit(int i, int id) {
  35.     int ans = 0;
  36.     for (; id < LIM; id += id &- id) ans += bit[i][id];
  37.     return ans;
  38. }
  39. int getQuery(int l, int r, int k) {
  40.     int L = blockId[l], R = blockId[r];
  41.     int ans = 0;
  42.     if (L >= R) {
  43.         for (int i = l; i <= r; i++) ans += (a[i] > k);
  44.         return ans;
  45.     }
  46.     for (int i = L + 1; i < R; i++) ans += getBit(i, k + 1);
  47.     for (int i = l; i <= (L + 1) * BS; i++) ans += (a[i] > k);
  48.     for (int i = R * BS + 1; i <= r; i++) ans += (a[i] > k);
  49.     return ans;
  50. }
  51. signed main() {
  52.     cin.tie(NULL)->sync_with_stdio(false);
  53.     if(ifstream("KQUERY.inp")) {
  54.         freopen("KQUERY.inp", "r", stdin);
  55.         freopen("KQUERY.out", "w", stdout);
  56.     }
  57.     cin >> n;
  58.     for (int i = 1; i <= n; i++) cin >> a[i];
  59.     process();
  60.     cin >> q;
  61.     while(q--) {
  62.         char type; cin >> type;
  63.         if (type == 'Q') {
  64.             int l, r, k; cin >> l >> r >> k;
  65.             cout << getQuery(l, r, k) << "\n";
  66.         }
  67.         else {
  68.             int i, x; cin >> i >> x;
  69.             updateBit(blockId[i], a[i], -1);
  70.             a[i] = x;
  71.             updateBit(blockId[i], a[i], 1);
  72.         }
  73.     }
  74.     return 0;
  75. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/PCHEYi
language:
C++14 (gcc 8.3)
created:
3 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!