cf1234 Round #590 Div3-D【二维树状数组】

Date：2021.01.06

题意：
*** 作1：将第pos个位置改为字母c
*** 作2：计算[l,r]中字母种类数

思路：建26个BIT，编号0-25。设原序列为s， *** 作1即为在第s[pos]-‘a’个BIT中将第pos个位置-1；再在第c-'a’个BIT中将第pos个位置+1。 *** 作2即为统计26棵BIT上有几个在[l,r]上的和>0。【注意BIT下标从1开始，别忘了初始化。】
代码如下：

#include 
#include 
#include 
using namespace std;
const int N = 1e5+10;
typedef long long LL;
LL n,t,tr[26][N];
char c[N];
LL lowbit(LL x)
{
    return x&-x;
}
void add(LL x,LL c,LL *tr)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c; 
}
LL sum(LL x,LL *tr)
{
    LL res=1;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>c+1;n=strlen(c+1);
    for(int i=1;i<=n;i++) add(i,1,tr[c[i]-'a']);
    cin>>t;
    while(t--)
    {
        int op,l,r;char q;cin>>op;
        if(op==1)
        {
            cin>>l>>q;
            add(l,-1,tr[c[l]-'a']);
            add(l,1,tr[q-'a']);
            c[l]=q;
        }
        else
        {
            LL ans=0;
            cin>>l>>r;
            for(int i=0;i<26;i++)
            {
                LL ss=sum(r,tr[i])-sum(l-1,tr[i]);
                if(ss>0) ans++;
            }
            cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5698715.html