Submission #402017

#	Time	Username	Problem	Language	Result	Execution time	Memory
402017		rama_pang	Arboras (RMI20_arboras)	C++17	100 / 100	1658 ms	24572 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 = [&](int prv) -> void {
    while (prv != 0) {
      int u = par[prv];
      lint newdp = dp_1.Query(st[prv]) + weight[prv];
      if (newdp <= dp_2.Query(st[u])) {
        // do nothing
        return;
      } 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]));
        return;
      } 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);
          prv = head;
          continue;
        }

        if (prefer[u] != -1) {
          // insert prefer[u] as head chain
          ModifyChain(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);

        prv = head;
        continue;
      }
    }
  };

  for (int i = 1; i < N; i++) {
    int w;
    cin >> w;
    weight[i] += w;
    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(u);
    cout << (dp_1.Query() + dp_2.Query()) % MOD << '\n';
  }
  return 0;
}

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