题解 CF580E 【Kefa and Watch】
顾z
2018-11-05 19:31:07
> ### Description
>
> $n$个数的字符串，$m + k$个操作
>
> `1 l r k`把$l - r$赋值为$k$
>
> `2 l r d`询问$l - r$是否有长度为$d$的循环节
>
> $n \leq 10^5, m + k \leq 10^5, d \leq 10$
>
> ### Input
>
> 第一行为三个整数$n,m,k$
>
> 第二行为一个$n$个数的字符串。
>
> 接下来$m+k$行每行对应一种操作。
>
> ### Output
>
> 对于每一个$2$操作,如果存在,输出一行$YES$，否则输出$NO$
**线段树维护哈希**
~~写起来爽,调起来更爽~~
我们首先**预处理出$po$数组记录$base^i$(这个要用来修改及查询的。)**
**还要预处理出来$val[i][j]$代表长度为$j$的全部为数字$i$的字符串的哈希值。**
然后每次区间合并的时候.
$$len=tr[rs].r-tr[rs].l+1$$
$$tr[o].va=(tr[ls].va\times po[len] \% mod +tr[rs].va) \% mod$$
这个应该不是很难理解吧。(就类似于你$hash$匹配的做法。)
修改时候,我们直接赋值$tr[o].va=val[k][len]$即可。
需要**注意**的有两点：
1. $lazy$标记初值要为$1$,因为会存在赋值为$0$的情况
2. 查询操作中,当前区间分别在左右两侧的时候$tr[ls].va \times po[r-mid]$！！
因此直接码代码就好了
还有一个**神仙结论**是做题的根据。
> **如果询问为$(l,r,d)$,则只需要判断$(l+d,r)$和$(l,r-d)$即可。**
证明的话,我不太会.但是这是正确的。
如果这题卡单$hash$的话可以写双$hash$。稍作修改即可。不多$BB$了.
``代码``
```c++
#include<cstdio>
#include<algorithm>
#include<iostream>
#define lo long long
#define base 31
#define mod 20020303
#define R register
using namespace std;
const int gz=1e5+8;
inline void in(R int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,m,K,po[gz]={1},val[10][gz];
char s[gz];
struct wc
{
int l,r,tg;
lo va;
}tr[gz<<2];
inline void pre()
{
for(R int i=1;i<gz;i++)
po[i]=po[i-1]*base%mod;
for(R int i=0;i<10;i++)
for(R int j=1;j<gz;j++)
val[i][j]=(val[i][j-1]*base%mod+i)%mod;
}
#define ls o<<1
#define rs o<<1|1
inline void up(R int o)
{
tr[o].va=(tr[ls].va*po[tr[rs].r-tr[rs].l+1]%mod+tr[rs].va%mod)%mod;
}
void build(R int o,R int l,R int r)
{
tr[o].l=l,tr[o].r=r;tr[o].tg=-1;
if(l==r)
{
tr[o].va=s[l]-'0';
return;
}
R int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
up(o);
}
inline void down(R int o)
{
if(tr[o].tg==-1)return;
R int k=tr[o].tg;
tr[ls].va=val[k][tr[ls].r-tr[ls].l+1];
tr[rs].va=val[k][tr[rs].r-tr[rs].l+1];
tr[ls].tg=tr[rs].tg=k;
tr[o].tg=-1;
}
void change(R int o,R int l,R int r,R int k)
{
if(tr[o].l==l and tr[o].r==r)
{
tr[o].tg=k;
tr[o].va=val[k][tr[o].r-tr[o].l+1];
return ;
}
down(o);
R int mid=(tr[o].l+tr[o].r)>>1;
if(r<=mid)change(ls,l,r,k);
else if(l>mid)change(rs,l,r,k);
else change(ls,l,mid,k),change(rs,mid+1,r,k);
up(o);
}
lo query(R int o,R int l,R int r)
{
if(tr[o].l==l and tr[o].r==r)return tr[o].va;
down(o);
R int mid=(tr[o].l+tr[o].r)>>1;
if(r<=mid)return query(ls,l,r);
else if(l>mid) return query(rs,l,r);
else
return ((query(ls,l,mid)%mod)*po[r-mid]%mod+query(rs,mid+1,r)%mod)%mod;//注意这里！！
}
int main()
{
pre();
in(n),in(m),in(K);
R int tt=m+K;
scanf("%s",s+1);
build(1,1,n);
for(R int opt,l,r,k;tt;tt--)
{
in(opt),in(l),in(r),in(k);
switch(opt)
{
case 1:change(1,l,r,k);break;
case 2:
{
if(r-l+1==k)
{
puts("YES");
continue;
}
puts(query(1,l,r-k)==query(1,l+k,r) ? "YES":"NO");
break;
}
}
}
}
```