首页 > 其他分享 >【题解】CF487E Tourists / 圆方树

【题解】CF487E Tourists / 圆方树

时间:2023-03-21 19:13:44浏览次数:53  
标签:sz cnt int 题解 top nd 圆方树 res Tourists

概念

圆方树是一种基于无向图构造的树。

我们知道,圆方树最早是 WC 上提出的处理仙人掌的东西,用于将树上做法拓展到复杂度正确的仙人掌做法。

但是一些关于点双有性质的题也可以用圆方树转化成树上问题,例如这个。

构造

对于原图中的点,称之为圆点。

对于原图的每个点双,考虑为其虚拟一个对应的结点,称之为方点。

从方点向原图中所有的圆点连边,得到的是一个森林。原图中每个点双和森林中的一棵树对应。

特别地,当原图连通时,得到的是一棵树,称为圆方树。

性质

  • 圆点、方点均不会和同类型的点相邻。

  • 圆方树的点数是 \(O(n)\) 的。

题解

对于此题,注意到到达某个点双时一定有路径经过其中的任意一点,所以这个点双对答案的贡献等价于其中点权最小的结点对答案的贡献。

因此考虑对原图建圆方树。

于是询问直接上树剖做就行。

考虑到修改的时候会影响到包含该结点的相邻方点,于是比较难修改。

考虑只钦定方点的答案为子树中圆点的最小贡献,询问时如果 \(lca\) 是方点就加上缺少的贡献。

时间复杂度 \(O(n \log n)\).

#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

#define il inline
#define pb emplace_back

const int maxn = 2e5 + 5;
const int maxm = 2e5 + 5;
const int nd_sz = maxn << 1;
const int sgt_sz = nd_sz << 2;
const int inf = 2147483647;

int n, m, q;
int seq[maxn];
multiset<int> val[nd_sz];

il int read()
{
    int res = 0;
    char ch = getchar();
    while ((ch < '0') || (ch > '9')) ch = getchar();
    while ((ch >= '0') && (ch <= '9')) res = res * 10 + ch - '0', ch = getchar();
    return res;
}

il void write(int x)
{
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

il void write(int x, char ch) { write(x), putchar(ch); }

namespace tree
{
    int nd, cnt_pos;
    int fa[nd_sz], son[nd_sz], top[nd_sz];
    int pos[nd_sz], rk[nd_sz], dep[nd_sz], sz[nd_sz];
    vector<int> g[nd_sz];

    il void dfs1(int u, int f)
    {
        fa[u] = f, dep[u] = dep[f] + 1, sz[u] = 1;
        for (int v : g[u])
            if (v != f)
            {
                dfs1(v, u);
                sz[u] += sz[v];
                if (sz[v] > sz[son[u]]) son[u] = v;
            }
    }

    il void dfs2(int u, int t)
    {
        // printf("dfs2 %d %d %d %d\n", u, son[u], fa[u], t);
        rk[pos[u] = ++cnt_pos] = u, top[u] = t;
        if (son[u]) dfs2(son[u], t);
        for (int v : g[u])
            if ((v != son[u]) && (v != fa[u])) dfs2(v, v);
    }

    il int lca(int u, int v)
    {
        while(top[u] != top[v])
        {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            u = fa[top[u]];
        }
        return (dep[u] < dep[v] ? u : v);
    }
}

namespace SGT
{
    #define ls (k << 1)
    #define rs (k << 1 | 1)
    #define top tree::top
    #define dep tree::dep
    #define nd tree::nd
    #define pos tree::pos
    int val[sgt_sz];

    il void push_up(int k) { val[k] = min(val[ls], val[rs]); }

    il void build(int k, int l, int r)
    {
        if (l == r) return val[k] = seq[tree::rk[l]], void();
        int mid = (l + r) >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        push_up(k);
    }

    il void update(int k, int l, int r, int p, int w)
    {
        if (l == r) return val[k] = w, void();
        int mid = (l + r) >> 1;
        if (p <= mid) update(ls, l, mid, p, w);
        else update(rs, mid + 1, r, p, w);
        push_up(k);
    }

    il int query(int k, int l, int r, int ql, int qr)
    {
        if ((l >= ql) && (r <= qr)) return val[k];
        int mid = (l + r) >> 1, res = inf;
        if (ql <= mid) res = query(ls, l, mid, ql, qr);
        if (qr > mid) res = min(res, query(rs, mid + 1, r, ql, qr));
        return res;
    }

    il int qry_path(int u, int v)
    {
        int res = inf;
        while (top[u] != top[v])
        {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            res = min(res, query(1, 1, nd, pos[top[u]], pos[u]));
            u = tree::fa[top[u]];
        }
        if (dep[u] > dep[v]) swap(u, v);
        res = min(res, query(1, 1, nd, pos[u], pos[v]));
        if (u > n) res = min(res, seq[tree::fa[u]]);
        return res;
    }

    #undef top
    #undef nd
}

namespace graph
{
    #define g tree::g

    struct node
    {
        int fr, to, nxt;
    } edge[maxm << 1];

    int cnt_eg, cnt_ver, cnt_vdcc;
    int top, stk[maxn];
    int head[maxn], dfn[maxn], low[maxn], bel[maxn];

    il void add_edge(int u, int v) { edge[++cnt_eg] = (node){u, v, head[u]}, head[u] = cnt_eg; }

    il void tarjan(int u)
    {
        dfn[u] = low[u] = ++cnt_ver, stk[++top] = u;
        for (int i = head[u], v, tp; i; i = edge[i].nxt)
        {
            v = edge[i].to;
            if (!dfn[v])
            {
                tarjan(v);
                low[u] = min(low[u], low[v]);
                if (low[v] >= dfn[u])
                {
                    cnt_vdcc++;
                    // printf("debug %d\n", cnt_vdcc);
                    do
                    {
                        tp = stk[top--];
                        // printf("%d <-> %d\n", cnt_vdcc, tp);
                        bel[u] = cnt_vdcc, g[tp].pb(cnt_vdcc), g[cnt_vdcc].pb(tp);
                    } while (tp != v);
                    // printf("%d <-> %d\n", cnt_vdcc, u);
                    g[u].pb(cnt_vdcc), g[cnt_vdcc].pb(u);
                }
            }
            else low[u] = min(low[u], dfn[v]);
        }
    }
}

int main()
{
    graph::cnt_vdcc = n = read(), m = read(), q = read();
    for (int i = 1; i <= n; i++) seq[i] = read();
    for (int i = 1, u, v; i <= m; i++) u = read(), v = read(), graph::add_edge(u, v), graph::add_edge(v, u);
    // graph::cnt_vdcc = n;
    for (int i = 1; i <= n; i++)
        if (!graph::dfn[i]) graph::tarjan(i);
    tree::dfs1(1, 0);
    tree::dfs2(1, 1);
    // puts("done");
    for (int i = 2; i <= n; i++) val[tree::fa[i] - n].insert(seq[i]);
    for (int i = n + 1; i <= graph::cnt_vdcc; i++) seq[i] = ((!val[i - n].empty()) ? (*val[i - n].begin()) :inf);
    tree::nd = graph::cnt_vdcc;
    // for (int i = 1; i <= tree::nd; i++) printf("%d ", seq[i]); puts("");
    SGT::build(1, 1, tree::nd);
    while (q--)
    {
        int a, b, nw;
        char ch = getchar();
        while ((ch != 'A') && (ch != 'C')) ch = getchar();

            // puts("");
            // for (int i = 1; i <= tree::nd; i++) printf("%d ", seq[i]);
            // puts("");

        if (ch == 'C')
        {
            a = read(), nw = read();
            SGT::update(1, 1, tree::nd, pos[a], nw);
            if (a == 1) { seq[a] = nw; continue; }
            int u = tree::fa[a];
            // printf("debug u = %d\n", u);
            val[u - n].erase(val[u - n].find(seq[a]));
            val[u - n].insert(nw);
            int mnv = *val[u - n].begin();
            // printf("debug mnv = %d\n", mnv);
            if (mnv == seq[u]) { seq[a] = nw; continue; }
            SGT::update(1, 1, tree::nd, pos[u], mnv);
            seq[u] = mnv, seq[a] = nw;
        }
        else
        {
            a = read(), b = read();
            write(SGT::qry_path(a, b), '\n');
        }
    }
    return 0;
}

标签:sz,cnt,int,题解,top,nd,圆方树,res,Tourists
From: https://www.cnblogs.com/lingspace/p/cf487e.html

相关文章

  • CF123E maze 题解
    思考暴力:枚举起点和终点,再枚举每一种遍历序列得到答案。复杂度起飞。根据期望的可加性,我们无需硬着头皮统计每一条序列的贡献,而是把序列的贡献拆成遍历序列包含的边的贡献......
  • 蓝桥楼赛第9期-修复未正确实现的实验类 题解
    题目描述程序存放的位置/home/shiyanlou/lab.py;实验类名应该为Lab;实验对象中不能插入重复标签;Python中对象引用问题,尤其如复合对象list,dict,tuple的......
  • 【AT_abc294_g 题解】
    题意给定一颗\(n\)个节点的带权无向树。给出\(q\)个操作:1iw:把第\(i\)条边的边权变成\(w\)。2uv:求\(u\tov\)简单路径的边权和。解法根据树上差分。......
  • ABC288Ex 题解
    题意传送门给定\(n,m,x\),询问有多少个长度为\(n\)的非负整数序列满足以下条件:\(0\lea_1\lea_2\le\dots\lea_n\lem\)\(a_1\oplusa_2\oplus\dots\oplusa_n=x\)......
  • 问题解决01:默认不执行.ps1文件 - 无法双击.ps1文件
    默认不允许执行.ps1文件扩展名为.ps1的文件是用PowerShell写好的脚本文件。在Windows系统中,默认情况下是不允许执行.ps1文件。想双击一下执行.ps1文件?双击ps1文件很有......
  • 【题解】CF1034E
    题目描述给定\(n\)和长度为\(2^n\)的数列\(a_{0},a_{1}...a_{2^n-1}\)和\(b_{0},b_1...b_{2^n-1}\),保证每个元素的值属于\([0,3]\)生成序列\(c\),对于\(......
  • 【题解】CF889E
    题目描述\[f(x,n)=x\moda_n\]\[f(x,i)=(x\moda_i)+f(x\moda_i,i+1)\]给出a序列,当x取遍所有非负整数时\(f(x,1)\)的最大值。题解首先注意到\(a_i\)只......
  • 【题解】CF1368E
    题目描述有一个由\(n\)个点\(m\)条边组成的有向无环图,每个点出度至多为2。您需要标记一些点(不超过\(\frac{4}{7}n\)个)。标记一个点\(u\)将会删除所有与\(u\)连......
  • 【题解】CF1225F
    题目描述给出一棵n个节点的有根树T,点编号为0∼n−1。记f(u)为u的父节点。初始时你有一条n个点的链L(标号任意),每次操作你可以令f(u)←f(f(u))。需要将链改造......
  • 【题解】CF1439A2
    题目描述给定一个\(n\timesm\)的\(01\)矩阵,每次操作可以将某个\(2\times2\)的矩阵内的\(3\)个数取反,请在\(n\timesm\)步内将矩阵变为全\(0\)。题解这种题......