NOI Online 提高组 T1 序列

George_Plover · 2020-03-07 20:22:37 · 题解

这场神奇的比赛要从一只蝙蝠说起？

题意：

给出一个长度为n序列a_i，需要通过一系列操作，把该序列变为目标序列b_i

操作一共有m种，每种操作描述为(t,u,v)

t=1$ ，则可以令$a_u$与$a_v$同时加$1$或减$1$，当$u=v$时相当于这个位置加或减了$2

每种操作的使用次数无限制。

n,m\leq 10^5 \ \ \ \ a_i,b_i\leq 10^9

这个题一读起来就非常amazing啊，感觉不怎么好直接下手，乍一看连搜索都不怎么好写，所以要尝试挖掘一下性质。

首先映入眼帘的的当然是操作t=2的时候，两个元素可以相互传递任意的数值，互帮互助，完全就是形成了 命运共同体 嘛！对于这样的两个位置u和v，我们就可以放宽限制了，因为只需要满足a_u+a_v=b_u+b_v之后，两者之间交换一些数值，就能使得 a_u=b_u , a_v=b_v 。所以我们能将这两个位置看成一个整体。

接下来，我们再来考虑一下操作t=1的时候有什么性质。

说实话我觉得这个性质不那么明显，我在家里来回兜圈的时候突然意识到了这个性质……

如果我们有操作(1,i,j)与(1,j,k)可以使用，如果我让a_i,a_j同增1，a_j,a_k同减1，那么就实现了a_i增1,a_k减1。同理，可以实现a_i减1,a_k增1。也就是说，利用j这个位置，我们实现了i和k的命运共同体！相当于拥有了操作(2,i,k),可以把i和k位置看成一个整体了。

进一步，如果我们把每个操作(1,u,v)视为一条边，那么对任意一个点u，我们发现，所有与u直接相连的点必定属于同一个命运共同体 集合。

于是我们运用图论知识，只对操作t=1考虑并且建边。如果一个连通图是二分图，利用上述性质，该连通图的点集一定会被划分为两个集合。如果不是二分图，那么这个连通图的所有点一定会被划分在同一个集合。

我们上面已经分析过了，每个集合可以看成一个需要让\sum a_i变成\sum b_i的点。

这么看来，我们建的图可能有很多个连通块，而每个连通块都可以被处理成为单点或者双点图。

但是还有一个问题，有一些操作是t=2，我们没法通过建图实现这个条件……我想到的解决办法，是对每个t=2的操作建虚拟点。把操作(2,u_i,v_i)拆为操作(1,u_i,n+i)和(1,v_i,n+i)。并且令a_{n+i}=b_{n+i}=0。这样，就准确的将每个t=2操作拆成了两个t=1操作，也就可以愉快的通过建边来满足题目要求了。

最后我们对每个连通子图进行考虑。

一共三种情况：

孤儿点 \ \ \ \ 这个连通子图由单独的一个点组成，连自环都没有，只能听天由命，如果a_i \ne b_i就可以直接输出”NO“了
单集合 \ \ \ \ 这个连通块所有点属于同一个集合，内部存在边，于是能且仅能实现自增2的倍数的操作，所以如果\sum a_i-\sum b_i不是2的倍数，就可以输出“NO”了。
双集合 \ \ \ \ 这个连通块是个二分图，能分成两个集合，（注意这两个集合的内部是没有边的，否则就不是二分图了）两个集合之间有连边，所以可以实现同增同减。如果\sum a_{i_1}-\sum b_{i_1}\ne\sum a_{i_2}-\sum b_{i_2},那么也可以输出“NO”了

考察了所有情况之后，如果没有问题的话，输出YES即可。

再考虑复杂度，这里划分集合可以采用并查集，带上路径压缩，由于此题数据范围不大，这里可以视为常数级别。而所有的建边都是基于操作数m和序列长度n的，复杂度可视为\Omega (n+m)

代码是比赛的时候写的，在中途变化过思路，比较丑陋，仅作参考

#define George_Plover
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define MAXN 200001
#define MAXM 400001

using namespace std;
int n,m,T;
int tot,pre[MAXN],to[MAXM],lin[MAXM];
LL a[MAXN],b[MAXN];
int fa[MAXN];
struct OP{
    int t,u,v;
}p[MAXN];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void add(int x,int y)
{
    tot++;
    lin[tot]=pre[x];
    pre[x]=tot;
    to[tot]=y;
}
void merge(int x,int y)
{
    int u=find(x),v=find(y);
    if(u==v)return;
    a[u]+=a[v];
    b[u]+=b[v];
    fa[v]=u;
}
void init()
{
    for(int i=1;i<=n+m;i++)
        fa[i]=i;
    memset(pre,0,sizeof(pre));
    tot=0;
}
int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&b[i]);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&p[i].t,&p[i].u,&p[i].v);
            a[i+n]=b[i+n]=0;
            if(p[i].t==1)
            {
                add(p[i].u,p[i].v);
                add(p[i].v,p[i].u);
            }
            else
            {
                add(i+n,p[i].v);
                add(p[i].v,i+n);
                add(i+n,p[i].u);
                add(p[i].u,i+n);
            }
        }

        for(int i=1;i<=n+m;i++)
        {
            int tmp=0;
            for(int j=pre[i];j;j=lin[j])
            {
                int v=to[j];
                if(tmp)
                {
                    merge(tmp,v);
                }
                tmp=v;
            }
        }
        bool flag=1;
        for(int i=1;i<=n;i++)
        {
            int j=to[pre[i]];
            if(!pre[i])
            {
                if(a[i]!=b[i])
                {
                    flag=0;
                    break;
                }
                continue;
            }
            int l=find(i),r=find(j);
            if(l==r)
            {
                if((a[l]-b[l])&1)
                {
                    flag=0;
                    break;
                }
                continue;
            }
            if(a[l]-b[l]!=a[r]-b[r])
            {
                flag=0;
                break;
            }
        }
        if(flag)
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
    }
    return 0;
}