题目思路
区间修改+区间查询,考虑用线段树维护哈希实现。
那么首先,需要明确判断循环节的方式:如上图所示是一个重要的结论:当区间的哈希值与
的哈希值相等时,那么该
区间是以
为循环节的。
有了以上的性质,直接线段树维护哈希,实现区间修改、区间查询即可。本题难点在于循环节判断的思路。
还有,卡自然溢出。。。
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;
}