「NOI Online」序列

传送门

首先讲句题外话：这篇题解应该是思路和代码实现都很简单的类型了 ~~所以你都点进来了怎么能不看呢~~

首先我们来分析一下这两种序列上的操作：

我们发现2操作可以看成是两个点 \(u, v\) 之间相互传递一部分数值，一边加上的刚好等于另一边减去的。

我们便尝试连边 \((u, v)\) 表示这两个点之间有传递关系 注意本文讲到的连边都是指连双向边

1操作的话就不太好办了，因为我们无法通过直接连边，来确保两个点的值同时变化相同的数值。

那么1操作能不能转变成2操作呢？

我们回到题面：要求若干次操作后 \(a_i = b_i\) 。

一般的想法都是直接去弥补值之间的差值，但是我们可以知道的是，两个点如果同时加上或减去一个数，它们的差值也是不会改变的。

所以我们可以拓宽思路，把 \(a_i\) 向 \(b_i\) 的单向转变，化作 \(a_i\) 和 \(b_i\) 的数值在两者经过若干次操作后的相等。

接下来我们就要通过改变 \(a_i\) 和 \(b_i\) 的值来实现单个位置 +1 或 -1 的操作了。

下面我们就用 \(i\) 来代表 \(a_i\) 对应的点的编号，\(i^{\prime}\) 来表示 \(b_i\) 对应的点的编号。

那么首先对于可以执行2操作的一对点 \((u, v)\) ，我们就可以连边 \((u, v), (u^{\prime}, v^{\prime})\) 表示这两个点的 \(a_i\) 和 \(b_i\) 之间都分别可以进行上文讲到的数值传递。

对于1操作的一对点 \((u, v)\) ，我们这样连边：

如果我们是想让 \(a_u\) 和 \(a_v\) 的值都加上1，那么连边 \((u^{\prime}, v)\)；

如果我们是想让 \(a_u\) 和 \(a_v\) 的值都减去1，那么连边 \((u, v^{\prime})\)；

为什么这样可行呢？因为我们之前提到了，\(a_i\) 和 \(b_i\) 需要在各自经过若干次操作后相等，那么我们可以认为 \(a_i\) 和 \(b_i\) 的大小是相对的，通过改变其中一个的值，就可以达到改变另一个值的目的。

那么我们再来分析一下这样的连边过程：连边 \((u^{\prime}, v)\) ，表示 \(b_u\) 和 \(a_v\) 之间可以传递数值。

那么我们如果让 \(b_u\) 加上1，\(a_v\) 减去1，进行这样一次数值传递的话，就 \(a_u\) 和 \(b_u\) 的大小而言，\(b_u\) 加上1，等价于让 \(a_u\) 减去1，也就是说我们整体上就实现了两个位置同时-1的操作，+1 的操作同理。

那么我们就得到了一张图。

这张图可能有很多个连通块，那么根据之前对于数值传递的定义，同一个连通块内的任意两个点都可以直接或间接地进行数值传递 。

而且不难发现所有连出来的边都是对称的，也就是说 这张图是轴对称的 。

既然图是对称的，那么 \(i\) 和 \(i^{\prime}\) 要么在同一个连通块内，要么就是分居两个对称的连通块。

如果这两个点位于同一个连通块，我们就只需要让这个大联通块的内部数值总和为偶数即可。

因为在这个联通块内，我们可以随意地进行数值传递操作，所以我们只需要关心数值的总和，又因为这个连通块是对称的，我们就需要得出一种可以让两边的数值也对称的方案，那么很显然只有总和为偶数的时候才能做到。

分居两个连通块就更好判断了，直接判断两个连通块各自的内部数值总和是否相等即可。

那么到这里我们就完美地解决了这道题了，复杂度 \(O(Tn)\) 。

参考代码：

#include <cstring>
#include <cstdio>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
template < class T > inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
    s = f ? -s : s;
}

typedef long long LL;
const int _ = 2e5 + 5;

int tot, head[_]; struct Edge { int v, nxt; } edge[_ << 1];
inline void Add_edge(int u, int v) { edge[++tot] = (Edge) { v, head[u] }, head[u] = tot; }
inline void link(int u, int v) { Add_edge(u, v), Add_edge(v, u); }

int n, m, val[_], num, pos[_]; LL sum[_];

inline void init() {
    num = tot = 0;
    memset(head, 0, sizeof head);
    memset(sum, 0, sizeof sum);
    memset(pos, 0, sizeof pos);
}

inline void dfs(int u, int p) {
    sum[pos[u] = p] += val[u];
    for (rg int i = head[u]; i; i = edge[i].nxt)
        if (!pos[edge[i].v]) dfs(edge[i].v, p);
}

inline void solve() {
    init(), read(n), read(m);
    for (rg int i = 1; i <= n << 1; ++i) read(val[i]);
    for (rg int t, x, y, i = 1; i <= m; ++i) {
        read(t), read(x), read(y);
        if (t == 1) link(x, y + n), link(y, x + n);
        if (t == 2) link(x, y), link(x + n, y + n);
    }
    for (rg int i = 1; i <= n << 1; ++i) if (!pos[i]) dfs(i, ++num);
    int flag = 1;
    for (rg int i = 1; i <= n; ++i) {
        if (pos[i] != pos[i + n])
            flag &= sum[pos[i]] == sum[pos[i + n]];
        else
            flag &= sum[pos[i]] % 2 == 0;
    }
    puts(flag ? "YES" : "NO");
}

int main() {
    file("sequence");
    int T; read(T);
    while (T--) solve();
    return 0;
}

「NOI Online」序列

「NOI Online」序列

推荐阅读