题解：P14963 [LBA-OI R2 B] 何意味

· · 题解

前言

题目传送门。

感谢出题人的这道题，使我多积累一个 trick，并引发我的一系列思考。

不足或补充欢迎大家指出。

思路

注意到只要满足 a_i=a_{i+1}，那么这两个数就可以消去或增加。

所以对于一组询问 l,r，我们只要将 a_l 到 a_r 相邻相同的尽可能消去，b 的操作同理。比较 a,b 消去后的序列，如果相同，输出 Yes。

由此我们得到 30 分的代码：

::::info[code]

#include<cstdio>
#include<vector>
using namespace std;
const int N=5e5+10;

int a[N],b[N];
vector <int> c,d;

void read()
{
    return ;
}

template <typename T,typename ...Args>
void read(T &x,Args &...args)
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    read(args...);
}

bool check()
{
    for(int i=0;i<c.size();i++)
    {
        if(c[i]!=d[i]) return false;
    }
    return true;
}

int main()
{
    int n,m,opt,l1,r1,l2,r2,x,y;
    read(n,m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]);
    for(int i=1;i<=m;i++)
    {
        read(opt);
        if(opt==1)
        {
            read(l1,r1,l2,r2);
            c.clear();  d.clear();
            c.push_back(-1);  d.push_back(-1);
            for(int j=l1;j<=r1;j++)
            {
                if(a[j]==c.back()) c.pop_back();
                else c.push_back(a[j]);
            }
            for(int j=l2;j<=r2;j++)
            {
                if(b[j]==d.back()) d.pop_back();
                else d.push_back(b[j]);
            }
            if(c.size()==d.size())
            {
                if(check()) puts("Yes");
                else puts("No");
            }
            else puts("No");
        }
        else if(opt==2)
        {
            read(x,y);
            a[x]=y;
        }
        else
        {
            read(x,y);
            b[x]=y;
        }
    }
    return 0;
}

::::

我又对其进行了分块处理，虽然按理来说时间复杂度仍然是 \mathcal O(n^2)，但是实际能得 45 分，然后我就止步与此了。

::::info[分块 code]

#include<cstdio>
#include<vector>
using namespace std;
const int N=5e5+1000;
const int B=700;

int a[N],b[N],aa[B+20][B+20],bb[B+20][B+20],len[2][N];
vector <int> c,d;

void read()
{
    return ;
}

template <typename T,typename ...Args>
void read(T &x,Args &...args)
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    read(args...);
}

bool check()
{
    for(int i=0;i<c.size();i++)
    {
        if(c[i]!=d[i]) return false;
    }
    return true;
}

void solve(int L,int R,vector <int> &e,int (*f)[B+20],int *g,int opt)
{
    int l=(L+B-1)/B,r=(R+B-1)/B,ll,rr;
    if(l==r)
    {
        for(int i=L;i<=R;i++)
        {
            if(g[i]==e.back()) e.pop_back();
            else e.push_back(g[i]);
        }
    }
    else
    {
        rr=l*B;
        for(int i=L;i<=rr;i++)
        {
            if(g[i]==e.back()) e.pop_back();
            else e.push_back(g[i]);
        }
        for(int i=l+1;i<r;i++)
        {
            ll=(i-1)*B+1;  rr=i*B;
            for(int j=1;j<=len[opt][i];j++)
            {
                if(f[i][j]==e.back()) e.pop_back();
                else e.push_back(f[i][j]);
            }
        }
        ll=(r-1)*B+1;
        for(int i=ll;i<=R;i++)
        {
            if(g[i]==e.back()) e.pop_back();
            else e.push_back(g[i]);
        }
    }
}

void update(int x,int y,int *f,int (*g)[B+20],int opt)
{
    f[x]=y;
    int cnt=(x+B-1)/B,l,r;
    l=(cnt-1)*B+1;  r=cnt*B;
    len[opt][cnt]=0;
    for(int i=l;i<=r;i++)
    {
        if(len[opt][cnt]&&f[i]==g[cnt][len[opt][cnt]]) len[opt][cnt]--;
        else g[cnt][++len[opt][cnt]]=f[i];
    }
}

int main()
{
    int n,m,opt,l1,r1,l2,r2,x,y;
    read(n,m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]);
    int l,r,cnt;
    cnt=(n/B)+1;
    for(int i=1;i<=cnt;i++)
    {
        l=(i-1)*B+1;  r=i*B;
        for(int j=l;j<=r;j++)
        {
            if(len[0][i]&&a[j]==aa[i][len[0][i]]) len[0][i]--;
            else aa[i][++len[0][i]]=a[j];
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        l=(i-1)*B+1;  r=i*B;
        for(int j=l;j<=r;j++)
        {
            if(len[1][i]&&b[j]==bb[i][len[1][i]]) len[1][i]--;
            else bb[i][++len[1][i]]=b[j];
        }
    }
    for(int i=1;i<=m;i++)
    {
        read(opt);
        if(opt==1)
        {
            read(l1,r1,l2,r2);
            c.clear();  d.clear();
            c.push_back(-1);  d.push_back(-1);
            solve(l1,r1,c,aa,a,0);
            solve(l2,r2,d,bb,b,1);
            if(c.size()==d.size())
            {
                if(check()) puts("Yes");
                else puts("No");
            }
            else puts("No");
        }
        else if(opt==2)
        {
            read(x,y);
            update(x,y,a,aa,0);
        }
        else
        {
            read(x,y);
            update(x,y,b,bb,1);
        }
    }
    return 0;
}

::::

正解

发现我们的操作只是需要消去相邻相同的数，所以我们立刻想到了异或 hash，但是显然不仅仅如此。

例如 a_i=a_j,i<j，但是 a_i 到 a_j 中的数不能全部消除，我们普通异或也会将其抵消。

所以我们要有一种满足：

对于不满足交换律，我们可以想到熟悉的矩阵。至于第一个条件，就是我们构造矩阵的方向。

所以定义一个 2\times 2 的矩阵：

\begin{pmatrix} a,b\\ c,d \end{pmatrix}

矩阵的单位元当然是：

\begin{pmatrix} 1,0\\ 0,1 \end{pmatrix}

所以有：

\begin{pmatrix} a,b\\ c,d \end{pmatrix} \times \begin{pmatrix} a,b\\ c,d \end{pmatrix} = \begin{pmatrix} 1,0\\ 0,1 \end{pmatrix}

展开可得：

\left\{ \begin{align} a^2+bc=1\qquad\\ ab+bd=0\qquad\\ ac+cd=0\qquad\\ bc+d^2=1\qquad \end{align} \right.

不妨令 a,b,c,d 均不为 0。

对于 (2)：b\times(a+d)=0，(3) 同理。

可得 a=-d，发现同时满足 (1),(4) 能推导出的式子。

然后考虑 b,c。

由 (1)，bc=1-a^2=(1-a)\times(1+a)，不妨就令 b=1-a,c=1+a。

所以我们用 a 来作为变量，可以构造矩阵：

\begin{pmatrix} a,1-a\\ 1+a,-a \end{pmatrix}

::::info[补充] 对于上面的推导，是令 a,b,c,d 均不为 0。

但是如果 a=d，那么由 (2),(3)，b=c=0。

又由 (1),(4)，可以得出 a=d=1 或 a=d=-1。

这样所有值都确定了，相当于构造了个寂寞。所以上面只写令其均不为 0。

综上 a=-d 是必须的，至于 b,c 的选择，只需要满足 bc=1-a^2 即可，可以随便构造。

这篇题解 的 b,c 构造方法就相对麻烦了一点（并无恶意），但也是可行的。 ::::

这样我们就得出了最终做法，先用异或 hash，再用上面的方法对每个数构造矩阵，然后写个线段树维护区间矩阵乘积，单点修改，区间查询，最后每次查询看所得的矩阵是否相等就行了。

代码实现我用的是自然溢出，跑得挺快的，目前还在第一页。不放心的话可以加上取模。

::::info[code]

#include<cstdio>
#include<random>
#include<algorithm>
# define gc() (p1==p2&&(p2=(p1=buffer)+fread(buffer,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
typedef unsigned int UI;
const int N=5e5+10;
const int MAXN=5e5;

char buffer[1<<20],*p1,*p2;
UI a[N],b[N],tmp[2][2],ans[2][2][2],X[N];
struct heyiwei
{
    struct segnote
    {
        UI g[2][2];
        void cheng(UI (*x)[2],UI (*y)[2])  //维护线段树节点的 push_up
        {
            g[0][0]=x[0][0]*y[0][0]+x[0][1]*y[1][0];
            g[0][1]=x[0][0]*y[0][1]+x[0][1]*y[1][1];
            g[1][0]=x[1][0]*y[0][0]+x[1][1]*y[1][0];
            g[1][1]=x[1][0]*y[0][1]+x[1][1]*y[1][1];
        }
        void cal(UI (*x)[2]) //查询用的矩阵乘法
        {
            tmp[0][0]=x[0][0];  tmp[0][1]=x[0][1];
            tmp[1][0]=x[1][0];  tmp[1][1]=x[1][1];
            x[0][0]=g[0][0]*tmp[0][0]+g[0][1]*tmp[1][0];
            x[0][1]=g[0][0]*tmp[0][1]+g[0][1]*tmp[1][1];
            x[1][0]=g[1][0]*tmp[0][0]+g[1][1]*tmp[1][0];
            x[1][1]=g[1][0]*tmp[0][1]+g[1][1]*tmp[1][1];
        }
    }segtree[N<<2];
    void build_tree(int x,int left,int right,UI *c)
    {
        if(left==right)
        {
            segtree[x].g[0][0]=c[left];  segtree[x].g[0][1]=1-c[left];
            segtree[x].g[1][0]=1+c[left]; segtree[x].g[1][1]=-c[left];
            return ;
        }
        int mid=(left+right)>>1;
        build_tree(x<<1,left,mid,c);
        build_tree(x<<1|1,mid+1,right,c);
        segtree[x].cheng(segtree[x<<1].g,segtree[x<<1|1].g);
    }

    void update(int x,int pos,int k,int l,int r)
    {
        if(l==r)
        {
            segtree[x].g[0][0]=k;  segtree[x].g[0][1]=1-k;
            segtree[x].g[1][0]=1+k; segtree[x].g[1][1]=-k;
            return ;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) update(x<<1,pos,k,l,mid);
        else update(x<<1|1,pos,k,mid+1,r);
        segtree[x].cheng(segtree[x<<1].g,segtree[x<<1|1].g);
    }

    void query(int x,int left,int right,int opt,int l,int r)
    {
        if(left<=l&&r<=right)
        {
            segtree[x].cal(ans[opt]);
            return ;
        }
        int mid=(l+r)>>1;
        // 注意乘的顺序，我是每次右乘，故先算右边。具体因人而异
        if(right>mid) query(x<<1|1,left,right,opt,mid+1,r);
        if(left<=mid) query(x<<1,left,right,opt,l,mid);
    }
}A,B;

void read()
{
    return ;
}

template <typename T,typename ...Args>
void read(T &x,Args &...args)
{
    x=0;
    char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=gc();
    }
    read(args...);
}

void init()// 随机数 异或 hash
{
    random_device r;
    mt19937 d(r());
    uniform_int_distribution <int> rnd(1,2000000000);
    for(int i=0;i<=MAXN;i++) X[i]=rnd(d);
}

bool check()
{
    if(ans[0][0][0]==ans[1][0][0]&&ans[0][0][1]==ans[1][0][1]&&ans[0][1][0]==ans[1][1][0]&&ans[0][1][1]==ans[1][1][1]) return true;
    return false;
}

int main()
{
    init();
    int n,m,l1,r1,l2,r2,x,y,opt;
    read(n,m);
    for(int i=1;i<=n;i++) read(a[i]),a[i]=X[a[i]];
    for(int i=1;i<=n;i++) read(b[i]),b[i]=X[b[i]];
    A.build_tree(1,1,n,a);
    B.build_tree(1,1,n,b);
    for(int i=1;i<=m;i++)
    {
        read(opt);
        if(opt==1)
        {
            read(l1,r1,l2,r2);
            ans[0][0][0]=ans[1][0][0]=ans[0][1][1]=ans[1][1][1]=1;
            ans[0][0][1]=ans[1][0][1]=ans[0][1][0]=ans[1][1][0]=0;
            A.query(1,l1,r1,0,1,n);
            B.query(1,l2,r2,1,1,n);
            if(check()) puts("Yes");
            else puts("No");
        }
        else if(opt==2)
        {
            read(x,y);
            y=X[y];
            A.update(1,x,y,1,n);
        }
        else
        {
            read(x,y);
            y=X[y];
            B.update(1,x,y,1,n);
        }
    }
    return 0;
}

::::

深入探究

矩阵运算

不感兴趣的可以跳过了。

还是用矩阵维护，但是我们可以用另外的方法，就是自定义矩阵运算法则。

可以看具体的应用 动态 DP。

我们在此题肯定不能用较高级的方法做，结果啥用没有，所以我们来研究位运算的法则。

我们把位运算都想一遍，能满足自定义矩阵乘法的就只用 \operatorname{or},\operatorname{and}（具体怎么样才满足还是见动态 DP 题解吧，我此处只是提供一种方法和思路）。

还是简略说一下：因为只有这两个运算满足分配律。

然后此处有两种选择：

对于第 2 个，我发现不存在构造方案，可以满足自身操作自身等于单位元（可能是我太菜了）。

但是第 (1) 个我找到了，令 e 为所有位数全一的数。

可以构造矩阵：

\begin{pmatrix} a,\operatorname{not}a\\ \operatorname{not}a,a \end{pmatrix}

单位元是：

\begin{pmatrix} 0,e\\ e,0 \end{pmatrix}

但是我写完发现跑的比普通的慢，为什么此处位运算比乘法和加法慢，我不理解了，其他地方几乎一样，希望这个方法仍有参考价值。

::::info[code]

#include<cstdio>
#include<random>
#include<algorithm>
# define e 4294967295u
# define gc() (p1==p2&&(p2=(p1=buffer)+fread(buffer,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
typedef unsigned int UI;
const int N=5e5+10;
const int MAXN=5e5;

char buffer[1<<20],*p1,*p2;
UI a[N],b[N],tmp[2][2],ans[2][2][2],X[N];
struct heyiwei
{
    struct segnote
    {
        UI g[2][2];
        void cheng(UI (*x)[2],UI (*y)[2]) //此处不同
        {
            g[0][0]=(x[0][0]|y[0][0])&(x[0][1]|y[1][0]);
            g[0][1]=(x[0][0]|y[0][1])&(x[0][1]|y[1][1]);
            g[1][0]=(x[1][0]|y[0][0])&(x[1][1]|y[1][0]);
            g[1][1]=(x[1][0]|y[0][1])&(x[1][1]|y[1][1]);
        }
        void cal(UI (*x)[2])
        {
            tmp[0][0]=x[0][0];  tmp[0][1]=x[0][1];
            tmp[1][0]=x[1][0];  tmp[1][1]=x[1][1];
            x[0][0]=(g[0][0]|tmp[0][0])&(g[0][1]|tmp[1][0]);
            x[0][1]=(g[0][0]|tmp[0][1])&(g[0][1]|tmp[1][1]);
            x[1][0]=(g[1][0]|tmp[0][0])&(g[1][1]|tmp[1][0]);
            x[1][1]=(g[1][0]|tmp[0][1])&(g[1][1]|tmp[1][1]);
        }
    }segtree[N<<2];
    void build_tree(int x,int left,int right,UI *c)
    {
        if(left==right)
        {
            segtree[x].g[0][0]=c[left];  segtree[x].g[0][1]=~c[left];  //此处不同
            segtree[x].g[1][0]=~c[left]; segtree[x].g[1][1]=c[left];
            return ;
        }
        int mid=(left+right)>>1;
        build_tree(x<<1,left,mid,c);
        build_tree(x<<1|1,mid+1,right,c);
        segtree[x].cheng(segtree[x<<1].g,segtree[x<<1|1].g);
    }

    void update(int x,int pos,int k,int l,int r)
    {
        if(l==r)
        {
            segtree[x].g[0][0]=k;  segtree[x].g[0][1]=~k;
            segtree[x].g[1][0]=~k; segtree[x].g[1][1]=k;  //此处不同
            return ;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) update(x<<1,pos,k,l,mid);
        else update(x<<1|1,pos,k,mid+1,r);
        segtree[x].cheng(segtree[x<<1].g,segtree[x<<1|1].g);
    }

    void query(int x,int left,int right,int opt,int l,int r)
    {
        if(left<=l&&r<=right)
        {
            segtree[x].cal(ans[opt]);
            return ;
        }
        int mid=(l+r)>>1;
        if(right>mid) query(x<<1|1,left,right,opt,mid+1,r);
        if(left<=mid) query(x<<1,left,right,opt,l,mid);
    }
}A,B;

void read()
{
    return ;
}

template <typename T,typename ...Args>
void read(T &x,Args &...args)
{
    x=0;
    char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=gc();
    }
    read(args...);
}

void init()
{
    random_device r;
    mt19937 d(r());
    uniform_int_distribution <int> rnd(1,2000000000);
    for(int i=0;i<=MAXN;i++) X[i]=rnd(d);
}

bool check()
{
    if(ans[0][0][0]==ans[1][0][0]&&ans[0][0][1]==ans[1][0][1]&&ans[0][1][0]==ans[1][1][0]&&ans[0][1][1]==ans[1][1][1]) return true;
    return false;
}

int main()
{
    init();
    int n,m,l1,r1,l2,r2,x,y,opt;
    read(n,m);
    for(int i=1;i<=n;i++) read(a[i]),a[i]=X[a[i]];
    for(int i=1;i<=n;i++) read(b[i]),b[i]=X[b[i]];
    A.build_tree(1,1,n,a);
    B.build_tree(1,1,n,b);
    for(int i=1;i<=m;i++)
    {
        read(opt);
        if(opt==1)
        {
            read(l1,r1,l2,r2);
            ans[0][0][0]=ans[1][0][0]=ans[0][1][1]=ans[1][1][1]=0;  //此处不同
            ans[0][0][1]=ans[1][0][1]=ans[0][1][0]=ans[1][1][0]=e;
            A.query(1,l1,r1,0,1,n);
            B.query(1,l2,r2,1,1,n);
            if(check()) puts("Yes");
            else puts("No");
        }
        else if(opt==2)
        {
            read(x,y);
            y=X[y];
            A.update(1,x,y,1,n);
        }
        else
        {
            read(x,y);
            y=X[y];
            B.update(1,x,y,1,n);
        }
    }
    return 0;
}

:::: ::::warning[警告] 但是我把自己 hack 了，我发现这样做会有一种奇妙的性质。

令 a,b 为两个不同矩阵，我这样算会出现：a\otimes b\otimes a=b，这显然是不符合预期的，也就是说这样隔一个也能消去，但是隔多个消不去。

但是由于数据较水，代码还是过去了。

给出一组数据：

3 1
3 2 3
2 2 2
1 1 3 2 2

应该是 No，我这输出 Yes。

希望我上面写的对你还是有启发意义的。 ::::

非矩阵运算

至于非矩阵运算，我就简单提一句：

我在这方面的研究不深，~其实也是我懒了~，有时间再补充一下吧。 ## 后记 笔者能力有限，难免会有错误，欢迎大家指出。 另外欢迎大家探索新的、好用的、快的构造方式（例如非矩阵运算的位运算）。可以写在评论区里，也可以私信我。我有时间会加在 [这里](https://www.luogu.com.cn/article/hsnmub1p) 的。