链接:

https://codeforces.com/contest/1234/problem/D

题意:

You are given a string s consisting of lowercase Latin letters and q queries for this string.

Recall that the substring s[l;r] of the string s is the string slsl+1…sr. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

There are two types of queries:

1 pos c (1≤pos≤|s|, c is lowercase Latin letter): replace spos with c (set spos:=c);

2 l r (1≤l≤r≤|s|): calculate the number of distinct characters in the substring s[l;r].

思路:

线段树维护二进制,二进制的每一位维护对应的字母在区间是否使用过, 合并区间就是与一下.

代码:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+10;

char s[MAXN];

int tree[MAXN*4];

int n, q;

void PushUp(int root)

{

    tree[root] = tree[root<<1] | tree[root<<1|1];

}

void Build(int root, int l, int r)

{

    if (l == r)

    {

        tree[root] = 1<<(s[l]-'a');

        return;

    }

    int mid = (l+r)/2;

    Build(root<<1, l, mid);

    Build(root<<1|1, mid+1, r);

    PushUp(root);

}

void Update(int root, int l, int r, int p, int c)

{

    if (l == r)

    {

        tree[root] = 1<<c;

        return;

    }

    int mid = (l+r)/2;

    if (p <= mid)

        Update(root<<1, l, mid, p, c);

    else

        Update(root<<1|1, mid+1, r, p, c);

    PushUp(root);

}

int Query(int root, int l, int r, int ql, int qr)

{

    if (qr < l || ql > r)

        return 0;

    if (ql <= l && r <= qr)

        return tree[root];

    int mid = (l+r)/2;

    int res = 0;

    res |= Query(root<<1, l, mid, ql, qr);

    res |= Query(root<<1|1, mid+1, r, ql, qr);

    return res;

}

int main()

{

    scanf("%s", s+1);

    n = strlen(s+1);

    Build(1, 1, n);

    scanf("%d", &q);

    int op, l, r;

    char val;

    while (q--)

    {

        scanf("%d", &op);

        if (op == 1)

        {

            scanf("%d %c", &l, &val);

            Update(1, 1, n, l, val-'a');

        }

        else

        {

            scanf("%d %d", &l, &r);

            int res = Query(1, 1, n, l, r);

            int cnt = 0;

            while (res)

            {

                if (res&1)

                    cnt++;

                res >>= 1;

            }

            printf("%d\n", cnt);

        }

    }

    return 0;

}

巴特西

Codeforces Round #590 (Div. 3) D. Distinct Characters Queries(线段树, 位运算)

链接:

题意:

思路:

代码:

最新文章

热门文章