P14963 [LBA-OI R2 B] 何意味 题解
KobeBeanBryantCox · · 题解
P14963 [LBA-OI R2 B] 何意味 题解
题目传送门。
出题人题解。
题意
略。
思路
题目是要求对
改完题目后就可以注意到，第二个操作没有用，第一个操作就是消消乐。
首先需要注意 1 2 2 1 是可以消消乐消成空的（有验题人以为不能）。
考虑怎么刻画，注意到两个相同字符可以消去，这启示我们使用随机值异或哈希。
注意到一个问题：这样会被 1 2 1 2 这种卡爆，这种是不能消消乐的，但是会被判断成可以消消乐。
出现这种情况原因是，异或具有交换律。考虑搞一个没有交换律的运算。
启示我们使用某种奇怪的运算，又由于能够消消乐的必须被弄成单位元，所以这种运算要满足：
- 有结合律；
- 没有交换律；
- 存在
>5\times 10^5 个元素a ，使得a 运算上自身等于该运算的单位元。
判断是否同构只需要判断区间运算结果是否相同。
不难发现这种运算是好构造的，一种可行的方案是使用
另一种可行的方案是定义运算
::::warning[hack]
upd：二元组的方法是错的，感谢工单的 hack。原因是，注意到，奇数个元素运算在一起变成
因此，理论上两个长为奇数的等串拼在一起，这种方法都会错。比如下面一个就会错：
6 1
1 2 3 1 2 3
1 1 1 1 1 1
1 1 6 1 6::::
还有很多可能的运算都满足这个条件。
然后用线段树维护就做完了，复杂度
STD
#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
int k=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
return k*f;
}
void out(int x)
{
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else out(x/10),putchar(x%10+'0');
}
const int N=5e5+10,mod=789169133;
struct Matrix
{
int a[2][2];
Matrix(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;}
int *operator[](int i){return a[i];}
friend Matrix operator*(Matrix a,Matrix b)
{
Matrix c;
c[0][0]=(1ll*a[0][0]*b[0][0]%mod+1ll*a[0][1]*b[1][0]%mod)%mod;
c[0][1]=(1ll*a[0][0]*b[0][1]%mod+1ll*a[0][1]*b[1][1]%mod)%mod;
c[1][0]=(1ll*a[1][0]*b[0][0]%mod+1ll*a[1][1]*b[1][0]%mod)%mod;
c[1][1]=(1ll*a[1][0]*b[0][1]%mod+1ll*a[1][1]*b[1][1]%mod)%mod;
return c;
}
friend bool operator==(Matrix a,Matrix b)
{
if(a[0][0]!=b[0][0])return 0;
if(a[0][1]!=b[0][1])return 0;
if(a[1][0]!=b[1][0])return 0;
if(a[1][1]!=b[1][1])return 0;
return 1;
}
}t[N];
Matrix I(){Matrix c;c[0][0]=c[1][1]=1;return c;}
int ksm(int a,int b)
{
int res=1;
for(;b;a=1ll*a*a%mod,b>>=1)if(b&1)res=1ll*res*a%mod;
return res;
}
mt19937 rnd(time(0));
void init()
{
for(int i=0;i<N;i++)
{
int a=rnd()%mod,b=rnd()%mod;
while(b==0)b=rnd()%mod;
t[i][0][0]=a,t[i][1][1]=mod-a,t[i][1][0]=b;
t[i][0][1]=1ll*(mod+1-1ll*a*a%mod)*ksm(b,mod-2)%mod;
}
}
int a[N][2];
struct Seg
{
struct node{int l,r;Matrix res;}tr[N<<2];
#define lc (x<<1)
#define rc (x<<1|1)
void pushup(int x){tr[x].res=tr[lc].res*tr[rc].res;}
void build(int x,int l,int r,int tp)
{
tr[x].l=l,tr[x].r=r;
if(l==r)return tr[x].res=t[a[l][tp]],void();
int mid=(l+r)>>1;
build(lc,l,mid,tp),build(rc,mid+1,r,tp),pushup(x);
}
void modify(int x,int p,int tp)
{
if(tr[x].l>p||tr[x].r<p)return;
if(tr[x].l==tr[x].r)return tr[x].res=t[a[tr[x].l][tp]],void();
modify(lc,p,tp),modify(rc,p,tp),pushup(x);
}
Matrix query(int x,int l,int r)
{
if(tr[x].l>r||tr[x].r<l)return I();
if(l<=tr[x].l&&tr[x].r<=r)return tr[x].res;
return query(lc,l,r)*query(rc,l,r);
}
}S,T;
int main()
{
int n=in(),q=in();init();
for(int i=1;i<=n;i++)a[i][0]=in();
for(int i=1;i<=n;i++)a[i][1]=in();
S.build(1,1,n,0),T.build(1,1,n,1);
while(q--)
{
int op=in();
if(op==1)
{
int l1=in(),r1=in(),l2=in(),r2=in();
if(S.query(1,l1,r1)==T.query(1,l2,r2))puts("Yes");
else puts("No");
continue;
}
op-=2;int p=in(),x=in();
a[p][op]=x;
if(op==0)S.modify(1,p,op);
else T.modify(1,p,op);
}
return 0;
}后记
本题在比赛中的数据过水，放过了 xor-hash 以及少数
upd：新的 hack 已经在工单了。此外，此题的错解过多且数据并不好造，所以很多错解都能过，我们欢迎大家提供 hack。