【Henu ACM Round#14 E】Kefa and Watch

在这里输入题意

【题解】

在做之前需要了解一个知识点。就是如果一个字符串s是一个a循环串。 (字符串的长度设为n,下标从1开始那么s[1..n-a]和s[1+a..n]是相同的. 且这是充分必要条件。可以看这篇文章 [链接](http://blog.sina.com.cn/s/blog_7981299401012xl0.html) 显然1..n-a就对应了文章中的**黄色部分**,而1+a..n对应了**蓝色部分**。根据文章中的描述。显然如果这两部分相同。则它是长度为a的一个循环串。 (且**就算n不是a的倍数**,那种情况**也能用这种方法**判断

则我们的问题转化成快速判断某两段区间的字符串是否相同。

需要用到字符串hash的知识。
比如字符串
12343
它的hash值为(1*base^0 + 2*base^1+3*base^2+4*base^3+3*base^4)
显然如果太大了,这个值是会爆long long的。
但是没关系。
我们直接把它对一个数字MOD取模就好了。

这样我们就能用一个<MOD的数字唯一对应一段字符串了。

我们可以用线段树维护每一段字符串的hash值。

1操作就是线段树的成段更新。(预处理出(base^{l-1}+base^l+base^{l+1}...base^{r})(前缀和),然后到了那段
区间直接让hash值等于c*(sum[r]-sum[l])就可以了。

2操作就是取出两段的区间的hash值,然后因为第一段是1..n-a,第二段是1+a..n,所以第二段整体的幂会比第一段多a,所以第一段的hash要再乘上base^a;
比较一下就好。
(据说卡1e9+7的模数

【代码】

#include <bits/stdc++.h>
#define ll long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;

const int N = 1e5+10;
const ll MOD = 1998000219;
const ll BASE = 12;

ll _pow[N],_sum[N];
int n,m,k;
ll lazy_tag[N<<2],_hash[N<<2];
string s;

ll _Get(int l,int r){
    l--,r--;
    if (l==0) return _sum[r];
    else{
        return (_sum[r]-_sum[l-1]+MOD)%MOD;
    }
}

void _pushdown(int rt,int l,int r){
    if (lazy_tag[rt]==0) return;

    int mid = (l+r)>>1;
    if (l!=r){
        _hash[rt<<1] = 1LL*lazy_tag[rt]*_Get(l,mid)%MOD;
        _hash[rt<<1|1] = 1LL*lazy_tag[rt]*_Get(mid+1,r)%MOD;
        lazy_tag[rt<<1] = lazy_tag[rt<<1|1] = lazy_tag[rt];
    }
    lazy_tag[rt] = 0;
}

void _modify(int num,int L,int R,int l,int r,int rt){
    if (L<=l && r<=R){
        _hash[rt] = 1LL*num*_Get(l,r)%MOD;
        lazy_tag[rt] = num;
        return;
    }
    _pushdown(rt,l,r);
    int mid = (l+r)>>1;
    if (L<=mid) _modify(num,L,R,lson);
    if (mid<R) _modify(num,L,R,rson);
    _hash[rt] = (_hash[rt<<1]+_hash[rt<<1|1])%MOD;
}

ll _get(int L,int R,int l,int r,int rt){
    if(L<=l && r<=R) return _hash[rt];
    int mid = (l+r)>>1;
    ll temp = 0;
    _pushdown(rt,l,r);
    if (L<=mid) temp = _get(L,R,lson);
    if (mid<R) temp=(temp + _get(L,R,rson))%MOD;
    return temp;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    #ifdef LOCAL_DEFINE
        freopen("rush.txt","r",stdin);
    #endif

    cin >> n >> m >> k;
    m+=k;
    cin >> s;

    _pow[0] = 1;
    _sum[0] = 1;
    for (int j = 1;j <=n;j++){
        _pow[j] = _pow[j-1]*BASE%MOD;
        _sum[j] = (_sum[j-1]+_pow[j])%MOD;
    }


    for (int i = 0;i <n;i++){
        _modify(s[i]-'0'+1,i+1,i+1,1,n,1);
    }

    while (m--){
        int ope,l,r,num;
        cin >>ope>>l>>r>>num;
        if (ope==1){
            _modify(num+1,l,r,1,n,1);
        }else{
            if ((r-l+1)==num || _get(l,r-num,1,n,1)*_pow[num]%MOD==
                                _get(l+num,r,1,n,1))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
    }

    return 0;
}