关于动态开点线段树的应用

自己瞎取的名字，就是动态开点线段树。
大概思想当空间不够用的时候，随时可以删点和新建点，比较灵活。
下面是几个例子，有的是值域线段树，有的是普通坐标的线段树。

• P1908 逆序对

本来是树状数组水题，现在变成了奇怪的动态开点值域线段树模板题。
其实不用值域线段树也可以。
普通线段树就要离散化然后按照单调递增的顺序加 value，再 query。
多麻烦啊，所以一个值域线段树解决问题。

因为最大值 MAX 为 $10^9$，所以 inf 设为 $10^9$。
因为每一次查询的是当前点往右的点数，所以要特判 l>r 的情况。
因为 inf=1e9，所以查询 1e9+1 就会炸掉，所以要特判。
其实把 inf 变成 1e9+10 不是一样的吗

那么代码如下。

因为线段树平均链深度为 $\log$ 级别。
所以开 $N \log N$ 大小的线段树。
动态开点线段树的优势在这道题还真没体现出来（

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

const int N = 1e7 + 10;
const int inf = 1e9 + 10;

int n, cnt, root, tree[N];
int a[N], ls[N], rs[N];

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

void upd(int &rt, int l, int r, int val, int f) {
  if (!rt) rt = ++cnt;
  if (l==r) { tree[rt] += f; return ; }
  int mid = (l+r) >> 1;
  if (val<=mid) upd(ls[rt], l, mid, val, f);
  else upd(rs[rt], mid+1, r, val, f);
  tree[rt] = tree[ls[rt]] + tree[rs[rt]];
  return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (!rt) return 0;
  if (L<=l && r<=R) return tree[rt];
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += query(ls[rt], l, mid, L, R);
  if (R>mid) ans += query(rs[rt], mid+1, r, L, R);
  return ans;
}

int main() {
  read(n); ll ans = 0;
  for (int i=1; i<=n; ++i) {
    int x; read(x);
    ans += (ll)query(root, 1, inf, x+1, inf);
    upd(root, 1, inf, x, 1);
  }
  printf("%lld\n", ans);
  return 0;
}

跑了 4s 多，还不如写普通线段树（bu

• P3313 旅行

虽然是个紫题，但是是个水紫。

首先问题可以简化成树上染色问题，四个 option 变成下面这样。

• 某个节点被重新染色
• 节点权值被修改
• 求路径上某种颜色权值和
• 求路径上某种颜色最大权值

那么考虑对于每一个颜色开一棵动态开点线段树。
然后直接树链剖分乱搞。（轻重链剖分）
对于 option 3 和 4 随便乱搞都可以过。

但是对于 option 1，可以转化为在树中删点，再丢到另一棵树里。
option 2 直接修改当前权值即可。

所以想到 pushup 操作。
可以将节点的 MAX 和 SUM 直接变成 0。
接着删点（就这么做！）跑路。
然后在另一棵树里面新建节点，只需要丢进去即可。
然后修改颜色（即要修改节点所属树根）。
或者是修改当前的权值。注意要 remove 和 update 之后做。

然后就没了。

似乎并不毒瘤？

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

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

const int MAXN = 1e5 + 10;
const int MAX_SIZE = 2e7;

int n, Q, cnt, tot/*build-cnt*/, idx;
int w[MAXN], c[MAXN], wl[MAXN], wc[MAXN];
int dep[MAXN], siz[MAXN], fa[MAXN], son[MAXN];
int tp[MAXN], root[MAXN], id[MAXN];
char opt[3]; int head[MAXN<<1];

struct Edge { int to, nxt; } e[MAXN<<1];
void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

void dfs1(int cur, int f) {
  fa[cur] = f, siz[cur] = 1;
  dep[cur] = dep[f] + 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  } return ;
}

void dfs2(int cur, int Tp) {
  tp[cur] = Tp, id[cur] = ++idx;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa[cur] || to==son[cur]) continue;
    dfs2(to, to);
  } return ;
}

struct seg { int ls, rs, Max, val; } tree[MAX_SIZE];
void pushup(int rt) {
  tree[rt].val = tree[tree[rt].ls].val + tree[tree[rt].rs].val;
  tree[rt].Max = max(tree[tree[rt].ls].Max, tree[tree[rt].rs].Max);
  return ;
}

void upd(int &rt, int l, int r, int pos, int W) {
  if (!rt) rt = ++tot;
  if (l==r) { tree[rt].val = tree[rt].Max = W; return ; }
  int mid = (l+r) >> 1;
  if (pos<=mid) upd(tree[rt].ls, l, mid, pos, W);
  else upd(tree[rt].rs, mid+1, r, pos, W);
  pushup(rt); return ;
}

void remv(int rt, int l, int r, int pos) {
  if (l==r) { tree[rt].val = tree[rt].Max = 0; return ; }
  int mid = (l+r) >> 1;
  if (pos<=mid) remv(tree[rt].ls, l, mid, pos);
  else remv(tree[rt].rs, mid+1, r, pos);
  pushup(rt); return ;
}

int querys(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return tree[rt].val;
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += querys(tree[rt].ls, l, mid, L, R);
  if (R>mid) ans += querys(tree[rt].rs, mid+1, r, L, R);
  return ans;
}

int querym(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return tree[rt].Max;
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans = max(ans, querym(tree[rt].ls, l, mid, L, R));
  if (R>mid) ans = max(ans, querym(tree[rt].rs, mid+1, r, L, R));
  return ans;
}

int qus(int l, int r, int rel) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    ans += querys(root[rel], 1, n, id[tp[l]], id[l]);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans += querys(root[rel], 1, n, id[l], id[r]);
  return ans;
}

int qum(int l, int r, int rel) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    ans = max(ans, querym(root[rel], 1, n, id[tp[l]], id[l]));
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans = max(ans, querym(root[rel], 1, n, id[l], id[r]));
  return ans;
}

int main() {
  read(n), read(Q);
  for (int i=1; i<=n; ++i)
    read(w[i]), read(c[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs1(1, 1), dfs2(1, 1);
  for (int i=1; i<=n; ++i)
    upd(root[c[i]], 1, n, id[i], w[i]);
  while (Q--) {
    cin >> opt+1;
    int u, v; read(u), read(v);
    if (opt[2] == 'C') {
      remv(root[c[u]], 1, n, id[u]);
      upd(root[v], 1, n, id[u], w[u]);
      c[u] = v;
    } else if (opt[2] == 'W') {
      remv(root[c[u]], 1, n, id[u]);
      upd(root[c[u]], 1, n, id[u], v);
      w[u] = v;
    } else if (opt[2] == 'S') printf("%d\n", qus(u, v, c[u]));
    else if (opt[2] == 'M') printf("%d\n", qum(u, v, c[u]));
  }
  return 0;
}