cf580E. Kefa and Watch(线段树维护字符串hash)
2024-09-05 22:52:30
题意
$n$个数的序列,$m + k$种操作
1、$l , r, k$把$l - r$赋值为$k$
2、$l, r, d$询问$l - r$是否有长度为$d$的循环节
Sol
首先有个神仙结论:若询问区间为$(l, r, d)$,则只需判断$(l + d, r)$和$(l, r - d )$是否相同
证明可以用归纳法。
然后线段树维护一下字符串hash值,维护一个区间覆盖的标记就好了
注意赋值的时候有$0$的情况,因此开始的标记不能为$0$
#include<cstdio>
#include<algorithm>
#define int long long
#define LL long long
#define ull long long
using namespace std;
const int MAXN = 1e6 + ;
const double eps = 1e-;
inline int read() {
char c = getchar(); int x = , f = ;
while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
while(c >= '' && c <= '') x = x * + c - '', 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 - ] * T[son].f % mod;
}
void pushdown(int k) {
if(T[k].f == -) return ;
ps(k, ls); ps(k, rs);
T[k].f = -;
}
void Build(int k, int ll, int rr) {
T[k] = (Node) {ll, rr, rr - ll + , , -};
if(ll == rr) {
T[k].ha = s[ll] - '';
return ;
}
int mid = T[k].l + T[k].r >> ;
Build(ls, ll, mid); Build(rs, mid + , 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 - ] * val % mod;
return ;
}
pushdown(k);
int mid = T[k].l + T[k].r >> ;
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 ;
if(ll <= T[k].l && T[k].r <= rr) return T[k].ha % mod;
pushdown(k);
int mid = T[k].l + T[k].r >> ;
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) + ] * IntervalQuery(rs, ll, rr) % mod) % mod;
}
void work() {
po[] = ; sum[] = ;
for(int i = ; i <= N; i++) po[i] = po[i - ] * seed % mod, sum[i] = (sum[i - ] + po[i]) % mod;
Build(, , N);
}
int Query(int l, int r, int k) {
return IntervalQuery(, l, r - k) == IntervalQuery(, l + k, r);
}
}Se[]; main() {
Se[].seed = ; Se[].mod = 1e9 + ;
Se[].seed = ; Se[].mod = 1e9 + ;
N = read(); M = read(); K = read();
scanf("%s", s + );
Se[].work(); Se[].work();
for(int i = ; i <= M + K; i++) {
int opt = read(), l = read(), r = read(), k = read();
if(opt == ) Se[].IntervalChange(, l, r, k), Se[].IntervalChange(, l, r, k);
else {
if((r - l + ) == k) {
puts("YES");
continue;
}
puts((Se[].Query(l, r, k) && Se[].Query(l, r, k))? "YES" : "NO");
}
}
return ;
}
最新文章
- Hibernate-模板模式
- MVVM架构~knockoutjs系列之验证信息自定义输出~续
- 【BZOJ-3809】Gty的二逼妹子序列 分块 + 莫队算法
- serv-u启动管理控制台后提示脚本错误解决方案
- COM符合名字对象建议使用的分隔符
- 用doxygen+graphviz自动化生成代码文档(附详细教程)
- Java中的数学运算BigDecimal
- 使用SMSManager短信管理器实现短信群发
- PHP递归题目
- 【Linux/Ubuntu学习3】解决ubuntu解压windows生成的zip文件时乱码问题
- lnmp下配置虚拟主机
- PHPCMS(2)PHPCMS V9 环境搭建(转)
- Swift - 设置应用程序图标的提醒个数(右上角小红圈)
- Go 语言数据类型
- /dev/null 2>;&;1的意思(可以直接参考shell重定向那篇,/dev/null是空设备)
- [Swift]LeetCode654. 最大二叉树 | Maximum Binary Tree
- Python-cookie,session
- Java多线程:CAS与java.util.concurrent.atomic
- IIS8无法通过IP访问解决办法
- Dalvik指令备忘