题解：P5168 xtq玩魔塔

SentencedFate · 2026-08-11 17:23:52 · 题解

这题真的有蓝吗/zy

看到“从 u 到 v 的最小血量”，就是“从 u 到 v 的路径最大值最小”。建出 Kruskal 重构树。

::::info[会 Kruskal 重构树的可以不用看]

具体的，我们对原图做 Kruskal，每次连接两个连通块时，设两个连通块的并查集根编号分别为 u 和 v，那么就建一个虚点 x，并把 x 的权值设为原图中连接两个连通块的边的边权。

连边 (x, u) 和 (x, v)，且把 u 和 v 的并查集父亲设为 x。这样会建出一个 2n - 1 个点的二叉树，其中所有叶子都是实点，权值为 0；所有非叶都是虚点，权值不为 0。那么原图中 u 到 v 的路径最大值最小，就是 Kruskal 重构树上 u 和 v 的 LCA 的权值。

为什么这两个东西等价？考虑 u 和 v 的 LCA 的权值，就是 Kruskal 过程中第一次连接 u 所在连通块和 v 所在连通块那条边的权值，想要从 u 到 v，就必须经过这条边。而根据 Kruskal 的过程，第一次使 u 和 v 连接时，u 到 v 的路径中不会有更大的边。所以证明了等价性。

::::

这样我们就解决了 opt = 2。opt = 1 和 opt = 3 怎么办呢？

注意到 Kruskal 重构树上，点的权值从根到叶子单调不增，所以如果一个点 u 的权值 \le y，那么 u 的权值也 \le y。

所以对于 opt = 3，我们在 Kruskal 重构树上从 x 向上跳，跳到最浅的满足权值 \le y 的祖先 u，那么 u 子树中的所有实点在原图中都可以被访问到。“子树”可以刻画为“dfn 区间”，那么 opt = 1 和 opt = 3 转化为了：单点修改，区间查询颜色数。

这个你就有很多方法维护了。代码中提供了 5 种方法：

• 在线解法

  • 树套树：设 i 之前和 i 颜色相同的、最靠右的位置为 \text{pre}_i（如果 i 之前没有和 i 颜色相同的那么 \text{pre}_i = 0）。

    设 i 之后和 i 颜色相同的、最靠左的位置为 \text{nxt}_i（如果 i 之后没有和 i 颜色相同的那么 \text{nxt}_i = n + 1）。

    注意到这本质上就是一个双向链表。

    把 (\text{pre}_i, i) 插入二维平面上，那么区间 [l, r] 的颜色数就是二维平面上矩阵 [0, l - 1] \times [l, r] 内的点数。其实际意义为：每种颜色只在区间内的第一次出现产生贡献。

    修改颜色时，先把 x 从原来颜色的链表中删除，再插入新颜色的链表中。需要重新插入所有更改了 \text{pre} 的点。

    时间复杂度：O(n \log^2 n)，空间复杂度：O(n \log^2 n)，实际表现：Memory Limit Exceeded 90。

  • 树状数组：把上面那个树套树换成二维树状数组。

    时间复杂度：O(n \log^2 n)，空间复杂度：O(n \log^2 n)，实际表现：Time Limit Exceeded 70。

  • KDT：把上面那个树套树换成 KDT。

    时间复杂度：O(n \log^2 n)，空间复杂度：O(n \log^2 n)，实际表现：Time Limit Exceeded 50。

• 离线解法

  • 三维莫队（带修莫队）：单点修改区间数颜色是【模板】带修莫队。直接套三维莫队模板即可。

    时间复杂度：O(n^{5 / 3})，空间复杂度：O(n)，实际表现：Accepted 100，最大点 449ms。

  • CDQ 分治：考虑上面的树套树做法，实现出来会发现每个 opt = 1 要修改 3 个二维点，也就是要在数据结构内修改 6 次；每个 opt = 3 要做 1 次矩形查询。

    我们考虑 1 个矩形查询可以拆成 4 个二维前缀和查询。那么，每次二维前缀和查询 (i, j) 本质上就是：

    查询有多少个点 (x, y) 满足 x \le i \wedge y \le j，且其加入的时间早于查询时间、删除时间晚于查询时间。

    如果把“加入”看作“插入权值为 1 的点”，“删除”看作“插入权值为 -1 的点”，那么每次二维前缀和查询 (i, j) 本质上就是：

    查询所有满足 x \le i \wedge y \le j，且其加入的时间早于查询时间的点 (x, y) 的点权和。

    这就是【模板】三维偏序，直接 CDQ 分治即可解决。

    时间复杂度：O(n \log^2 n)，空间复杂度：O(n)，实际表现：Accepted 100，最大点 552ms。

代码已折叠。笔者最后选择了 CDQ 分治解法，虽然三维莫队也是可过的。

为了防止爆空间，废案解法已注释。

::::info[代码]

#include <set>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) ((x) & (-(x)))
namespace FastIn
{
    const int S = 4e6 + 7;
    char *p1, *p2, buf[S];
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, S, stdin), p1 == p2) ? EOF : *p1++)
    inline void read(int &x)
    {
        x = 0;
        char c = gc();
        while (c < '0' || c > '9')
            c = gc();
        for (; c >= '0' && c <= '9'; c = gc())
            x = (x << 3) + (x << 1) + (c & 15);
    }
    #undef gc
}
using FastIn::read;
const int MAXN = 1e5 + 7;
struct Edge { int u, v, w; } edg[MAXN * 3];
struct ListNode { int v, nxt; } e[MAXN << 2];
int n, m, Q, V, rt, idx = 1, h[MAXN << 2], tim, a[MAXN], b[MAXN * 3], dfn[MAXN], ldfn[MAXN << 2], rdfn[MAXN << 2], bdfn[MAXN], dep[MAXN << 2], fa[19][MAXN << 2], ans[MAXN << 1];
struct Oper { int op, x, y; } q[MAXN << 1];
inline void add(const int &u, const int &v) { e[++idx] = {v, h[u]}, h[u] = idx; }
namespace UFS
{
    int fa[MAXN << 2];
    inline void init()
    {
        for (int i = 1; i <= n + m; ++i)
            fa[i] = i;
    }
    inline int getfa(const int &u) { return fa[u] == u ? u : (fa[u] = getfa(fa[u])); }
}
void DFS0(const int &u)
{
    dep[u] = dep[fa[0][u]] + 1, ldfn[u] = tim + 1, u <= n && (bdfn[dfn[u] = ++tim] = u);
    for (int i = 1; i < 19; ++i)
        fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (int i = h[u], v = e[i].v; i; v = e[i = e[i].nxt].v)
        fa[0][v] = u, DFS0(v);
    rdfn[u] = tim;
}
inline int LCA(int u, int v)
{
    dep[u] < dep[v] && (std::swap(u, v), true);
    for (int i = dep[u] - dep[v]; i; i &= (i - 1))
        u = fa[__builtin_ctz(i)][u];
    if (u == v)
        return u;
    for (int i = 18; ~i; --i)
        fa[i][u] != fa[i][v] && (u = fa[i][u], v = fa[i][v]);
    return fa[0][u];
}
inline int getwfa(int u, const int &val)
{
    for (int i = 18; ~i; --i)
        fa[i][u] && edg[fa[i][u] - n].w <= val && (u = fa[i][u]);
    return u;
}
// namespace OnlineSol
// {
//  namespace ISgT
//  {
//      struct ISgTNode { int sum, ch[2]; } tr[MAXN << 6];
//      int tot = 0;
//      #define ls tr[rt].ch[0]
//      #define rs tr[rt].ch[1]
//      #define lson l, mid, ls
//      #define rson mid + 1, r, rs
//      void update(const int &pos, const int &val, const int &l, const int &r, int &rt)
//      {
//          !rt && (rt = ++tot), tr[rt].sum += val;
//          if (l == r)
//              return;
//          int mid = (l + r) >> 1;
//          pos <= mid ? update(pos, val, lson) : update(pos, val, rson);
//      }
//      int query(const int &L, const int &R, const int &l, const int &r, const int &rt)
//      {
//          if (!rt)
//              return 0;
//          if (L <= l && r <= R)
//              return tr[rt].sum;
//          int mid = (l + r) >> 1, res = 0;
//          if (L <= mid)
//              res += query(L, R, lson);
//          if (R > mid)
//              res += query(L, R, rson);
//          return res;
//      }
//      #undef ls
//      #undef rs
//      #undef lson
//      #undef rson
//  }
//  namespace SgT
//  {
//      int tr[MAXN << 2];
//      #define ls rt << 1
//      #define rs (rt << 1) | 1
//      #define lson l, mid, rt << 1
//      #define rson mid + 1, r, (rt << 1) | 1
//      void update(const int &x, const int &y, const int &val, const int &l, const int &r, const int &rt)
//      {
//          ISgT::update(y, val, 0, n, tr[rt]);
//          if (l == r)
//              return;
//          int mid = (l + r) >> 1;
//          x <= mid ? update(x, y, val, lson) : update(x, y, val, rson);
//      }
//      int query(const int &xl, const int &xr, const int &yl, const int &yr, const int &l, const int &r, const int &rt)
//      {
//          if (xl <= l && r <= xr)
//              return ISgT::query(yl, yr, 0, n, tr[rt]);
//          int mid = (l + r) >> 1, res = 0;
//          if (xl <= mid)
//              res += query(xl, xr, yl, yr, lson);
//          if (xr > mid)
//              res += query(xl, xr, yl, yr, rson);
//          return res;
//      }
//      inline void update(const int &x, const int &y, const int &val) { update(x, y, val, 0, n, 1); }
//      inline int query(const int &l, const int &r) { return query(0, l - 1, l, r, 0, n, 1); }
//      #undef ls
//      #undef rs
//      #undef lson
//      #undef rson
//  }
//  namespace BIT
//  {
//      std::unordered_map<int, int> c[MAXN];
//      inline void update(const int &x, const int &y, const int &val)
//      {
//          for (int i = x + 1; i <= n + 1; i += lowbit(i))
//              for (int j = y + 1; j <= n + 1; j += lowbit(j))
//                  c[i][j] += val, !c[i][j] && (c[i].erase(j), true);
//      }
//      inline int lquery(const int &x, const int &y)
//      {
//          int res = 0;
//          for (int i = x + 1; i; i &= (i - 1))
//              for (int j = y + 1; j; j &= (j - 1))
//                  c[i].count(j) && (res += c[i][j]);
//          return res;
//      }
//      inline int query(const int &l, const int &r) { return lquery(l - 1, r) - lquery(l - 1, l - 1); }
//  }
//  namespace KDT
//  {
//      struct KDTNode { int ch[2], sum; } tr[MAXN << 5];
//      int rt, tot = 0;
//      #define ls(u) tr[u].ch[0]
//      #define rs(u) tr[u].ch[1]
//      void update(const int &xpos, const int &ypos, const int &val, const int &xl, const int &xr, const int &yl, const int &yr, int &u)
//      {
//          !u && (u = ++tot), tr[u].sum += val;
//          if (xl == xr && yl == yr)
//              return;
//          if (xr - xl > yr - yl)
//          {
//              int mid = (xl + xr) >> 1;
//              xpos <= mid ? update(xpos, ypos, val, xl, mid, yl, yr, ls(u)) : update(xpos, ypos, val, mid + 1, xr, yl, yr, rs(u));
//          }
//          else
//          {
//              int mid = (yl + yr) >> 1;
//              ypos <= mid ? update(xpos, ypos, val, xl, xr, yl, mid, ls(u)) : update(xpos, ypos, val, xl, xr, mid + 1, yr, rs(u));
//          }
//      }
//      int query(const int &xL, const int &xR, const int &yL, const int &yR, const int &xl, const int &xr, const int &yl, const int &yr, const int &u)
//      {
//          if (!u)
//              return 0;
//          if (xL <= xl && xr <= xR && yL <= yl && yr <= yR)
//              return tr[u].sum;
//          if (xr - xl > yr - yl)
//          {
//              int mid = (xl + xr) >> 1, res = 0;
//              if (xL <= mid)
//                  res += query(xL, xR, yL, yR, xl, mid, yl, yr, ls(u));
//              if (xR > mid)
//                  res += query(xL, xR, yL, yR, mid + 1, xr, yl, yr, rs(u));
//              return res;
//          }
//          else
//          {
//              int mid = (yl + yr) >> 1, res = 0;
//              if (yL <= mid)
//                  res += query(xL, xR, yL, yR, xl, xr, yl, mid, ls(u));
//              if (yR > mid)
//                  res += query(xL, xR, yL, yR, xl, xr, mid + 1, yr, rs(u));
//              return res;
//          }
//      }
//      inline void update(const int &x, const int &y, const int &val) { update(x, y, val, 0, n, 0, n, rt); }
//      inline int query(const int &l, const int &r) { return query(0, l - 1, l, r, 0, n, 0, n, rt); }
//      #undef ls
//      #undef rs
//  }
//  int pre[MAXN], nxt[MAXN], lstapr[MAXN * 3];
//  std::set<int> vc[MAXN * 3];
//  inline void solve()
//  {
//      for (int i = 1, col; i <= n; ++i)
//      {
//          vc[col = a[bdfn[i]]].insert(i);
//          if (lstapr[col])
//              nxt[lstapr[col]] = i, pre[i] = lstapr[col];
//          else
//              pre[i] = 0;
//          nxt[i] = n + 1, lstapr[col] = i;
//      }
//      for (int i = 1; i <= n; ++i)
//          KDT::update(pre[i], i, 1);
//      std::set<int>::iterator it;
//      for (int i = 1, op, x, y, z, l, r; i <= Q; ++i)
//          if (op = q[i].op, x = q[i].x, y = q[i].y, op == 1)
//              pre[dfn[x]] && (z = pre[dfn[x]], nxt[z] = nxt[dfn[x]]),
//              nxt[dfn[x]] != n + 1 && (
//                  z = nxt[dfn[x]],
//                  KDT::update(pre[z], z, -1),
//                  pre[z] = pre[dfn[x]],
//                  KDT::update(pre[z], z, 1),
//                  true
//              ),
//              vc[a[x]].erase(dfn[x]),
//              a[x] = y, it = vc[y].upper_bound(dfn[x]),
//              r = it == vc[y].end() ? n + 1 : *it,
//              l = it == vc[y].begin() ? 0 : *(--it),
//              z = dfn[x],
//              KDT::update(pre[z], z, -1),
//              pre[dfn[x]] = l, nxt[dfn[x]] = r,
//              KDT::update(pre[z], z, 1),
//              vc[y].insert(dfn[x]),
//              l && (nxt[l] = dfn[x]),
//              r != n + 1 && (
//                  KDT::update(pre[r], r, -1),
//                  pre[r] = dfn[x],
//                  KDT::update(pre[r], r, 1),
//                  true
//              );
//          else if (op == 2)
//              printf("%d\n", x == y ? 0 : edg[LCA(x, y) - n].w);
//          else
//              z = getwfa(x, y), printf("%d\n", KDT::query(ldfn[z], rdfn[z]));
//  }
// }
namespace OfflineSol
{
//  namespace Mo
//  {
//      const int B = 2222;
//      int mt, ans[MAXN << 1], c[MAXN * 3];
//      struct Modify { int x, y; } mdf[MAXN << 1];
//      struct Query { int l, r, t, i; } qry[MAXN << 1];
//      inline void solve()
//      {
//          m = 0;
//          for (int i = 1; i <= n; ++i)
//              b[dfn[i]] = a[i];
//          for (int i = 1; i <= n; ++i)
//              a[i] = b[i];
//          for (int i = 1, z; i <= Q; ++i)
//              if (q[i].op == 1)
//                  mdf[++mt] = {dfn[q[i].x], q[i].y};
//              else if (q[i].op == 2)
//                  ans[i] = q[i].x == q[i].y ? 0 : edg[LCA(q[i].x, q[i].y) - n].w;
//              else
//                  z = getwfa(q[i].x, q[i].y), qry[++m] = {ldfn[z], rdfn[z], mt, i};
//          std::sort(qry + 1, qry + m + 1, [&](const Query &x, const Query &y) { return x.l / B == y.l / B ? (x.r / B == y.r / B ? x.t < y.t : x.r < y.r) : x.l < y.l; });
//          for (int i = 1, l = 1, r = 0, t = 0, cans = 0; i <= m; ++i)
//          {
//              auto add = [&](const int &x) { ++c[x] == 1 && ++cans; };
//              auto del = [&](const int &x) { !--c[x] && --cans; };
//              while (r < qry[i].r)
//                  add(a[++r]);
//              while (l > qry[i].l)
//                  add(a[--l]);
//              while (r > qry[i].r)
//                  del(a[r--]);
//              while (l < qry[i].l)
//                  del(a[l++]);
//              while (t < qry[i].t)
//                  ++t, l <= mdf[t].x && mdf[t].x <= r && (del(a[mdf[t].x]), add(mdf[t].y), true), std::swap(a[mdf[t].x], mdf[t].y);
//              while (t > qry[i].t)
//                  l <= mdf[t].x && mdf[t].x <= r && (del(a[mdf[t].x]), add(mdf[t].y), true), std::swap(a[mdf[t].x], mdf[t].y), --t;
//              ans[qry[i].i] = cans;
//          }
//          for (int i = 1; i <= Q; ++i)
//              q[i].op != 1 && printf("%d\n", ans[i]);
//      }
//  }
    namespace CDQ
    {
        struct Point { int x, y, v; bool isqry; } p[MAXN << 4], rec[MAXN << 4];
        int pc, pre[MAXN], nxt[MAXN], lstapr[MAXN * 3], ans[MAXN << 1];
        std::set<int> vc[MAXN * 3];
        namespace BIT
        {
            int c[MAXN];
            inline void add(const int &x, const int &v)
            {
                for (int i = x + 3; i < MAXN; i += lowbit(i))
                    c[i] += v;
            }
            inline int query(const int &x)
            {
                int res = 0;
                for (int i = x + 3; i; i &= (i - 1))
                    res += c[i];
                return res;
            }
        }
        inline void dac(const int &l, const int &r)
        {
            if (l == r)
                return;
            int mid = (l + r) >> 1; dac(l, mid), dac(mid + 1, r);
            for (int i = l, j = mid + 1, tp = l - 1; i <= mid || j <= r; )
                if (j > r || (i <= mid && p[i].x <= p[j].x))
                    rec[++tp] = p[i], !p[i].isqry && (BIT::add(p[i].y, p[i].v), true), ++i;
                else
                    rec[++tp] = p[j], p[j].isqry && (p[j].v < 0 ? ans[-p[j].v] -= BIT::query(p[j].y) : ans[p[j].v] += BIT::query(p[j].y)), ++j;
            for (int i = l; i <= mid; ++i)
                !p[i].isqry && (BIT::add(p[i].y, -p[i].v), true);
            for (int i = l; i <= r; ++i)
                p[i] = rec[i];
        }
        inline void solve()
        {
            for (int i = 1, col; i <= n; ++i)
            {
                vc[col = a[bdfn[i]]].insert(i);
                if (lstapr[col])
                    nxt[lstapr[col]] = i, pre[i] = lstapr[col];
                else
                    pre[i] = 0;
                nxt[i] = n + 1, lstapr[col] = i;
            }
            for (int i = 1; i <= n; ++i)
                p[++pc] = {pre[i], i, 1, false};
            std::set<int>::iterator it;
            for (int i = 1, op, x, y, z, l, r, xl, xr, yl, yr; i <= Q; ++i)
                if (op = q[i].op, x = q[i].x, y = q[i].y, op == 1)
                    pre[dfn[x]] && (z = pre[dfn[x]], nxt[z] = nxt[dfn[x]]),
                    nxt[dfn[x]] != n + 1 && (
                        z = nxt[dfn[x]],
                        p[++pc] = {pre[z], z, -1, false},
                        pre[z] = pre[dfn[x]],
                        p[++pc] = {pre[z], z, 1, false},
                        true
                    ),
                    vc[a[x]].erase(dfn[x]),
                    a[x] = y, it = vc[y].upper_bound(dfn[x]),
                    r = it == vc[y].end() ? n + 1 : *it,
                    l = it == vc[y].begin() ? 0 : *(--it),
                    z = dfn[x],
                    p[++pc] = {pre[z], z, -1, false},
                    pre[dfn[x]] = l, nxt[dfn[x]] = r,
                    p[++pc] = {pre[z], z, 1, false},
                    vc[y].insert(dfn[x]),
                    l && (nxt[l] = dfn[x]),
                    r != n + 1 && (
                        p[++pc] = {pre[r], r, -1, false},
                        pre[r] = dfn[x],
                        p[++pc] = {pre[r], r, 1, false},
                        true
                    );
                else if (op == 2)
                    ans[i] = x == y ? 0 : edg[LCA(x, y) - n].w;
                else
                    z = getwfa(x, y), l = ldfn[z], r = rdfn[z],
                    xl = 0, xr = l - 1, yl = l, yr = r,
                    p[++pc] = {xr, yr, i, true},
                    p[++pc] = {xl - 1, yr, -i, true},
                    p[++pc] = {xr, yl - 1, -i, true},
                    p[++pc] = {xl - 1, yl - 1, i, true};
            dac(1, pc);
            for (int i = 1; i <= Q; ++i)
                q[i].op != 1 && printf("%d\n", ans[i]);
        }
    }
}
int main()
{
    read(n), read(m), read(Q), UFS::init();
    for (int i = 1; i <= n; ++i)
        read(a[i]), b[++V] = a[i];
    for (int i = 1, u, v, w; i <= m; ++i)
        read(u), read(v), read(w), edg[i] = {u, v, w};
    std::sort(edg + 1, edg + m + 1, [&](const Edge &x, const Edge &y) { return x.w < y.w; });
    for (int i = 1, op, x, y; i <= Q; ++i)
        if (read(op), read(x), read(y), op == 1)
            q[i] = {op, x, y}, b[++V] = y;
        else
            q[i] = {op, x, y};
    std::sort(b + 1, b + V + 1), V = std::unique(b + 1, b + V + 1) - b - 1;
    for (int i = 1; i <= n; ++i)
        a[i] = std::lower_bound(b + 1, b + V + 1, a[i]) - b;
    for (int i = 1; i <= Q; ++i)
        if (q[i].op == 1)
            q[i].y = std::lower_bound(b + 1, b + V + 1, q[i].y) - b;
    for (int i = 1, u, v; i <= m; ++i)
        if ((u = UFS::getfa(edg[i].u)) != (v = UFS::getfa(edg[i].v)))
            UFS::fa[u] = UFS::fa[v] = i + n, add(i + n, u), add(i + n, v), rt = i + n;
    DFS0(rt), OfflineSol::CDQ::solve();
    return 0;
}

::::