fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // #define int long long
  4. const int maxn = 3e4 + 5;
  5. #define fastIO                        \
  6.     ios_base::sync_with_stdio(false); \
  7.     cin.tie(0);                       \
  8.     cout.tie(0);
  9. #define File(_x, _y)    \
  10.     if (fopen(_x, "r")) \
  11.     freopen(_x, "r", stdin), freopen(_y, "w", stdout)
  12. #define file "main"
  13.  
  14. int n, m, block, res, t;
  15. int a[maxn], get_max[176];
  16. const int maxqrt = 176;
  17.  
  18. const int N = 10001;
  19. int T[maxqrt][N];
  20.  
  21. void update(int p, int v, int b)
  22. {
  23.     while (p < N)
  24.         T[b][p] += v, p += p & (-p);
  25. }
  26.  
  27. int get(int p, int b)
  28. {
  29.     int res = 0;
  30.     while (p > 0)
  31.         res += T[b][p], p -= p & (-p);
  32.     return res;
  33. }
  34.  
  35. int main()
  36. {
  37.     fastIO;
  38.     File(file ".inp", file ".out");
  39.  
  40.     int MX = 0;
  41.     cin >> n;
  42.     while (block * block < n)
  43.         block++;
  44.  
  45.     for (int i = 1; i <= n; i++)
  46.     {
  47.         cin >> a[i];
  48.         update(a[i], 1, i / block);
  49.         get_max[i / block]++;
  50.     }
  51.  
  52.     cin >> t;
  53.     for (int i = 1; i <= t; i++)
  54.     {
  55.         int tp;
  56.         cin >> tp;
  57.         int l, r, k;
  58.  
  59.         if (tp == 0)
  60.         {
  61.             cin >> l >> r;
  62.             update(a[l], -1, l / block);
  63.             update(r, 1, l / block);
  64.             a[l] = r;
  65.         }
  66.         else
  67.         {
  68.             cin >> l >> r >> k;
  69.             int sum = 0;
  70.             int l_block = l / block;
  71.             int r_block = r / block;
  72.  
  73.             if (l_block == r_block)
  74.             {
  75.                 for (int j = l; j <= r; ++j)
  76.                     sum += (a[j] > k);
  77.             }
  78.             else
  79.             {
  80.                 for (int j = l; j < (l_block + 1) * block; j++)
  81.                     sum += (a[j] > k);
  82.  
  83.                 for (int j = r_block * block; j <= r; j++)
  84.                     sum += (a[j] > k);
  85.  
  86.                 for (int j = l_block + 1; j < r_block; j++)
  87.                     sum += get_max[j] - get(k, j);
  88.             }
  89.  
  90.             cout << sum << '\n';
  91.         }
  92.     }
  93.  
  94.     return 0;
  95. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KnbN7H
language:
C++14 (clang 8.0)
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!