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

题目思路

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

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

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

还有，卡自然溢出。。。

Code

#include 
#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 >> m >> k;
    hash_init(n + 10);
    cin >> s; s = '@' + s;
    SegTree::build(SEGRG);
    for(int i = 1; i > op >> l >> r >> x;
        if(op == 1) SegTree::update(SEGRG, l, r, x + 1);
        else cout