題目連結:http://fastvj.rainng.com/problem/246827/origin
題目大意:
給你一個長度為n的字元串,m次修改,q次詢問;
2 L R 1:
詢問[L, R]是否為周期為1的字元串
1 L R x:
把[L, R]的字元修改為x
周期:一個串s以d為周期長度指的是d<=|s|且對任意1<=i<=|s|-d有s[i]=s[i+d]
是以:(n%d)可以不等于0
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38FdsYkRGZkRG9lcvx2bjxiNx8VZ6l2csgXRE5keNRkT4lkeYhnRzwEMW1mY1RzRapnTtxkb5ckYplTeMZTTINGMShUYfRHelRHLwEzX39GZhh2css2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xyayFWbyVGdhd3LcV2Zh1Wa9M3clN2byBXLzN3btg3Pn5GcuczN2UTM1cTMxMTNwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
思路:根據上一篇部落格的知識:https://blog.csdn.net/qq_21433411/article/details/90719116 我們已經可以維護這個字元串了。
就是如何判斷周期:
我們把區間[L, R]錯一下位:就會發現[L+d, R]和[L, R-d]是否相等?就能判斷[L, R]為周期。
坑點:ull自然溢出會WA75.卡了我一整天。
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn=100005;
ull base1 =233;
ull base2 =123;
const int mod=998244353;
ull p[2][maxn];
ull sum[2][maxn*4];
ull sf[2][maxn];
void getp()
{
p[0][0]=1;
p[1][0]=1;
for(int i=1;i<maxn;i++)
{
p[0][i]=p[0][i-1]*base1;
p[1][i]=p[1][i-1]*base2%mod;
}
sf[0][0]=sf[1][0]=1;
for(int i=1;i<maxn;i++)
{
sf[0][i]=sf[0][i-1]+p[0][i];
sf[1][i]=(sf[1][i-1]+p[1][i])%mod;
}
}
struct Node
{
int l ,r;
}node[maxn*4];
int add[maxn*4];
void updata(int i)
{
sum[0][i]=sum[0][i<<1]+sum[0][(i<<1)+1]*p[0][(node[i<<1].r-node[i<<1].l+1)];
sum[1][i]=(sum[1][i<<1]+sum[1][(i<<1)+1]*p[1][(node[i<<1].r-node[i<<1].l+1)]%mod)%mod;
return;
}
void BT(int i, int l, int r)
{
node[i].l=l, node[i].r=r;
add[i]=-1;
sum[0][i]=0;
sum[1][i]=0;
if(l==r)
{
scanf("%1d",&sum[0][i]);
sum[1][i]=sum[0][i];
return;
}
BT((i<<1), l, (l+r)/2);
BT((i<<1)+1, (l+r)/2+1, r);
updata(i);
return;
}
void updown(int i)
{
if(add[i]!=-1)
{
add[i<<1]=add[i];
add[(i<<1)+1]=add[i];
sum[0][i<<1]=add[i]*sf[0][node[i<<1].r-node[i<<1].l];
sum[1][i<<1]=add[i]*sf[1][node[i<<1].r-node[i<<1].l]%mod;
sum[0][(i<<1)+1]=add[i]*sf[0][node[(i<<1)+1].r-node[(i<<1)+1].l];
sum[1][(i<<1)+1]=add[i]*sf[1][node[(i<<1)+1].r-node[(i<<1)+1].l]%mod;
add[i]=-1;
}
}
void up(int i, int l, int r, int c)
{
if(node[i].l==l&&node[i].r==r)
{
add[i]=c;
sum[0][i]=add[i]*sf[0][r-l];
sum[1][i]=add[i]*sf[1][r-l]%mod;
return;
}
updown(i);
int mid=(node[i].l+node[i].r)/2;
if(r<=mid)
{
up(i<<1, l, r, c);
}
else if(l>mid)
{
up((i<<1)+1, l, r, c);
}
else
{
up(i<<1, l, mid, c);
up((i<<1)+1, mid+1, r, c);
}
updata(i);
return;
}
ull ans1=0;
ull ans2=0;
void fd(int i, int l, int r, int k)
{
if(node[i].l==l&&node[i].r==r)
{
ans1+=sum[0][i]*(p[0][l-k]);
ans2=(ans2+sum[1][i]*(p[1][l-k]))%mod;
return;
}
updown(i);
int mid=(node[i].l+node[i].r)/2;
if(r<=mid)
{
fd(i<<1, l, r, k);
}
else if(l>mid)
{
fd((i<<1)+1, l, r, k);
}
else
{
fd(i<<1, l, mid, k);
fd((i<<1)+1, mid+1, r, k);
}
updata(i);
return;
}
int main()
{
getp();
int n, q, m;
scanf("%d%d%d",&n,&q,&m);
q+=m;
BT(1, 1, n);
while(q--)
{
int op, L, R, d;
scanf("%d%d%d%d",&op,&L,&R,&d);
if(op==1)
{
up(1, L, R, d);
}
else
{
if(R-L+1<=d)
{
printf("YES\n");
continue;
}
ull k1, k2, k3, k4;
ans1=ans2=0;
fd(1, L, R-d, L);
k1=ans1, k2=ans2;
ans1=ans2=0;
fd(1, L+d, R, L+d);
k3=ans1, k4=ans2;
if(k1==k3&&k2==k4)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
}
return 0;
}