fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool memory1;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7. typedef double dbe;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<ll> vll;
  10.  
  11. #define openFile(name) freopen((name ".inp"), "r", stdin), freopen((name ".out"), "w", stdout)
  12. #define FOR(i, a, b, x) for (ll i = (a); i <= (b); i += (x))
  13. #define ROF(i, a, b, x) for (ll i = (a); i >= (b); i += (x))
  14. #define fi first
  15. #define se second
  16. #define MASK(x) (1LL << (x))
  17. #define getBit(mask, i) (((mask) >> (i)) & 1)
  18. #define BitOn(mask) (__builtin_popcountll(mask))
  19.  
  20. const int maxN = 2e5 + 5e4 + 2;
  21. const ll LOG = 20;
  22. const ll INF18 = 1e18;
  23. const int INF9 = 1e9;
  24. const ll MOD = 1e9 + 7;
  25.  
  26. //////////////////////////////////////////////
  27. /////////////////nhan0123456//////////////////
  28. //////////////////////////////////////////////
  29. const ll BL = 500;
  30. const ll MAXVAL = 5e4 + 5;
  31.  
  32. struct BIT {
  33.     vll b;
  34.     ll n;
  35.     void sz(ll _) {
  36.         n = _;
  37.         b.assign(n + 2, 0);
  38.     }
  39.     void update(ll i, ll val = 1) {
  40.         for (; i <= n; i += i & -i) b[i] += val;
  41.     }
  42.     ll get(ll i) {
  43.         ll ans = 0;
  44.         for (; i > 0; i -= i & -i) ans += b[i];
  45.         return ans;
  46.     }
  47.     ll get(ll l, ll r) {
  48.         return get(r) - get(l - 1);
  49.     }
  50. };
  51.  
  52. ll n, q;
  53. ll a[maxN];
  54. ll block[maxN];
  55. BIT bit[BL + 2];
  56. ll block_cnt;
  57. ll block_start[BL + 2], block_end[BL + 2];
  58.  
  59. ll getBlock(ll i) {
  60.     return (i - 1) / BL + 1;
  61. }
  62.  
  63. void initBlock() {
  64.     block_cnt = getBlock(n);
  65.     FOR (i, 1, n, 1) block[i] = getBlock(i);
  66.     FOR (i, 1, block_cnt, 1) {
  67.         block_start[i] = (i - 1) * BL + 1;
  68.         block_end[i] = min(n, i * BL);
  69.         bit[i].sz(MAXVAL);
  70.     }
  71.     FOR (i, 1, n, 1) bit[block[i]].update(a[i]);
  72. }
  73.  
  74. ll Calc1(ll x, ll val) {
  75.     ll res = 0;
  76.     FOR (b, 1, block[x] - 1, 1) {
  77.         res += bit[b].get(val + 1, MAXVAL);
  78.     }
  79.     FOR (i, block_start[block[x]], x - 1, 1) {
  80.         if (a[i] > val) ++res;
  81.     }
  82.     return res;
  83. }
  84.  
  85. ll Calc2(ll x, ll val) {
  86.     ll res = 0;
  87.     FOR (b, block[x] + 1, block_cnt, 1) {
  88.         res += bit[b].get(1, val - 1);
  89.     }
  90.     FOR (i, x + 1, block_end[block[x]], 1) {
  91.         if (a[i] < val) ++res;
  92.     }
  93.     return res;
  94. }
  95.  
  96. ll Solve() {
  97.     ll S = 0;
  98.     BIT all; all.sz(MAXVAL);
  99.     ROF (i, n, 1, -1) {
  100.         S += all.get(a[i] - 1);
  101.         all.update(a[i]);
  102.     }
  103.  
  104.     cin >> q;
  105.     while (q--) {
  106.         ll x, y;
  107.         cin >> x >> y;
  108.         S -= Calc1(x, a[x]) + Calc2(x, a[x]);
  109.         bit[block[x]].update(a[x], -1);
  110.         a[x] = y;
  111.         bit[block[x]].update(a[x], +1);
  112.         S += Calc1(x, a[x]) + Calc2(x, a[x]);
  113.         cout << S << "\n";
  114.     }
  115.  
  116.     return 0;
  117. }
  118.  
  119. void input() {
  120.     cin >> n >> q;
  121.     FOR (i, 1, n, 1) cin >> a[i];
  122.     initBlock();
  123.     Solve();
  124. }
  125.  
  126. int main() {
  127.     //openFile("temp");
  128.     ios_base::sync_with_stdio(0);
  129.     cin.tie(0);
  130.     input();
  131.  
  132.     //bool memory2;
  133.     //cerr << "\n\n\nTime: "<< 1000.0 * clock() / CLOCKS_PER_SEC << " ms";
  134.     //cerr << "\n\n\nMemory: "<< abs(&memory1 - &memory2) * 1.0 / MASK(20) <<" MB";
  135.  
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NZSpdP
language:
C++ (gcc 8.3)
created:
10 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!