2016.10.02省选模拟T4 travel
树链剖分 tarjan 问题转化    2016-10-06 18:55:58    361    0    0

题意:有一个有点权的无向图,两种操作分别为修改一个点的点权或查询两点之间所有路径上的所有点权的最小值。 

n,m,q100000.

 

先考虑不带修改操作

点双缩点,然后把割点单独提出来,和相邻点双连通分量连边

然后就变成树了!

预处理每个bcc/割点的最小值,然后问题转化为求两点路径间的最小值,可以树链剖分/LCT.

 

对于修改操作,用set维护节点的最小值,如果修改的是割点的话,就同时用答案更新每个与它相连的bcc.

然后复杂度就萎掉了...

发现一个性质:bcc连的一定是割点,割点连的一定是bcc。 

 

那么:

修改割点的同时,只更新他的父亲bcc。 
若查询的lca是bcc,那么要查询他父亲那个割点。 

 

#include <bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>

#pragma GCC optimize("O2")
#define VAL(x) #x " = " << x << " "

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef __gnu_pbds::priority_queue<int, greater<int>, __gnu_pbds::pairing_heap_tag> heap;

string program_name = __FILE__;
string iput = program_name.substr(0, program_name.length() - 4) + ".in";
string oput = program_name.substr(0, program_name.length() - 4) + ".out";

template <class t> inline bool chkmin(t &x, t y) { return x > y ? x = y, true : false; }
template <class t> inline bool chkmax(t &x, t y) { return x < y ? x = y, true : false; }
 
template <class t> inline t &read(t &x) 
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) if (c == '-') f = -1;
    for (x = 0; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x *= f;
}
 
template <class t> inline void write(t x, char p = '\n') 
{
    static char s[25];
    static int top = 0; 
    if (x < 0) putchar('-'), x = -x;
    do s[++top] = x % 10 + 48; while (x /= 10);
    do putchar(s[top]); while (-- top);
    putchar(p);
}
 
const int mo = 1000000007;
const int oo = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int maxm = 2e5 + 5;
 
namespace heavy_light_decomposition
{
    namespace SegmentTree
    {
        const int base = 1 << 20;

        int s[(1 << 21) + 5];

        inline void update(int x, const int &v)
        {
            s[x += base] = v;
            x >>= 1;
            while (x) s[x] = min(s[x << 1], s[x << 1 | 1]), x >>= 1;
        }

        inline int query(int l, int r)
        {
            int ret = oo;
            for (l += base - 1, r += base + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
                if (!(l & 1)) chkmin(ret, s[l ^ 1]);
                if (r & 1) chkmin(ret, s[r ^ 1]);
            }
            return ret;
        }
    }

    int n;
    int w[maxm];

    int st[maxm], cnte;
    struct edge { int to, next; } e[maxm << 1];

    inline void addedge(const int &u, const int &v)
    {
        e[++ cnte] = (edge) {v, st[u]}; st[u] = cnte;
    }

    int fa[maxm], dep[maxm], size[maxm], son[maxm];
    int dfn[maxm], top[maxm], Time;

    inline void modify(const int &x, const int &v)
    {
        SegmentTree::update(dfn[x], v);
    }

    void dfs1(const int &x, const int &Fa)
    {
        fa[x] = Fa;
        dep[x] = dep[Fa] + 1;
        size[x] = 1;
        for (int i = st[x]; i; i = e[i].next) {
            int v = e[i].to;
            if (v != Fa && !fa[v]) {
                dfs1(v, x);
                size[x] += size[v];
                if (size[son[x]] < size[v])
                    son[x] = v;
            }
        }
    }

    void dfs2(const int &x, const int &Top)
    {
        top[x] = Top;
        dfn[x] = ++ Time;
        modify(x, w[x]);
        if (son[x]) dfs2(son[x], Top);
        for (int i = st[x]; i; i = e[i].next) {
            int v = e[i].to;
            if (!dfn[v])
                dfs2(v, v);
        }
    }

    inline void init(const int &x)
    {
        n = x;
        dfs1(1, 1);
        dfs2(1, 1);
    }

    inline pii query(int x, int y)
    {
        int ret = oo;
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]])
                swap(x, y);
            chkmin(ret, SegmentTree::query(dfn[top[x]], dfn[x]));
            x = fa[top[x]];
        }
        if (dep[x] < dep[y]) swap(x, y);
        chkmin(ret, SegmentTree::query(dfn[y], dfn[x]));
        return make_pair(ret, fa[y]);
    }
}

int n;
int m;
int q;
int w[maxn];

multiset<int> _set[maxm];

int st[maxn], cnte;
struct edge { int to, next; } e[maxm];

inline void addedge(const int &u, const int &v)
{
    e[++ cnte] = (edge) {v, st[u]}; st[u] = cnte;
}

bool iscut[maxn];
int bccid[maxn], totbcc;
int dfn[maxn], low[maxn], Time;

int top;
pii _stack[maxm];

void tarjan(const int &x, const int &fa)
{
    dfn[x] = low[x] = ++ Time;

    for (int i = st[x]; i; i = e[i].next) {

        pii cur;
        int v = e[i].to;

        cur = make_pair(x, v);

        if (!dfn[v]) {
            _stack[++ top] = cur;
            tarjan(v, x);
            chkmin(low[x], low[v]);
            if (low[v] >= dfn[x]) {
                iscut[x] = true;
                bccid[x] = ++ totbcc;
                heavy_light_decomposition::addedge(x, totbcc);
                heavy_light_decomposition::w[x] = w[x];
                heavy_light_decomposition::w[totbcc] = oo;
                do {
                    int a = _stack[top].first;
                    int b = _stack[top].second;
                    if (chkmax(bccid[a], totbcc)) _set[totbcc].insert(w[a]);
                    if (chkmax(bccid[b], totbcc)) _set[totbcc].insert(w[b]);
                    if (iscut[a]) heavy_light_decomposition::addedge(totbcc, a);
                    if (iscut[b]) heavy_light_decomposition::addedge(totbcc, b);
                    if (x != a) chkmin(heavy_light_decomposition::w[totbcc], w[a]);
                    if (x != b) chkmin(heavy_light_decomposition::w[totbcc], w[b]);
                } while (_stack[top --] != cur);
            }
        }
        else 
            if (dfn[v] < dfn[x] && v != fa)
                _stack[++ top] = cur, chkmin(low[x], dfn[v]);
    }
}

inline void exec()
{
    read(n);
    read(m);
    read(q);

    for (int i = 1; i <= n; ++ i) 
        read(w[i]);

    for (int i = 1, u, v; i <= m; ++ i) {
        read(u); 
        read(v);
        addedge(u, v);
        addedge(v, u);
    }

    totbcc = n;
    tarjan(1, 0);

    for (int i = 1; i <= n; ++ i) 
        if (iscut[i])
            bccid[i] = i;

    heavy_light_decomposition::init(totbcc);

    while (q --) {

        static char s[2];
        static int u, v;

        scanf("%s", s);
        read(u), read(v);

        if (s[0] == 'A') {
            pii ret = heavy_light_decomposition::query(bccid[u], bccid[v]);
            if (u != v && ret.second <= n && iscut[ret.second])
                chkmin(ret.first, w[ret.second]);
            write(ret.first);
        }
        else
        {
            if (iscut[u]) {
                heavy_light_decomposition::modify(u, v);
                if (u != 1) {
                    int x = heavy_light_decomposition::fa[u];
                    int tmp = *_set[x].begin();
                    _set[x].erase(_set[x].find(w[u]));
                    _set[x].insert(v);
                    if (*_set[x].begin() != tmp)
                        heavy_light_decomposition::modify(x, *_set[x].begin());
                }
            }
            else 
            {
                int x = bccid[u];
                int tmp = *_set[x].begin();
                _set[x].erase(_set[x].find(w[u]));
                _set[x].insert(v);
                if (*_set[x].begin() != tmp)
                    heavy_light_decomposition::modify(x, *_set[x].begin());
            }
            w[u] = v;
        }
    }
}

int main() {

    if (fopen(iput.c_str(), "r")) {
        freopen(iput.c_str(), "r", stdin);
        freopen(oput.c_str(), "w", stdout);
    }
 
    exec();

#ifdef DEBUG_STATUS
    cerr << (double) clock() / CLOCKS_PER_SEC << endl;
#endif

    fclose(stdin);
    fclose(stdout);

    return 0;
}

 

BZOJ4568: [Scoi2016]幸运数字
361 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航