Advertisement
Guest User

Untitled

a guest
Dec 29th, 2019
432
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <iomanip>
  11. #include <fstream>
  12. #include <cassert>
  13. #include <cstring>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <numeric>
  17. #include <ctime>
  18. #include <bitset>
  19. #include <complex>
  20. #include <random>
  21. #include <functional>
  22.  
  23. using namespace std;
  24.  
  25. const int MAXN = 2e6 + 1;
  26. const int INF = 1e9 + 239;
  27.  
  28. namespace ST {
  29.     int t[4 * MAXN];
  30.     int cnt[4 * MAXN];
  31.     int mod[4 * MAXN];
  32.  
  33.     void pull(int v) {
  34.         if (t[2 * v + 1] < t[2 * v + 2]) {
  35.             t[v] = t[2 * v + 1];
  36.             cnt[v] = cnt[2 * v + 1];
  37.         } else if (t[2 * v + 1] > t[2 * v + 2]) {
  38.             t[v] = t[2 * v + 2];
  39.             cnt[v] = cnt[2 * v + 2];
  40.         } else {
  41.             t[v] = t[2 * v + 1];
  42.             cnt[v] = cnt[2 * v + 1] + cnt[2 * v + 2];
  43.         }
  44.     }
  45.  
  46.     void apply(int v, int x) {
  47.         t[v] += x;
  48.         mod[v] += x;
  49.     }
  50.  
  51.     void push(int v) {
  52.         if (mod[v] != 0) {
  53.             apply(2 * v + 1, mod[v]);
  54.             apply(2 * v + 2, mod[v]);
  55.             mod[v] = 0;
  56.         }
  57.     }
  58.  
  59.     void modify(int v, int l, int r, int ql, int qr, int val) {
  60.         if (qr <= l || r <= ql) {
  61.             return;
  62.         } else if (ql <= l && r <= qr) {
  63.             apply(v, val);
  64.         } else {
  65.             push(v);
  66.             int m = (r + l) >> 1;
  67.             modify(2 * v + 1, l, m, ql, qr, val);
  68.             modify(2 * v + 2, m, r, ql, qr, val);
  69.             pull(v);
  70.         }
  71.     }
  72.  
  73.     int cntmn() {
  74.         return cnt[0];
  75.     }
  76.  
  77.     void build(int v, int l, int r) {
  78.         if (l + 1 == r) {
  79.             cnt[v] = 1;
  80.         } else {
  81.             int m = (r + l) >> 1;
  82.             build(2 * v + 1, l, m);
  83.             build(2 * v + 2, m, r);
  84.             pull(v);
  85.         }
  86.     }
  87.  
  88.     void init() {
  89.         fill(t, t + 4 * MAXN, 0);
  90.         fill(cnt, cnt + 4 * MAXN, 0);
  91.         fill(mod, mod + 4 * MAXN, 0);
  92.         build(0, 0, MAXN);
  93.     }
  94.    
  95.     void add(int l, int r, int c) {
  96.         r++;
  97.         modify(0, 0, MAXN, l, r, c);
  98.     }
  99. }
  100.  
  101. void zip(vector<int> &a, vector<pair<int, int>> &qr) {
  102.     vector<int> sn = a;
  103.     for (auto [f, s] : qr) {
  104.         sn.push_back(s);
  105.     }
  106.     sort(sn.begin(), sn.end());
  107.     for (auto &t : a) {
  108.         t = 2 * (lower_bound(sn.begin(), sn.end(), t) - sn.begin() + 1);
  109.     }
  110.     for (auto &[f, t] : qr) {
  111.         t = 2 * (lower_bound(sn.begin(), sn.end(), t) - sn.begin() + 1);
  112.     }
  113. }
  114.  
  115. vector<int> my(int n, vector<int> a, vector<pair<int, int>> qr) {
  116.     ST::init();
  117.     zip(a, qr);
  118.     a.insert(a.begin(), MAXN - 1);
  119.     a.push_back(0);
  120.     n += 2;
  121.     auto add = [&](int i, int c) {
  122.         int f = a[i];
  123.         int s = a[i + 1];
  124.         if (f > s) {
  125.             swap(f, s);
  126.         }
  127.         ST::add(f, s, c);
  128.     };
  129.     auto add_scaner = [&](int val) {
  130.         ST::add(val, val, -INF);
  131.     };
  132.     auto kill_scaner = [&](int val) {
  133.         ST::add(val, val, INF);
  134.     };
  135.     auto solve = [&]() {
  136.         return ST::cntmn();
  137.     };
  138.     for (int i = 0; i < MAXN; i++) {
  139.         kill_scaner(i);
  140.     }
  141.     for (int i = 1; i + 1 < n; i++) {
  142.         add_scaner(a[i] - 1);
  143.     }
  144.     for (int i = 0; i + 1 < n; i++) {
  145.         add(i, 1);
  146.     }
  147.     vector<int> res;
  148.     for (auto [pos, x] : qr) {
  149.         pos++;
  150.         add(pos - 1, -1);
  151.         add(pos, -1);
  152.         kill_scaner(a[pos] - 1);
  153.         a[pos] = x;
  154.         add(pos - 1, 1);
  155.         add(pos, 1);
  156.         add_scaner(a[pos] - 1);
  157.         res.push_back(solve());
  158.     }
  159.     return res;
  160. }
  161.  
  162. void read() {
  163.     int n, q;
  164.     cin >> n >> q;
  165.     vector<int> a(n);
  166.     for (auto &t : a) {
  167.         cin >> t;
  168.     }
  169.     vector<pair<int, int>> qr(q);
  170.     for (auto &[pos, x] : qr) {
  171.         cin >> pos >> x;
  172.         pos--;
  173.     }
  174.     auto ans = my(n, a, qr);
  175.     for (auto t : ans) {
  176.         cout << t << ' ';
  177.     }
  178.     cout << endl;
  179. }
  180.  
  181. signed main() {
  182.     ios_base::sync_with_stdio(false);
  183.     cin.tie(0);
  184.  
  185.     read();
  186. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement