Submission #402016

#	Time	Username	Problem	Language	Result	Execution time	Memory
402016		rama_pang	Arboras (RMI20_arboras)	C++17	100 / 100	1633 ms	26316 KiB

arboras

#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const lint INF = 1e18;
const lint MOD = 1e9 + 7;

class SegTree {
 public:
  int sz;
  vector<int> cnt;
  vector<lint> tree;
  vector<lint> lazy;

  SegTree(int sz) : sz(sz), cnt(2 * sz), tree(2 * sz), lazy(2 * sz) {
    Build(1, 0, sz - 1);
  }

  void Build(int n, int tl, int tr) {
    if (tl == tr) {
      cnt[n] = 1;
      tree[n] = 0;
      lazy[n] = 0;
      return;
    }
    int md = (tl + tr) / 2;
    int z = n + 2 * (md - tl + 1);
    Build(n + 1, tl, md);
    Build(z, md + 1, tr);
    Pull(n, n + 1, z);
  }

  void Pull(int n, int lc, int rc) {
    cnt[n] = cnt[lc] + cnt[rc];
    tree[n] = tree[lc] + tree[rc];
    if (cnt[n] > 1) {
      tree[n] %= MOD;
    }
  }

  void Apply(int n, lint x) {
    tree[n] += cnt[n] * x;
    lazy[n] += x;
    if (cnt[n] > 1) {
      tree[n] %= MOD;
    }
  }

  void Push(int n, int lc, int rc) {
    Apply(lc, lazy[n]);
    Apply(rc, lazy[n]);
    lazy[n] = 0;
  }

  void Update(int n, int tl, int tr, int l, int r, lint x) {
    if (l > tr || tl > r || tl > tr || l > r) return;
    if (l <= tl && tr <= r) return Apply(n, x);
    int md = (tl + tr) / 2;
    int z = n + 2 * (md - tl + 1);
    Push(n, n + 1, z);
    Update(n + 1, tl, md, l, r, x);
    Update(z, md + 1, tr, l, r, x);
    Pull(n, n + 1, z);
  }

  void Update(int l, int r, lint x) {
    Update(1, 0, sz - 1, l, r, x);
  }

  lint Query(int p) {
    int n = 1, tl = 0, tr = sz - 1;
    while (tl != tr) {
      int md = (tl + tr) / 2;
      int z = n + 2 * (md - tl + 1);
      Push(n, n + 1, z);
      if (p <= md) {
        n = n + 1;
        tr = md;
      } else {
        n = z;
        tl = md + 1;
      }
    }
    assert(tl == tr);
    return tree[n];
  }

  lint Query() {
    return tree[1];
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;

  vector<int> st(N);
  vector<int> ist(N);
  vector<int> siz(N);
  vector<int> par(N);
  vector<int> root(N);
  vector<int> depth(N);
  vector<vector<int>> adj(N);

  par[0] = -1;
  for (int i = 1; i < N; i++) {
    cin >> par[i];
    adj[par[i]].emplace_back(i);
  }

  const auto DfsInit = [&](const auto &self, int u) -> void {
    siz[u] = 1;
    for (auto &v : adj[u]) {
      depth[v] = depth[u] + 1;
      self(self, v);
      siz[u] += siz[v];
      if (siz[v] > siz[adj[u][0]]) {
        swap(v, adj[u][0]);
      }
    }
  };

  const auto DfsHld = [&](const auto &self, int u) -> void {
    static int timer = 0;
    st[u] = timer++;
    ist[st[u]] = u;
    for (auto v : adj[u]) {
      root[v] = v == adj[u][0] ? root[u] : v;
      self(self, v);
    }
  };

  DfsInit(DfsInit, 0);
  DfsHld(DfsHld, 0);

  // Complexity by Link-Cut Tree Heavy-Light analysis
  // Keep segment tree, with dp[v] on position v
  // Update link-cut style on HLD
  // Time: O((N + Q) log^2 N).

  set<int> chain;
  for (int i = 0; i < N; i++) {
    chain.emplace(st[i]);
  }

  const auto ModifyChain = [&](int u, int sgn) {
    if (sgn == -1) {
      chain.erase(chain.find(st[u]));
    } else if (sgn == +1) {
      chain.emplace(st[u]);
    }
  };

  SegTree dp_1(N);
  SegTree dp_2(N);
  vector<int> prefer(N, -1);
  vector<lint> weight(N);

  const auto Update = [&](const auto &self, int prv) -> void {
    if (prv == 0) return;
    int u = par[prv];
    lint newdp = dp_1.Query(st[prv]) + weight[prv];

    if (newdp <= dp_2.Query(st[u])) {
      // do nothing
    } else if (dp_2.Query(st[u]) < newdp && newdp <= dp_1.Query(st[u])) {
      dp_2.Update(st[u], st[u], newdp - dp_2.Query(st[u]));
    } else if (dp_1.Query(st[u]) < newdp) {
      lint dp1 = dp_1.Query(st[u]);
      lint dp2 = dp_2.Query(st[u]);
      int head = ist[*prev(chain.upper_bound(st[u]))];
      assert(root[u] == root[head]);

      if (prefer[u] == prv) {
        dp_1.Update(st[head], st[u], newdp - dp1);
        return self(self, head);
      }

      if (prefer[u] != -1) {
        // insert prefer[u] as head chain
        ModifyChain(prefer[u], +1);
        prefer[u] = -1;
      }
      prefer[u] = prv;
      if (root[u] == root[prv]) {
        // delete prv as head chain
        ModifyChain(prv, -1);
      }

      dp_2.Update(st[u], st[u], dp1 - dp2);
      dp_1.Update(st[head], st[u], newdp - dp1);

      return self(self, head);
    }
  };

  const auto Print = [&]() {
    for (int i = 0; i < N; i++) {
      cout << i << ' ' << dp_1.Query(st[i]) << ' ' << dp_2.Query(st[i]) << '\n';
    }
    cout << '\n';
  };

  for (int i = 1; i < N; i++) {
    int w;
    cin >> w;
    weight[i] += w;
    Update(Update, i);
  }

  cout << (dp_1.Query() + dp_2.Query()) % MOD << '\n';

  int Q;
  cin >> Q;
  while (Q--) {
    int u, w;
    cin >> u >> w;
    weight[u] += w;
    Update(Update, u);
    cout << (dp_1.Query() + dp_2.Query()) % MOD << '\n';
    // Print();
  }
  return 0;
}

Compilation message (stderr)

arboras.cpp: In function 'int main()':
arboras.cpp:200:14: warning: variable 'Print' set but not used [-Wunused-but-set-variable]
  200 |   const auto Print = [&]() {
      |              ^~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 31 / 31
• Subtask 4: 45 / 45