CF580E - Kefa and Watch 线段树维护哈希

题目思路

区间修改+区间查询，考虑用线段树维护哈希实现。

那么首先，需要明确判断循环节的方式：如上图所示是一个重要的结论：当区间的哈希值与的哈希值相等时，那么该区间是以为循环节的。

有了以上的性质，直接线段树维护哈希，实现区间修改、区间查询即可。本题难点在于循环节判断的思路。

还有，卡自然溢出。。。

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define ull unsigned long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
const ull BASE = 17, MOD = 1e9 + 7;

ull hashp[N], hashm[N];
string s;

void hash_init(int n){
    hashp[0] = hashm[0] = 1;
    for(int i = 1; i <= n; i++) hashp[i] = (hashp[i - 1] * BASE + 1) % MOD, hashm[i] = (hashm[i - 1] * BASE) % MOD;
}

namespace SegTree{
    #define ls rt << 1
    #define rs rt << 1 | 1
    #define lson ls, l,
    #define rson rs, mid + 1,

    struct Info{
        ull val, len;
        friend Info operator+ (Info a, Info b){
            return Info {
                (a.val + b.val * hashm[a.len]) % MOD,
                a.len + b.len
            };
        }
    }tree[N << 2];

    ull lazy[N << 2];

    inline void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }

    inline void push(int rt, ull val){
        tree[rt].val = (val * hashp[tree[rt].len - 1]) % MOD;
        lazy[rt] = val;
    }

    inline void push_down(int rt){
        if(!(lazy[rt] + 1)) return;
        push(ls, lazy[rt]), push(rs, lazy[rt]);
        lazy[rt] = -1;
    }

    void build(int rt, int l, int r){
        lazy[rt] = -1;
        if(l == r) return (void)(tree[rt] = Info{(ull)(s[l] - '0' + 1), 1});
        int mid = l + r >> 1;
        build(lson), build(rson);
        push_up(rt);
    }

    void update(int rt, int l, int r, int L, int R, ull val){
        if(l >= L && r <= R) return push(rt, val);
        push_down(rt);
        int mid = l + r >> 1;
        if(mid >= L) update(lson, L, R, val);
        if(mid < R) update(rson, L, R, val);
        push_up(rt);
    }

    Info query(int rt, int l, int r, int L, int R){
        if(L > R) return Info{0, 0};
        if(l >= L && r <= R) return tree[rt];
        push_down(rt);
        int mid = l + r >> 1;
        if(mid >= L && mid < R) return query(lson, L, R) + query(rson, L, R);
        if(mid >= L) return query(lson, L, R);
        if(mid < R) return query(rson, L, R);
    }
}

#define SEGRG 1, 1,

inline void solve(){
    int n, m, k; cin >> n >> m >> k;
    hash_init(n + 10);
    cin >> s; s = '@' + s;
    SegTree::build(SEGRG);
    for(int i = 1; i <= m + k; i++){
        ull op, l, r, x; cin >> op >> l >> r >> x;
        if(op == 1) SegTree::update(SEGRG, l, r, x + 1);
        else cout << (SegTree::query(SEGRG, l + x, r).val == SegTree::query(SEGRG, l, r - x).val ? "YES" : "NO") << endl;

    }
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}