题意

$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 ;
}

最新文章

  1. Hibernate-模板模式
  2. MVVM架构~knockoutjs系列之验证信息自定义输出~续
  3. 【BZOJ-3809】Gty的二逼妹子序列 分块 + 莫队算法
  4. serv-u启动管理控制台后提示脚本错误解决方案
  5. COM符合名字对象建议使用的分隔符
  6. 用doxygen+graphviz自动化生成代码文档(附详细教程)
  7. Java中的数学运算BigDecimal
  8. 使用SMSManager短信管理器实现短信群发
  9. PHP递归题目
  10. 【Linux/Ubuntu学习3】解决ubuntu解压windows生成的zip文件时乱码问题
  11. lnmp下配置虚拟主机
  12. PHPCMS(2)PHPCMS V9 环境搭建(转)
  13. Swift - 设置应用程序图标的提醒个数(右上角小红圈)
  14. Go 语言数据类型
  15. /dev/null 2&gt;&amp;1的意思(可以直接参考shell重定向那篇,/dev/null是空设备)
  16. [Swift]LeetCode654. 最大二叉树 | Maximum Binary Tree
  17. Python-cookie,session
  18. Java多线程:CAS与java.util.concurrent.atomic
  19. IIS8无法通过IP访问解决办法
  20. Dalvik指令备忘

热门文章

  1. liunx环境下安装tomcat
  2. 写出高效优美的单片机C语言代码
  3. monkey之monkeyServer
  4. css 属性相关
  5. SqlServer规则
  6. 豆瓣api获取图片403
  7. POJ3734【状压枚举】
  8. 在OpenCV for Android 2.4.5中使用SURF(nonfree module)
  9. 阿里巴巴开源性能监控神器Arthas初体验
  10. lombok常用注解