Submission #3222684

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const auto& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

struct M {
  using T = array<lint, 3>;
  static T op(const T& a, const T& b) { return {min(a[0], b[0]), max(a[1], b[1]), a[2] + b[2]}; }
  static constexpr T e() { return {numeric_limits<lint>::max(), numeric_limits<lint>::min(), 0}; }
  static T mk(lint a) { return {a, a, a}; }
};

template<class M> struct ST {
  using T = typename M::T;
  int n;
  V<T> t;

  ST(int n) : n(n) {
    t.assign(2 * n, M::e());
  }

  void build() {
    for (int i = n - 1; i; i--) t[i] = M::op(t[2 * i], t[2 * i + 1]);
  }

  T get(int l, int r) {
    T resl = M::e(), resr = M::e();
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) { 
      if (l & 1) resl = M::op(resl, t[l++]); 
      if (r & 1) resr = M::op(t[--r], resr);
    }
    return M::op(resl, resr);
  }

  T get(int i) { return t[i + n]; };

  void set(int i, const T& a) {
    for (t[i += n] = a; i >>= 1;) t[i] = M::op(t[2 * i], t[2 * i + 1]);
  }
};

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n, q; cin >> n >> q;
  V<> a(2 * n); for (int i = 0; i < 2 * n; i++) cin >> a[i];
  V<> b(2 * n); for (int i = 0; i < 2 * n; i++) cin >> b[i];
  lint sa = accumulate(a.begin(), a.end(), 0LL);
  ST<M> pos(2 * n), neg(2 * n);
  int cp = 0;
  for (int i = 1; i < 2 * n - 1; i++) (b[i] - a[i] >= 0 ? cp++, pos : neg).t[i + 2 * n] = M::mk(b[i] - a[i]);
  pos.build(), neg.build();
  for (int iq = 0; iq < q; iq++) {
    int p, x, y; cin >> p >> x >> y, p--;
    if (p and p < 2 * n - 1) {
      if (y - x >= 0) {
        pos.set(p, M::mk(y - x));
        neg.set(p, M::e());
        cp += (b[p] - a[p] < 0);
      } else {
        neg.set(p, M::mk(y - x));
        pos.set(p, M::e());
        cp -= (b[p] - a[p] >= 0);
      }
    }
    sa += x - a[p];
    a[p] = x, b[p] = y;
    lint s = pos.get(1, 2 * n - 1)[2];
    if (cp & 1) {
      s -= min(pos.get(1, 2 * n - 1)[0], -neg.get(1, 2 * n - 1)[1]);
    }
    cout << sa + s << '\n';
  }
}

Submission Info

Judge Result