题解 P6185 【[NOI Online 提高组]序列（民间数据）】
Damo
2020-03-09 10:06:08
# 思路
大家都太强了……看了半天都是图论大神。
我只好写一个蒟蒻的做法，小小的 __带权并查集__。
我是这么想哒，考虑 $i,j$ 和 $j,k$ 两种操作，能够给 $i,k$ 带来什么：
- 如果 $i,j$ 是可以同时增加的，而 $j,k$ 也是可以同时减少的，那么 $i,j$ 同时增加 $x$ ，$j,k$ 同时减少 $x$ ，完美地做到了 $i,k$ 一个增加、一个减少。
- 如果 $i,j$ 是可以同时增加的，而 $j,k$ 是一加一减的，那么 $i,k$ 通过 $j$ 这个中介，就可以做到 $i$ 增加一、$k$ 也增加一。
- 如果都是一加一减型，那么可以认为存在一个 $i,k$ 的一加一减型。
所以说，对于这种三个点的关系，其中一个作为中介的时候，如果 $i,j$ 和 $j,k$ 的状态不同，就可以做到同时增加；否则得到一增一减的结果。
于是，__把同时增加设为$1$、一增一减设为$0$，连边之后，二者的关系为路径的异或和__。而且，这也是自洽的，因为自己到自己的长度是$0$，相当于增加了又减少，没有问题。
然后就有了带权并查集的思路，因为 __所有的操作可以等价于直接与并查集的根操作__，毕竟是异或和，$dis(a,rt)\oplus dis(b,rt)=dis(a,b)$ 嘛，所以 $a,b$ 本来就可以选择 $root$ 作为中介点。
加出来一个环怎么办？如果这会导致一个长度为$1$的环，那么在根节点上打一个标记，表示“__可以自行消化偶数权值__”。否则，没什么鸟用，因为每个节点本身就有一个隐藏的长度为零的自环。
最后，暴力检查每一个根节点是否达到了要求即可，因为根节点就已经没有人能够跟它操作了，除了自环消化偶数。
我没有打启发式合并，普通的路径压缩，最坏是 $\mathcal O(n\log n)$ 的。还是能过。
~~却因为没有清空挂掉了。事实上，三道题都因为奇怪的原因挂掉了~~
# 代码
实现的时候，可以只存储 $b_i-a_i$ ，也就是 $a_i$ 需要的变化量。
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
inline long long readint(){
long long a = 0; char c = getchar(), f = 1;
for(; c<'0'||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
inline void writeint(long long x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) writeint(x/10);
putchar((x%10)^48);
}
# define MB template < typename T >
MB void getMax(T &a,const T &b){ if(a < b) a = b; }
MB void getMin(T &a,const T &b){ if(b < a) a = b; }
const int MaxN = 100005;
int fa[MaxN], val[MaxN];
inline int findSet(int a){
if(fa[a] == a) return a;
int root = findSet(fa[a]);
val[a] ^= val[fa[a]];
return fa[a] = root;
}
bool win[MaxN]; // 是否有长度为1的自环
void unionSet(int a,int b,int c){
int x = findSet(a), y = findSet(b);
int dis = val[a]^c^val[b];
if(x == y) win[x] = win[x] or dis == 1;
else{
fa[x] = y, val[x] = dis;
win[y] = win[y] or win[x];
}
}
long long a[MaxN]; int n, m;
int main(){
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);
for(int T=readint(); T; --T){
n = readint(), m = readint();
for(int i=1; i<=n; ++i){
a[i] = readint();
fa[i] = i, val[i] = 0;
win[i] = false;
}
for(int i=1; i<=n; ++i)
a[i] = readint()-a[i];
for(int opt,x; m; --m){
opt = readint()%2, x = readint();
unionSet(x,readint(),opt);
}
for(int i=1,rt; i<=n; ++i){
rt = findSet(i);
if(rt == i) continue;
if(val[i] == 1) // a[i]-=a[i],a[rt]-=a[i]
a[rt] -= a[i]; // 权值同时增加a[i] ...
else a[rt] += a[i]; // ... 需求便减少了
}
bool ok = true;
for(int i=1,rt; i<=n and ok; ++i){
rt = findSet(i);
if(rt != i) continue;
if(win[rt]) a[rt] %= 2;
if(a[rt] != 0) ok = false;
}
if(ok) puts("YES"); else puts("NO");
}
return 0;
}
```
也许是错的——希望有大佬在看出错误之后 ~~心狠手辣地、尖酸刻薄地~~ 指出，受教了！