链接:

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 r,int p,int c)
{
    if (l == r)
    {
        tree[root] = 1<<c;
        return;
    }
    int mid = (l+r)/2;
    if (p <= mid)
        Update(root<<1,mid,p,c);
    else
        Update(root<<1|1,r,c);
    PushUp(root);
}

int Query(int root,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,ql,qr);
    res |= Query(root<<1|1,qr);
    return res;
}

int main()
{
    scanf("%s",s+1);
    n = strlen(s+1);
    Build(1,1,n);
    scanf("%d",&q);
    int op,r;
    char val;
    while (q--)
    {
        scanf("%d",&op);
        if (op == 1)
        {
            scanf("%d %c",&l,&val);
            Update(1,n,val-'a');
        }
        else
        {
            scanf("%d %d",&r);
            int res = Query(1,r);
            int cnt = 0;
            while (res)
            {
                if (res&1)
                    cnt++;
                res >>= 1;
            }
            printf("%d\n",cnt);
        }
    }

    return 0;
}