【题解】LOJ 523 「LibreOJ β Round #3」绯色 IOI(悬念)

请注意,本文编写于 98 天前,最后修改于 98 天前,其中某些信息可能已经过时。

毫无疑问这是一道考场无人 $AC$ 的毒瘤题

Problem

有 $m$ 个妹子, $n$ 个汉子,第 $i$ 个妹子可以交流的汉子可以用 $a[i],b[i]$ 来描述

具体来说,假设 $j$ 满足 $\min\{(j-a_i) \bmod n,(a_i-j) \bmod n\}=b_i$ ,则对于第 $i$ 个妹子来说第 $j$ 个汉子是可以交流的,其中保证 $b_i\leq\left\lfloor\frac{n}{2}\right\rfloor$

对于所有的 $(i,j)$ 这样的关系,我们将其按照 $i$ 为第一关键字 $j$ 为第二关键字从小到大排序,依次给定权值 $c_x$ ,也就是说第 $i$ 个妹子和第 $j$ 个汉子交流可以产生贡献 $c_x$

当然,一个妹子只能和一个汉子交流,一个汉子也只能和一个妹子交流

保证所有的妹子都能最终都能和某一个汉子配对,问最大贡献为多少

有 $q$ 个修改操作,每次将第 $x$ 个关系的权值修改为 $y$ ,请输出修改后的最大贡献

Thought

看到这个题正常人都会写二分图最大带权匹配吧...

首先有第一个特殊性质,存在妹子的满匹配

首先算出每个妹子能够交流的汉子
分别令 $j-a_i\equiv b_i \pmod n,a_i-j\equiv b_i \pmod n$
并且尝试取 $ \min$

然后会发现能匹配的汉子编号恰好为 $a[i]+b[i] \bmod n$ 和 $a[i]-b[i]\bmod n$

妙呀,这样就又有了一个性质:每个妹子最多能够和两个汉子交流

我们设妹子为左侧节点,汉子为右侧节点

我们将所有连向了同一个右侧节点的左侧节点称之为有关系,将直接或者间接有关系的左侧节点放在一个集合中

显然,不在一个集合中的节点之间没有任何的影响,所以仅仅需要单独考虑一个集合中的元素

由于妹子存在满匹配,所以对于任何一个集合或者集合的子集来说,与其相连的右侧节点数量一定是大于等于其集合大小的

那么对于同一个集合来说,就必然不会出现几个左侧节点连接的右侧节点恰好形成一个环并且还有一个左侧节点两端都连在环上的情况

并且由于每个集合中的点是有直接或者间接的关系的,这就说明其相连的右侧节点是两两可达的

可以发现,在这样的情况下,集合中的点和其右侧节点必然组成了一棵树/基环树

那么就可以在树上进行 $DP$ 了!

如果我们将左侧节点看做一条边,那么问题转化为对每条边确定一个方向,每个点只能被一条边指,求最大权值

显然基环树上的环的方向只有两种可能:顺时针 $or$ 逆时针
显然基环树上树边的方向只有一种可能:远离环(或者说这是一个外向基环树

那么对于基环树上的情况只需要存下每个环顺逆时针的权值和,取最大值即可

树的情况稍微复杂一点
由于树上的点数 $=$ 边数 $+1$ ,那么显然只有一个点不会被选择,如果以该点为根,每条边都恰好指向远离根的方向

考虑维护每条边指向某个方向时对哪些点做出贡献,也就是该边另外一侧的节点

这些节点在 $DFS$ 序上一定是一段/两段连续的区间,线段树维护贡献即可,每次询问取使得贡献最大的根节点

时间复杂度 $O(q\log n)$

一些实现上的细节:

Q: 如何定位某个关系 $(i,j)$

A: 考虑直接找到该点 $i$ ,找它相连的边即可

Q: 如何修改权值?

A: 我们先找到该点,和该点所属的集合,分情况讨论:

  • 该集合为基环树

    • 如果该边在环上,查询该边是正向或者逆向,直接修改并且更新最大值
    • 如果该边在树上,查询该边是内向或是外向,直接修改并且更新最大值
  • 该集合为树

    • 找到这条边影响的区间 $[l,r]$ ,在线段树上直接做区间加法 $c_{new}-c[old]$ ,并且更新最大值

Q: 如何建立线段树

A: 对于一个集合,对其进行 $DFS$ ,如果是个树,那么动态开个线段树即可

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 500010;
int n, m, T, q;
int a[N], b[N];
struct Edge {
    int t, n, w;
}e[N << 1];
int head[N], Etot = 1;

bool vis[N];
int bel[N], setCnt;
vector <int> Set[N];

bool ban[N << 1];
bool Cir;

//just for JHS
bool edgCir[N << 1];//if the edge on the circle
bool edgOut[N << 1];//if the edge is pointing to the outside

int CirNod[N];
bool nodCir[N];
int positiveKey[N];
int negativeKey[N];
int treeKey[N];

int dfn[N], low[N], DFN;
int siz[N];

struct C {
    int c, id;
}E[N << 1];
int Cnt;

#define L ch[x][0]
#define R ch[x][1]
#define mid ((l + r) >> 1)
struct Seg {
    int rt[N], cnt;
    int ch[N << 2][2];
    int a[N << 2], tag[N << 2];
    void build(int &x, int l, int r) {
        x = ++ cnt;
        if(l == r) return;
        else {
            build(L, l, mid);
            build(R, mid + 1, r);
        }
    }
    void upd(int x) {a[x] = max(a[L], a[R]);}
    void pus(int x) {tag[L] += tag[x]; tag[R] += tag[x]; a[L] += tag[x]; a[R] += tag[x]; tag[x] = 0;}
    void add(int x, int l, int r, int ll, int rr, int key) {
        if(ll > rr || !key) return;
        if(l >= ll && r <= rr) {
            a[x] += key;
            tag[x] += key;
        }
        else {
            pus(x);
            if(mid >= ll) add(L, l, mid, ll, rr, key);
            if(mid < rr) add(R, mid + 1, r, ll, rr, key);
            upd(x);
        }
    }
    int get(int x) {
        return a[rt[x]];
    }
}Seg;

void addedge(int u, int v, int w) {
    e[++ Etot] = {v, head[u], w};
    head[u] = Etot;
//    printf("%d %d %d\n", u, v, w);
}

void dfs1(int x) {
    bel[x] = setCnt;
    vis[x] = 1;
    Set[setCnt].push_back(x);
    for(int i = head[x]; i; i = e[i].n) {
        if(vis[e[i].t]) continue;
        dfs1(e[i].t);
    }
}

void dfs2(int x) {
    vis[x] = 1;
    for(int i = head[x]; i; i = e[i].n) {
        if(edgCir[i] || edgCir[i ^ 1] || ban[i] || ban[i ^ 1]) continue;
        if(vis[e[i].t]) {
            CirNod[bel[x]] = e[i].t;
            Cir = 1;
        }
        else {
            ban[i] = 1;
            dfs2(e[i].t);
            ban[i] = 0;
        }
        if(Cir) {
            nodCir[x] = 1;
            positiveKey[bel[x]] += e[i].w;
            negativeKey[bel[x]] += e[i ^ 1].w;
            edgCir[i] = 1;
            //正向边为 1
            //反向边为 0
            //所以在判断是不是在环上的边需要同时判断 i 和 i^1
        }
        if(CirNod[bel[x]] == x)
            Cir = 0;
        if(Cir) return;
    }
    vis[x] = 0;
}

void dfs3(int x, int _f) {
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == _f) continue;
        if(edgCir[i] || edgCir[i ^ 1]) continue;
        edgOut[i] = 1;
        treeKey[bel[x]] += e[i].w;
        dfs3(e[i].t, x);
    }
}

void dfs4(int x, int _f) {
    dfn[x] = ++ DFN;
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == _f) continue;
        dfs4(e[i].t, x);
    }
    low[x] = DFN;
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == _f) continue;
        Seg.add(Seg.rt[bel[x]], 1, siz[bel[x]], 1, dfn[e[i].t] - 1, e[i].w);
        Seg.add(Seg.rt[bel[x]], 1, siz[bel[x]], low[e[i].t] + 1, siz[bel[x]], e[i].w);
        Seg.add(Seg.rt[bel[x]], 1, siz[bel[x]], dfn[e[i].t], low[e[i].t], e[i ^ 1].w);
    }
}

int main() {
    n = read(); m = read(); T = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    for(int i = 1; i <= n; ++ i)
        b[i] = read();
    for(int i = 1; i <= n; ++ i) {
        int con1 = (a[i] + b[i]) % m + 1;
        int con2 = (a[i] - b[i] + m) % m + 1;
        int MIN = min(con1, con2);
        int MAX = max(con1, con2);
        int c = read();
        E[++ Cnt] = {c, Etot + 1};
        addedge(MAX, MIN, c);
        if(MAX != MIN) {
            c = read();
            E[++ Cnt] = {c, Etot + 1};
        }
        else
            c = 0;
        addedge(MIN, MAX, c);
    }
    for(int i = 1; i <= m; ++ i) {
        if(!bel[i]) {
            ++ setCnt;
            dfs1(i);
            //Confirm the id;
        }
    }
    memset(vis, 0, sizeof(vis));
    int ans = 0;
    for(int i = 1; i <= setCnt; ++ i) {
        Cir = 0;
        dfs2(*Set[i].begin());
        //Confirm the type
        //Confirm the direction
        if(CirNod[i]) {//the flag of JHS
            for(auto it : Set[i])
                if(nodCir[it])
                    dfs3(it, 0);
            //Confirm the edgOut
            ans += max(positiveKey[i], negativeKey[i]) + treeKey[i];
        }
        else {
            siz[i] = Set[i].size();
            Seg.build(Seg.rt[i], 1, Set[i].size());
            DFN = 0; dfs4(*Set[i].begin(), 0);
            //Confirm the siz and id on the tree
            ans += Seg.get(i);
        }
    }
    printf("%d\n", ans);
    
    q = read();
    while(q --) {
        int x = read() - T * ans;
        int y = read() - T * ans;
        int S = bel[e[E[x].id].t];
        if(CirNod[S]) {
            ans -= max(positiveKey[S], negativeKey[S]) + treeKey[S];
            if(edgCir[E[x].id] || edgCir[E[x].id ^ 1])
                if(edgCir[E[x].id])
                    positiveKey[S] += (y - E[x].c);
                else
                    negativeKey[S] += (y - E[x].c);
            else {
                if(edgOut[E[x].id])
                    treeKey[S] += (y - E[x].c);
            }
            ans += max(positiveKey[S], negativeKey[S]) + treeKey[S];
            E[x].c = y;
        }
        else {
            ans -= Seg.get(S);
            if(dfn[e[E[x].id].t] > dfn[e[E[x].id ^ 1].t]) {
                Seg.add(Seg.rt[S], 1, siz[S], 1, dfn[e[E[x].id].t] - 1, (y - E[x].c));
                Seg.add(Seg.rt[S], 1, siz[S], low[e[E[x].id].t] + 1, siz[S], (y - E[x].c));
            }
            else
                Seg.add(Seg.rt[S], 1, siz[S], dfn[e[E[x].id ^ 1].t], low[e[E[x].id ^ 1].t], (y - E[x].c));
            ans += Seg.get(S);
            E[x].c = y;
        }
        printf("%d\n", ans);
    }
    return 0;
}
Comments

添加新评论