CodeForces - 580E Kefa and Watch（线段树哈希）

传送门：CodeForces - 580E

思路分析

这里的哈希多项式是递增的
如果一个区间的周期是$d$，那么$[l,r-d]$和$[l+d,r]$是一样的，用线段树维护hash值就行了

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const int N = 1e5+10;

char s[N];

struct TreeNode {
    struct node {
        int l,r,mid,len,lazy;
        ull sum;
    } tree[N<<2];


    ll mod;
    ull base,ba[N],sba[N];

#define ls x<<1
#define rs x<<1|1

    void init(){
        ba[0] = 1;
        sba[0] = 0;
        for(int i=1;i<N;i++){
            ba[i] = ba[i-1]*base;
            sba[i] = sba[i-1]+ba[i];
            ba[i]%=mod;
            sba[i]%=mod;
        }
    }
    
    void pp(int x) {
        tree[x].sum = tree[ls].sum+tree[rs].sum;
        tree[x].sum%=mod;
    }

    void build(int x,int l,int r) {
        tree[x] = {l,r,l+r>>1,r-l+1,-1,0};
        if(l==r) {
            tree[x].sum = (s[l]-'0'+1)*ba[l];
            tree[x].sum%=mod;
            return ;
        }
        int mid = tree[x].mid;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pp(x);
    }

    void pd(int x) {
        if(tree[x].lazy!=-1) {
            int now = tree[x].lazy;
            tree[ls].lazy = tree[rs].lazy = now;
            tree[ls].sum = (sba[tree[ls].r]-sba[tree[ls].l-1]+mod)*now;
            tree[rs].sum = (sba[tree[rs].r]-sba[tree[rs].l-1]+mod)*now;
            tree[ls].sum%=mod;
            tree[rs].sum%=mod;
            tree[x].lazy = -1;
        }
    }

    void modify(int x,int l,int r,int k) {
        if(l<=tree[x].l && tree[x].r<=r) {
            tree[x].lazy = k;
            tree[x].sum = (sba[tree[x].r]-sba[tree[x].l-1]+mod)*k;
            tree[x].sum%=mod;
            return ;
        }
        int mid = tree[x].mid;
        pd(x);
        if(l<=mid) modify(ls,l,r,k);
        if(r>mid) modify(rs,l,r,k);
        pp(x);
    }

    ull query(int x,int l,int r) {
        if(l<=tree[x].l && tree[x].r<=r) {
            return tree[x].sum%mod;
        }
        pd(x);
        ull ans = 0;
        int mid = tree[x].mid;
        if(l<=mid) ans+=query(ls,l,r),ans%=mod;
        if(r>mid) ans+=query(rs,l,r),ans%=mod;
        pp(x);
        return ans;
    }
}t[2];




int main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,m,k;
    cin>>n>>m>>k;
    cin>>s+1;
    t[0].mod = 10000103;
    t[1].mod = 99999787;
    for(int i=0;i<=1;i++) {
        t[i].base = 13331;
        t[i].init();
        t[i].build(1,1,n);
    }
    for(int i=1; i<=m+k; i++) {
        int op,l,r,d;
        cin>>op>>l>>r>>d;
        if(op==1) {
            for(int j = 0;j<=1;j++) t[j].modify(1,l,r,d+1);
        }
        else {
            if(r-l+1<=d) {
                cout<<"YES"<<endl;
                continue;
            }
            int ok = 1;
            for(int j = 0;j<=1;j++){
                ull s1,s2;
                s1 = t[j].query(1,l,r-d)*t[j].ba[n-l];
                s1%=t[j].mod;
                s2 = t[j].query(1,l+d,r)*t[j].ba[n-(l+d)];
                s2%=t[j].mod;
                if(s1 != s2) ok = 0;
            }
            if(ok) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }





    return 0;
}