[ZJOI2012] 网络 题解

· · 题解

这是一篇 FHQ 题解。

其他题解都是 LCT 做的，我就不服气，这道题中只有链，完全可以直接用 FHQ-Treap 维护链。

具体的：
分成 C 张独立的图维护，按照链的顺序对每条链建一棵 FHQ-Treap：
连接 u 和 v 时：要想拼完最大度数不超过 2 就必须都是链头或链尾；要想没有环，就不能在同一条链上（读者自证不难）。如果两个都是链头或者两个都是链尾就翻转一个，然后链头 merge 到链尾后面。

对于查询操作：写一个查询排名的函数，把两端点之间的点都分裂出来，求个最大值即可。

断链也很简单：直接查询排名 split 一下就行了。

修改点权一路 pushup 上去即可。

时间复杂度 O(m\log n + kC\log n)。
不用卡常轻松拿下最优解。

#include<bits/stdc++.h>
using namespace std;
mt19937 Rnd(time(0));
const int N = 10011;
typedef struct{
    typedef struct{
        int key,fa,siz,mx,x; 
        int ls,rs;
        bool rev;
    }Tree;
    Tree t[N];
    void rev(int p)
    {
        swap(t[p].ls,t[p].rs),t[p].rev ^= 1;
    }
    void pushdown(int p)
    {
        if(t[p].rev) rev(t[p].ls),rev(t[p].rs),t[p].rev = 0;
    }
    void pushup(int p)
    {
        t[p].mx = max({t[t[p].ls].mx,t[p].x,t[t[p].rs].mx});
        t[p].siz = t[t[p].ls].siz + 1 + t[t[p].rs].siz;
        t[t[p].ls].fa = t[t[p].rs].fa = p;
    }
    void Pushup(int p)
    {
        while(p) pushup(p),p = t[p].fa;
    }
    void split(int p,int k,int& l,int& r)
    {
        if(!p) return l = r = 0,void();
        pushdown(p);
        if(t[t[p].ls].siz + 1 <= k)
            l = p,split(t[p].rs,k - t[t[p].ls].siz - 1,t[p].rs,r);
        else
            r = p,split(t[p].ls,k,l,t[p].ls);
        pushup(p);
    }
    int merge(int x,int y)
    {
        if(!x || !y) return (x | y);
        if(t[x].key < t[y].key)
            return pushdown(x),t[x].rs = merge(t[x].rs,y),pushup(x),x;
        return pushdown(y),t[y].ls = merge(x,t[y].ls),pushup(y),y;
    }
    int st[N];
    int rk(int p)
    {
        int top = 0,r = p;
        st[++top] = r;
        while(t[r].fa) st[++top] = r = t[r].fa;
        while(top) pushdown(st[top--]);
        int res = t[t[p].ls].siz + 1;
        while(t[p].fa)
        {
            if(t[t[p].fa].rs == p)
                res += t[t[t[p].fa].ls].siz + 1;
            p = t[p].fa;
        }
        return res;
    }
    int findroot(int x)
    {
        while(t[x].fa) x = t[x].fa;
        return x;
    }
    int ask(int x,int y)
    {
        int rot = findroot(x);
        if(rot != findroot(y))
            return -1;
        int l = rk(x),r = rk(y);
        if(l > r) swap(l,r);
        split(rot,r,x,y);
        int w;
        split(x,l - 1,x,w);
        rot = t[w].mx;
        t[merge(merge(x,w),y)].fa = 0;
        return rot;
    }
    bool link(int x,int y)
    {
        int X = findroot(x),Y = findroot(y);
        if(X == Y)
        {
            x = rk(x),y = rk(y);
            if(x > y) swap(x,y);
            cout << (x == 1 && y == t[X].siz ? "Error 2.\n" : "Error 1.\n");
            return 0;
        }
        int kx = rk(x),ky = rk(y);
        if((kx != 1 && kx != t[X].siz) || (ky != 1 && ky != t[Y].siz))
        {
            cout << "Error 1.\n";
            return 0;
        }
        if(!((kx == 1) ^ (ky == 1))) rev(Y);
        if(kx == 1) t[merge(Y,X)].fa = 0;
        else t[merge(X,Y)].fa = 0;
        return 1;
    }
    void cut(int x,int y)
    {
        int l,r;
        split(findroot(x),min(rk(x),rk(y)),l,r);
        t[l].fa = t[r].fa = 0;
    }
}FHQ;
FHQ t[10];
int a[N];
int n,m,C,k;
map<pair<int,int>,int> mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m >> C >> k;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        for(int j = 0;j < C;j++)
            t[j].t[i] = {(int)Rnd(),0,1,a[i],a[i],0,0,0};
    }
    for(int i = 1;i <= m;i++)
    {
        int x,y,w;
        cin >> x >> y >> w;
        if(x > y) swap(x,y);
        mp[{x,y}] = w;
        t[w].link(x,y);
    }
    while(k--)
    {
        int opt;
        cin >> opt;
        if(opt == 0)
        {
            int x,y;
            cin >> x >> y;
            a[x] = y;
            for(int c = 0;c < C;c++)
                t[c].t[x].x = y,t[c].Pushup(x);
        }else if(opt == 1)
        {
            int x,y,w;
            cin >> x >> y >> w;
            if(x > y) swap(x,y);
            if(!mp.count({x,y}))
            {
                cout << "No such edge.\n";
                continue;
            }
            int usd = mp[{x,y}];
            if(usd == w)
            {
                cout << "Success.\n";
                continue;
            }
            if(t[w].link(x,y))
                t[usd].cut(x,y),mp[{x,y}] = w,cout << "Success.\n";
        }else{
            int c,x,y;
            cin >> c >> x >> y;
            cout << t[c].ask(x,y) << "\n";
        }
    }
    return 0;
}