# cf580E. Kefa and Watch(线段树维护字符串hash)

## 题意

$n$个数的序列，$m + k$种操作

1、$l , r, k$把$l - r$赋值为$k$

2、$l, r, d$询问$l - r$是否有长度为$d$的循环节

## Sol

#include<cstdio>
#include<algorithm>
#define int long long
#define LL long long
#define ull long long
using namespace std;
const int MAXN = 1e6 + 10;
const double eps = 1e-9;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, K;
char s[MAXN];
struct Segment {
ull sum[MAXN], po[MAXN], seed, mod;
#define ls k << 1
#define rs k << 1 | 1
struct Node {
int l, r, siz;
ull ha, f;
}T[MAXN];
void update(int k) {
T[k].ha = (T[ls].ha % mod + po[T[ls].siz] * T[rs].ha % mod) % mod;
}
void ps(int k, int son) {
T[son].f = T[k].f;
T[son].ha = sum[T[son].siz - 1] * T[son].f % mod;
}
void pushdown(int k) {
if(T[k].f == -1) return ;
ps(k, ls); ps(k, rs);
T[k].f = -1;
}
void Build(int k, int ll, int rr) {
T[k] = (Node) {ll, rr, rr - ll + 1, 0, -1};
if(ll == rr) {
T[k].ha = s[ll] - '0';
return ;
}
int mid = T[k].l + T[k].r >> 1;
Build(ls, ll, mid); Build(rs, mid + 1, rr);
update(k);
}
void IntervalChange(int k, int ll, int rr, ull val) {
if(ll <= T[k].l && T[k].r <= rr) {
T[k].f = val % mod;
T[k].ha = sum[T[k].siz - 1] * val % mod;
return ;
}
pushdown(k);
int mid = T[k].l + T[k].r >> 1;
if(ll <= mid) IntervalChange(ls, ll, rr, val);
if(rr >  mid) IntervalChange(rs, ll, rr, val);
update(k);
}
ull IntervalQuery(int k, int ll, int rr) {
if(ll > rr) return 0;
if(ll <= T[k].l && T[k].r <= rr) return T[k].ha % mod;
pushdown(k);
int mid = T[k].l + T[k].r >> 1;
if(ll > mid) return IntervalQuery(rs, ll, rr) % mod;
else if(rr <= mid) return IntervalQuery(ls, ll, rr) % mod;
else return (IntervalQuery(ls, ll, rr) % mod + po[mid - max(T[k].l, ll) + 1] * IntervalQuery(rs, ll, rr) % mod) % mod;
}
void work() {
po[0] = 1; sum[0] = 1;
for(int i = 1; i <= N; i++) po[i] = po[i - 1] * seed % mod, sum[i] = (sum[i - 1] + po[i]) % mod;
Build(1, 1, N);
}
int Query(int l, int r, int k) {
return IntervalQuery(1, l, r - k) == IntervalQuery(1, l + k, r);
}
}Se[2];

main() {
Se[0].seed = 27; Se[0].mod = 1e9 + 7;
Se[1].seed = 233; Se[1].mod = 1e9 + 9;
scanf("%s", s + 1);
Se[0].work(); Se[1].work();
for(int i = 1; i <= M + K; i++) {
if(opt == 1) Se[0].IntervalChange(1, l, r, k), Se[1].IntervalChange(1, l, r, k);
else {
if((r - l + 1) == k) {
puts("YES");
continue;
}
puts((Se[0].Query(l, r, k) && Se[1].Query(l, r, k))? "YES" : "NO");
}
}
return 0;
}

1811 篇文章120 人订阅

0 条评论

## 相关文章

1132

### Core官方DI解析(4)--CallSiteRuntimeResolver

​ CallSiteRuntimeResolver类型是一个创建或获取服务实例的类型,这个类型继承了CallSiteVisitor<TArgument, TRe...

991

3046

2966

843

913

### 数据结构和算法——旋转打印链表

1、问题描述 输入参数nnn为正整数，如输入n=5n=5n=5，则按行打印如下的数字： ? 2、问题的理解 这个问题是将数字1…n21…n21\dots n^2...

3043

691

1504

1473