AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

线段树维护哈希

作者: 作者的头像   不知名的fE ,  2025-05-10 16:45:38 · 河北 ,  所有人可见 ,  阅读 4


0


import java.util.Scanner;


public class Main {
    static final int N = 200010, p = 131, mod = (int) 1e9 + 7;
    static long[] exp = new long[N];
    static char[] str = new char[N];
    static Node[] tree = new Node[N << 2];
    static int n, q;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        String s = sc.next();
        exp[0] = 1;
        for (int i = 1; i <= n; i++) {
            exp[i] = exp[i - 1] * p % mod;
            str[i] = s.charAt(i - 1);
        }
        build(1, 1, n);
        q = sc.nextInt();
        for (int i = 1; i <= q; i++) {
            int op = sc.nextInt();
            if (op == 1) {
                int x = sc.nextInt();
                char c = sc.next().charAt(0);
                update(1, 1, n, x, c);
            } else {
                int l1 = sc.nextInt(), r1 = sc.nextInt();
                int l2 = sc.nextInt(), r2 = sc.nextInt();
                if (check(l1, r1, l2, r2)) System.out.println("YES");
                else System.out.println("NO");
            }
        }
    }

    static boolean check(int l1, int r1, int l2, int r2) {
        return query(1, 1, n, l1, r1).equals(query(1, 1, n, l2, r2));
    }

    static Node query(int u, int l, int r, int L, int R) {
        if (L <= l && r <= R) return tree[u];
        int mid = l + r >> 1;
        if (R <= mid) return query(u << 1, l, mid, L, R);
        if (L > mid) return query(u << 1 | 1, mid + 1, r, L, R);
        return query(u << 1, l, mid, L, R).add(query(u << 1 | 1, mid + 1, r, L, R));
    }

    static void update(int u, int l, int r, int x, char c) {
        if (l == r) {
            tree[u].h = c - 'a' + 1;
            return;
        }
        int mid = l + r >> 1;
        if (x <= mid) update(u << 1, l, mid, x, c);
        else update(u << 1 | 1, mid + 1, r, x, c);
        pushup(u);
    }

    static void build(int u, int l, int r) {
        tree[u] = new Node();
        if (l == r) {
            tree[u].h = str[l] - 'a' + 1;
            tree[u].len = 1;
            return;
        }

        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }

    static void pushup(int u) {
        tree[u] = tree[u << 1].add(tree[u << 1 | 1]);
    }

    static class Node {
        long h;
        int len;

        Node add(Node o) {
            Node res = new Node();
            res.h = (this.h * exp[o.len] % mod + o.h) % mod;
            res.len = this.len + o.len;
            return res;
        }

        public boolean equals(Node o) {
            return this.h == o.h && this.len == o.len;
        }
    }
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息