[WC2014]紫荆花之恋

[WC2014]紫荆花之恋

题目要求r_i + r_j \geq dis_{i,j}的点对有多少，那么考虑枚举路径上一个点把路径分开，就是求r_i -dis_i \geq r_j + dis_j的点对数量。那么在这个点上维护平衡树，就可以二分查找了。去重，考虑在儿子节点上挂一个平衡树，维护的信息和父亲的一样，但是只包含儿子的子树中的点。枚举i，在分割点的平衡树和分割点包含i的子树平衡树中分别查找

考虑点分治优化这一过程。新增一个点后，只需计算它在点分树上每个祖先处形成的贡献之和。就可以快速求出答案了。将原来挂在儿子上有关父亲的信息挂在点分树的儿子上即可。注意到加入点可能会使点分树退化为不优秀的性质，考虑替罪羊树的思想，定期重构即可

一些实现上的细节：需要写三个东西：平衡树，倍增求距，点分树。要采用高效平衡树。注意平衡树回收删掉的节点节省内存。建议模块化代码方便一块一块的调试。。。点分树部分很多迷之细节，想清楚再写，对着rqy的代码调了半天才发现问题。。

#include <bits/stdc++.h>

struct IO {
  const static int S = 3e7;
  char buc_in[S], buc_out[S], *p_in = buc_in, *p_out = buc_out;
  IO() { fread(buc_in, 1, S, stdin); }
  ~IO() { fwrite(buc_out, 1, p_out - buc_out, stdout); }
  inline int rd() {
    int ret = 0;
    while (!isdigit(*p_in)) ++p_in;
    while (isdigit(*p_in)) ret = ret * 10 + *p_in++ - '0';
    return ret;
  }
  inline void out(long long x) {
    static char buc[20], *p = buc;
    do *p++ = x % 10 + '0';
    while (x /= 10);
    while (p != buc)
      *p_out++ = *--p;
    *p_out++ = '\n';
  }
} io;

const int N = 2e5 + 233, P = 1e9;

namespace BTree {
  int pool[N * 100], *top = pool;
  inline void init_pool() {
    for (int i = 1; i < N * 100; ++i)
      *top++ = i;
  }
  inline int get() { return *--top; }
  inline void del(int x) { *top++ = x; }

  struct Node {
    int ch[2], val, size;
    inline void init() {
      ch[0] = ch[1] = val = size = 0;
    }
  } t[N * 100];

  inline void pushup(int x) {
    t[x].size = t[t[x].ch[0]].size + t[t[x].ch[1]].size + 1;
  }

  int stk[N], tmp[N], ver;

  void dfs(int x) {
    if (t[x].ch[0]) dfs(t[x].ch[0]);
    stk[++ver] = x, tmp[ver] = t[x].val;
    if (t[x].ch[1]) dfs(t[x].ch[1]);
  }

  void build(int &x, int l, int r) {
    int mid = (l + r) >> 1;
    x = stk[ver--]; t[x].init();
    t[x].val = tmp[mid];
    if (l < mid) build(t[x].ch[0], l, mid - 1);
    if (r > mid) build(t[x].ch[1], mid + 1, r);
    pushup(x);
  }

  int re, rfa, dir;

  void _insert(int &x, int val) {
    if (!x) {
      t[x = get()].val = val;
      return pushup(x);
    }
    _insert(t[x].ch[val > t[x].val], val);
    pushup(x);
    if (t[t[x].ch[0]].size > 0.75 * t[x].size || t[t[x].ch[1]].size > 0.75 * t[x].size)
      re = x, rfa = dir = 0;
    else if (t[x].ch[val > t[x].val] == re)
      rfa = x, dir = val > t[x].val;
  }

  inline void insert(int &x, int val) {
    re = rfa = dir = 0;
    _insert(x, val);
    if (re) {
      ver = 0; dfs(re); build(re, 1, ver);
      if (rfa)
        t[rfa].ch[dir] = re;
      else
        x = re;
    }
  }

  int query(int x, int val) {
    int ret = 0;
    while (x) {
      if (val < t[x].val)
        x = t[x].ch[0];
      else {
        ret += t[t[x].ch[0]].size + 1;
        x = t[x].ch[1];
      }
    }
    return ret;
  }

  void clear(int x) {
    if (t[x].ch[0]) clear(t[x].ch[0]);
    if (t[x].ch[1]) clear(t[x].ch[1]);
    t[x].init(); del(x);
  }
}

int R[N];

struct Graph {
  int to, nxt, cost;
} G[N * 2];
int head[N], etot;

inline void addedge(int x, int y, int c) {
  G[++etot] = { y, head[x], c }, head[x] = etot;
  G[++etot] = { x, head[y], c }, head[y] = etot;
}

namespace FTree {
  const int up = 17;
  int dad[N][up + 1], dep[N], dis[N];

  inline void link(int x, int f, int c) {
    addedge(x, f, c);
    dep[x] = dep[f] + 1;
    dis[x] = dis[f] + c;
    dad[x][0] = f;
    for (int i = 1; i <= up; ++i)
      dad[x][i] = dad[dad[x][i - 1]][i - 1];
  }

  inline int get_lca(int x, int y) {
    if (dep[x] < dep[y]) std::swap(x, y);
    for (int i = up; ~i; --i)
      if (dep[dad[x][i]] >= dep[y])
        x = dad[x][i];
    if (x == y) return x;
    for (int i = up; ~i; --i)
      if (dad[x][i] != dad[y][i])
        x = dad[x][i], y = dad[y][i];
    return dad[x][0];
  }

  inline int get_dis(int x, int y) {
    int lca = get_lca(x, y);
    return dis[x] + dis[y] - dis[lca] * 2;
  }
}

namespace DTree {

  int root1[N], root2[N], fa[N], vis1[N], vis2[N], tag;
  std::set<int> son[N];

  void clear(int x) {
    vis1[x] = tag;
    for (int y : son[x]) {
      BTree::clear(root2[y]);
      root2[y] = 0;
      clear(y);
    }
    BTree::clear(root1[x]);
    root1[x] = 0;
    son[x].clear();
  }

  int pos, min_tree, all;

  int get_size(int x, int dad) {
    int ret = 1;
    for (int i = head[x]; i; i = G[i].nxt) {
      int y = G[i].to;
      if (vis1[y] == tag && vis2[y] != tag && y != dad) {
        ret += get_size(y, x);
      }
    }
    return ret;
  }

  int get_pos(int x, int dad) {
    int ret = 1, max = 0;
    for (int i = head[x]; i; i = G[i].nxt) {
      int y = G[i].to;
      if (vis1[y] == tag && vis2[y] != tag && y != dad) {
        int tmp = get_pos(y, x);
        ret += tmp;
        max = std::max(max, tmp);
      }
    }
    max = std::max(max, all - ret);
    if (max < min_tree) {
      min_tree = max;
      pos = x;
    }
    return ret;
  }

  void insert(int x, int dad, int dep, int &r) {
    BTree::insert(r, dep - R[x]);
    for (int i = head[x]; i; i = G[i].nxt) {
      int y = G[i].to;
      if (vis1[y] == tag && vis2[y] != tag && y != dad) {
        insert(y, x, dep + G[i].cost, r);
      }
    }
  }

  int find_center(int x) {
    all = get_size(x, 0);
    min_tree = P;
    get_pos(x, 0);
    x = pos;
    vis2[x] = tag;

    insert(x, 0, 0, root1[x]);
    for (int i = head[x]; i; i = G[i].nxt) {
      int y = G[i].to;
      if (vis1[y] == tag && vis2[y] != tag) {
        int r = 0; insert(y, x, G[i].cost, r);
        int z = find_center(y);
        fa[z] = x; son[x].insert(z);
        root2[z] = r;
      }
    }
    return x;
  }

  inline void rebuild(int x) {
    ++tag;
    clear(x);
    int dad = fa[x], r = root2[x];
    root2[x] = 0;
    if (dad)
      son[dad].erase(x);
    x = find_center(x);
    fa[x] = dad;
    root2[x] = r;
    if (dad)
      son[dad].insert(x);
  }

  inline long long insert(int x, int f) {
    long long ret = 0;
    fa[x] = f;
    son[f].insert(x);
    for (int i = x; i; i = fa[i]) {
      if (fa[i]) {
        int tmp = FTree::get_dis(x, fa[i]);
        ret += BTree::query(root1[fa[i]], R[x] - tmp);
        ret -= BTree::query(root2[i], R[x] - tmp);
        BTree::insert(root2[i], tmp - R[x]);
      }
      int tmp = FTree::get_dis(x, i);
      BTree::insert(root1[i], tmp - R[x]);
    }
    int y = 0;
    for (int i = x; fa[i]; i = fa[i])
      if (BTree::t[root1[i]].size > 0.75 * BTree::t[root1[fa[i]]].size)
        y = fa[i];
    if (y) rebuild(y);
    return ret;
  }
}

int main() {
  BTree::init_pool();
  io.rd(); int n = io.rd();
  long long last_ans = 0;
  for (int i = 1; i <= n; ++i) {
    int f = io.rd() ^ (last_ans % P), c = io.rd();
    R[i] = io.rd();
    FTree::link(i, f, c);
    last_ans += DTree::insert(i, f);
    io.out(last_ans);
  }
  return 0;
}