ABC415F题解

题目要求区间查询最大连续相同字母串的长度，单点修改。

可以用线段树维护。维护一个区间对于每个字母靠左端点、靠右端点、中间的最大连续相同字母串，和字母总数以及区间长度。则我们可以像维护区间最大子段和一样维护这些东西。

注意当某个字母总数等于区间长度时，表示区间全为这种字母，此时合并时的算法就和区间最大子段和不同了。对于靠左或靠右的最大值，要加上那个全为这种字母的区间的长度。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5+5;

struct Node
{
    int lm[35], mm[35], rm[35];
    int sum[35];
    int len;
    Node operator+(const Node &_) const
    {
        Node res;
        for(int i = 1;i <= 26;i++)
        {
            if(sum[i] == len) res.lm[i] = sum[i] + _.lm[i];
            else res.lm[i] = lm[i];

            if(_.sum[i] == _.len) res.rm[i] = _.sum[i] + rm[i];
            else res.rm[i] = _.rm[i];

            res.mm[i] = max({mm[i], _.mm[i], rm[i] + _.lm[i]});

            res.sum[i] = _.sum[i] + sum[i];
        }
        res.len = len + _.len;
        return res;
    }
    void init(char c)
    {
        len = 1;
        for(int i = 1;i <= 26;i++)
        {
            lm[i] = mm[i] = rm[i] = sum[i] = 0;
        }
        lm[c-'a'+1] = mm[c-'a'+1] = rm[c-'a'+1] = sum[c-'a'+1] = 1;
    }
};

int n, m;
char ss[MAXN];

struct SegmentTree
{
    #define lp (p<<1)
    #define rp (p<<1|1)
    Node tree[MAXN<<2];
    void push_up(int p)
    {
        tree[p] = tree[lp] + tree[rp];
    }
    void build(int s, int t, int p)
    {
        if(s == t)
        {
            tree[p].init(ss[s]);
            return;
        }
        int mid = (s + t) >> 1;
        build(s, mid,  lp);
        build(mid+1, t, rp);
        push_up(p);
    }
    void set(int x, int s, int t, int p, char k)
    {
        if(x == s && t == s)
        {
            tree[p].init(k);
            return;
        }
        int mid = (s + t) >> 1;
        if(x <= mid) set(x, s, mid, lp, k);
        if(x > mid) set(x, mid+1, t, rp, k);
        push_up(p);
    }
    Node query(int l, int r, int s, int t, int p)
    {
        if(l <= s && t <= r)
        {
            return tree[p];
        }
        int mid = (s + t) >> 1;
        if(l > mid) return query(l, r, mid+1, t, rp);
        if(r <= mid) return query(l, r, s, mid, lp);
        return query(l, r, s, mid, lp) + query(l, r, mid+1, t, rp);
    }
    int query(int l, int r)
    {
        Node re = query(l, r, 1, n, 1);
        int res = 0;
        for(int i = 1;i <= 26;i++) res = max(res, re.mm[i]);
        return res;
    }
}tree;

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", ss+1);
    tree.build(1, n, 1);
    for(int i = 1;i <= m;i++)
    {
        int op;
        scanf("%d", &op);
        if(op == 1)
        {
            int x; char c[5];
            scanf("%d%s", &x, c+1);
            tree.set(x, 1, n, 1, c[1]);
        }
        if(op == 2)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", tree.query(l, r));
        }
    }
    return 0;
}

文章操作

代码

相关推荐

评论

ABC415F题解