Comet OJ 11/10模拟赛C / 分块

Posted on 2019-11-10 Edited on 2019-12-08 Views:

本地笔记整理~原稿写于11/10，2019/12/8上传

题意

若干年后。

主持魔法学院重建工作的 $\omega$ 坐在围墙上，与一旁的少女交谈。

「老师老师，你知道咱们学院是怎么传递信息的吗？」

「当然知道啊！」 $\omega$ 笑着摸了摸少女的头说道，「魔法学院有处地点，它们依次编号为到。我们搭设了条线路，第条线路连接号地点和号地点。当然，任意两处地点间都存在一条由线路构成的路径。」

少女调皮地歪了下脑袋。「但是老师，为什么我在号地点，经常收不到号地点的信息呢？」

「因为怕狡猾的敌人窃听我们啊。」 $\omega$ 回答道，「学院内部只使用个频道，每处地点分别会选择性地屏蔽一些频道。两处地点能够直接通信，当且仅当它们被一条线路所连接，且存在两处地点都没有屏蔽的频道。为了测评通讯质量，我们定义『通讯值』为最多能把处地点分成多少非空组，满足不同组内的地点无法直接通信。」

「这样一成不变的话，行动不是迟早会暴露在敌人面前吗？」

「是啊。所以我们打算轮流执行次修改，第次修改会改变号地点的频道屏蔽状态。现在我来考考你，在修改之前以及每次修改后，你能分别求出通讯值是多少吗？」

少女微微一笑，仿佛心中已有了答案。

这题目的题面，有点尬啊。

解法

考虑 u,v 如果 $S_u \cap S_v \neq \emptyset$ 那么 u,v 必在同一组内，因此若定义该条件为连边条件的话问题就变成了动态计算树子图的连通分量个数。

因为每一次都是单点修改，所以每次只要计算少连了多少边就可以得知答案增加了多少。

因此，问题被转化为如何快速计算一个节点所有相邻节点中与其集合交集非空的节点数，或者交集为空的节点数。

对于一般的树，暴力大约是足够了，时间复杂度就是 $\mathcal O(q\deg(u))$ ，但是对于菊花图 $\deg(u) = \mathcal{O}(n)$ ，于是乎就没了。

考虑转化为有根树，每个节点只有一个父亲，对于这个父亲我们现场算，我们接着维护一个数组 f[u][S] 表示的儿子当中集合为的节点个数，然后在询问时变为 $\mathcal O\left(2^m\right)$ 查询。在修改时 $\mathcal O(1)$ 修改父亲的数组值。

这当然是可以的，但是 $m\le 20$ 。还是不够。

注意到如果 $A \cap B = \emptyset$ ，那么 $B \subseteq \overline A$ ，因此，我们还可以维护数组 f[u][S] 记录的儿子中集合为的子集的节点数，询问便是 $f[u][\overline{S_u}]$ ，变成了 $\mathcal O(1)$ 的复杂度，倒是修改变为了 $\mathcal O\left(2^m\right)$ 。依然不行。

考虑合并两种解法，对于集合的前 $\left\lfloor \frac{m}{2} \right\rfloor$ 种元素，我们用第一种方法，对于集合的后 $\left\lceil \frac{m}{2} \right\rceil$ 种元素，我们用第二种方法，那么单次的查询修改就都到了 $\mathcal O\left(2^{m\over 2}\right)$ 。时间复杂度上是能通过该题了。

但是这张表要 $\mathcal O\left(n2^m\right)$ 的空间不就炸了吗？

为了解决炸空间的问题，我们只选择度数大于使用这种方法，对于小度数的节点暴力就完事了。

总体复杂度就是 $\mathcal O \left(nd + \frac{n}{d}2^{m\over 2}\right)$ 。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
const int MS = 1 << 10;
const int D = 200;
const int T = 500;
int n, m, fa[N], w[N], all, tp, ans = 0;
int fst[N], nxt[2 * N], to[2 * N], tot = 1;
int f[D][MS][MS], id[N], cnt = 0 , deg[N];
void link(int u, int v) {
    deg[u]++; deg[v]++;
    nxt[++tot] = fst[u];
    fst[u] = tot; to[tot] = v;
}
void dfs(int u, int p) {
    fa[u] = p;
    for (int e = fst[u]; e; e = nxt[e])
        if (to[e] != p) dfs(to[e], u);
}
inline int readbin() {
    char s[22]; scanf("%s", s);
    int ans = 0;
    for (int i = 0; i < m; i++)
        ans = (ans << 1) | (s[i] - '0');
    return ans;
}
void modify(int u, int x, int d) {
    int k = id[u];
    int mask = (1 << tp) - 1;
    int fr = x >> tp, bk = x & mask, c = mask ^ bk;
    for (int s = c; s; s = c & (s - 1))
        f[k][fr][mask ^ s] += d;
    f[k][fr][mask] += d;
}
int query(int u, int x) {
    int k = id[u];
    x = all ^ x;
    int mask = (1 << tp) - 1;
    int fr = x >> tp, bk = x & mask, ans = 0;
    for (int s = fr; s; s = fr & (s - 1))
        ans += f[k][s][bk];
    return ans + f[k][0][bk];
}
void solve() {
    all = (1 << m) - 1;
    tp = (m + 1) / 2;
    for (int i = 1; i <= n; i++) 
        if (deg[i] > T) id[i] = ++cnt;
    for (int i = 1; i <= n; i++)
        if (id[fa[i]]) modify(fa[i], w[i], 1);
    int Q; scanf("%d", &Q);
    while (Q--) {
        int x, c; scanf("%d ", &x);
        c = readbin();
        int last = 0, now = 0;
        if (id[x]) {
            last = query(x, w[x]);
            now = query(x, c);
            if (fa[x]) {
                last += (w[x] & w[fa[x]]) == 0;
                now += (c & w[fa[x]]) == 0;
            }
        } else {
            for (int e = fst[x]; e; e = nxt[e]) {
                last += (w[x] & w[to[e]]) == 0;
                now += (c & w[to[e]]) == 0;
            }
        }
        printf("%d\n", (ans += now - last));
        if (id[fa[x]]) {
            modify(fa[x], w[x], -1);
            modify(fa[x], c, 1);
        }
        w[x] = c; 
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        link(u, v); link(v, u);
    }
    for (int i = 1; i <= n; i++) w[i] = readbin(); 
    dfs(1, 0); ans = n;
    for (int i = 2; i <= n; i++) if (w[i] & w[fa[i]]) ans--;
    printf("%d\n", ans);
    solve();
    return 0;
}