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

题意

$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 + 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;
    N = read(); M = read(); K = read();
    scanf("%s", s + 1);
    Se[0].work(); Se[1].work();
    for(int i = 1; i <= M + K; i++) {
        int opt = read(), l = read(), r  = read(), k = read();
        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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java与Android技术栈

Scala学习笔记(四) 类的初步Scala 类相关总结

终于来到面向对象的地方了,虽说函数式编程是 Scala 的特性,让人们觉得 Scala 是更好的 Java。但是在架构层面上一直提倡着:小处用函数式编程,大处用...

1132
来自专栏博客园

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

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

991
来自专栏Jackson0714

PHP内核之旅-3.变量

3046
来自专栏TungHsu

这或许是对小白最友好的python入门了吧——8,初识for语句

有时候我们想要使用列表中所有元素,但是如果手打又不现实,这时候我们可以用for语句来遍历整个列表,我们先举个例子,还是昨天的列表 ? 现在我们用for语句来遍历...

2966
来自专栏Android开发实战

设计模式-单例模式

单例模式(Singleton Pattern)是 Java 中最简单的设计模式之一。

843
来自专栏博客园

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

这两个类都在其CallSiteVisitor<TArgument, TResult>基类中

913
来自专栏null的专栏

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

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

3043
来自专栏阿杜的世界

Java Web技术经验总结(五)

按照注释中的说法,字符编码取决于JVM启动参数、Locale和底层的系统编码,因此我再回去看我的JVM的启动参数(命令:ps -ef | grep java):

691
来自专栏Jackson0714

PHP内核之旅-3.变量

1504
来自专栏王硕

原 PostgreSQL的系统函数分析记录

1473

扫码关注云+社区

领取腾讯云代金券