提出 #55828915

---

ソースコード 拡げる

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <set>
#include <type_traits>
#include <utility>
#include <vector>

namespace noshi91 {

template <class T, class Comp> class partially_retroactive_priority_queue {
public:
  struct return_type {
    std::vector<T> insert;
    std::vector<T> erase;
  };

private:
  int n, m;
  Comp comp;
  struct node {
    int ssum, smin;
    T qmax, dmin;
  };
  std::vector<node> tree;

  const T &min_op(const T &x, const T &y) { return comp(x, y) ? x : y; }
  const T &max_op(const T &x, const T &y) { return comp(x, y) ? y : x; }

  void update_s(int i) {
    while (i /= 2) {
      tree[i].ssum = tree[i << 1].ssum + tree[i << 1 | 1].ssum;
      tree[i].smin = std::min(tree[i << 1].smin,
                              tree[i << 1].ssum + tree[i << 1 | 1].smin);
    }
  }
  void update_q(int i) {
    while (i /= 2)
      tree[i].qmax = max_op(tree[i << 1].qmax, tree[i << 1 | 1].qmax);
  }
  void update_d(int i) {
    while (i /= 2)
      tree[i].dmin = min_op(tree[i << 1].dmin, tree[i << 1 | 1].dmin);
  }

  void incremental_update(const int i, return_type &ret) {
    tree[i].ssum += 1;
    update_s(i);
    int s = tree[1].ssum - 1, k = 1;
    while (k < m) {
      k <<= 1;
      if (tree[k].ssum + tree[k | 1].smin == s) {
        s -= tree[k].ssum;
        k |= 1;
      }
    }
    if (k == m)
      return;
    int c = 0, r = tree.size();
    while (k < r) {
      if (k & 1) {
        if (comp(tree[k].dmin, tree[c].dmin))
          c = k;
        k++;
      }
      k >>= 1, r >>= 1;
    }
    assert(c != 0); // If this assertion fails, there's a bug in this library.
    while (c < m) {
      c <<= 1;
      if (comp(tree[c | 1].dmin, tree[c].dmin))
        c |= 1;
    }
    ret.insert.push_back(tree[c].dmin);
    tree[c].ssum = 0;
    tree[c].qmax = tree[c].dmin;
    tree[c].dmin = tree[0].dmin;
    update_s(c);
    update_q(c);
    update_d(c);
  }

  void decremental_update(const int i, return_type &ret) {
    tree[i].ssum -= 1;
    update_s(i);
    int s = tree[1].ssum, k = 1;
    while (k < m) {
      k <<= 1;
      if (s != tree[k].smin) {
        s -= tree[k].ssum;
        k |= 1;
      }
    }
    int c = 0;
    while (k) {
      if (k & 1) {
        if (comp(tree[c].qmax, tree[--k].qmax))
          c = k;
      }
      k >>= 1;
    }
    if (c == 0)
      return;
    while (c < m) {
      c <<= 1;
      if (comp(tree[c].qmax, tree[c | 1].qmax))
        c |= 1;
    }
    ret.erase.push_back(tree[c].qmax);
    tree[c].ssum = 1;
    tree[c].dmin = tree[c].qmax;
    tree[c].qmax = tree[0].qmax;
    update_s(c);
    update_q(c);
    update_d(c);
  }

public:
  partially_retroactive_priority_queue(int n, Comp comp, T min, T max)
      : n(n), m(1), comp(std::move(comp)), tree() {
    assert(comp(min, max));
    assert(!comp(min, min));
    assert(!comp(max, max));
    while (m < n + 1)
      m *= 2;
    tree.resize(2 * m, node{0, 0, min, max});
    tree[0].qmax = min;
    tree[0].dmin = max;
  }
  return_type set_push(int i, T x) {
    assert(0 <= i && i < n);
    assert(comp(tree[0].qmax, x) && comp(x, tree[0].dmin));
    auto ret = set_no_op(i);
    i += m;
    tree[i].dmin = x;
    update_d(i);
    incremental_update(i, ret);
    return ret;
  }
  return_type set_pop(int i) {
    assert(0 <= i && i < n);
    auto ret = set_no_op(i);
    i += m;
    decremental_update(i, ret);
    return ret;
  }
  return_type set_no_op(int i) {
    assert(0 <= i && i < n);
    return_type ret;
    i += m;
    if (tree[i].ssum == -1) {
      incremental_update(i, ret);
    } else if (comp(tree[0].qmax, tree[i].qmax)) {
      ret.erase.push_back(tree[i].qmax);
      tree[i].qmax = tree[0].qmax;
      update_q(i);
    } else if (comp(tree[i].dmin, tree[0].dmin)) {
      tree[i].dmin = tree[0].dmin;
      update_d(i);
      decremental_update(i, ret);
    }
    return ret;
  }
  void dump() {
    std::cerr << "\n##### dump partially_retroactive_priority_queue #####\n\n";
    std::multiset<T, Comp> set(comp);
    for (int i = 0; i < n; i++) {
      std::cerr << i << "-th op: ";
      const auto &v = tree[i + m];
      if (v.ssum == -1) {
        std::cerr << "pop";
        if (!set.empty())
          set.erase(std::prev(set.end()));
      } else if (comp(tree[0].qmax, v.qmax)) {
        std::cerr << "push " << v.qmax;
        set.insert(v.qmax);
      } else if (comp(v.dmin, tree[0].dmin)) {
        std::cerr << "push " << v.dmin;
        set.insert(v.dmin);
      } else {
        std::cerr << "no_op";
      }
      std::cerr << "\n{{";
      bool first = true;
      for (const T &x : set) {
        if (!std::exchange(first, false))
          std::cerr << ",";
        std::cerr << " " << x;
      }
      std::cerr << " }}\n";
    }
    std::cerr << "\n##### end #####\n\n";
    std::cerr.flush();
  }
};

} // namespace noshi91

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int N, Q;
  std::cin >> N >> Q;
  std::vector<int> D(N), P(N);
  for (auto &e : D)
    std::cin >> e, e--;
  for (auto &e : P)
    std::cin >> e;
  struct query_type {
    int c, x, y;
  };
  std::vector<query_type> qs(Q);
  for (auto &[c, x, y] : qs)
    std::cin >> c >> x >> y, c--, x--;

  std::vector<int> count(N, 1);
  for (const auto &e : D)
    count[e]++;
  for (const auto &[c, x, y] : qs)
    count[x]++;
  for (int i = N; --i;)
    count[i - 1] += count[i];

  noshi91::partially_retroactive_priority_queue<int, std::less<int>> prpq(
      count[0], {}, 0, int(1e9) + 1);
  for (int i = 0; i < N; i++) {
    prpq.set_pop(--count[i]);
  }

  long long ans = 0;
  const auto update = [&](const auto &res) {
    for (const auto &e : res.insert)
      ans -= e;
    for (const auto &e : res.erase)
      ans += e;
  };

  std::vector<int> idx(N);
  for (int i = 0; i < N; i++) {
    idx[i] = --count[D[i]];
    update(prpq.set_push(idx[i], P[i]));
    ans += P[i];
  }

  for (const auto &[c, x, y] : qs) {
    update(prpq.set_no_op(idx[c]));
    ans -= P[c];
    idx[c] = --count[x];
    P[c] = y;
    update(prpq.set_push(idx[c], y));
    ans += P[c];
    std::cout << ans << "\n";
  }

  return 0;
}

提出情報

ジャッジ結果