Codeforces Round #590 (Div. 3) D. Distinct Characters Queries
题意：
有一个字符串，对这个字符串有两种操作1：修改某个位置的字符为其他字符2：查询 [ l, r ] 的不同字符的数目
思路：
一共有26个字符，所以我们用26位的二进制来表示字符的存在情况：a ((1 >> 0) & 1), b(1 >> 1 & 1)…… = 1即存在，= 0即不存在依此来建线段树，父亲结点的值是左右儿子的值的按位或
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define MID (l + r) >> 1
#define lsn rt << 1
#define rsn rt << 1 | 1
#define Lson lsn, l, mid
#define Rson rsn, mid + 1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
using namespace std
;
typedef long long ll
;
const int maxN
= 1e5 + 7;
const int maxM
= 2e6;
int q
;
char s
[maxN
];
int tree
[maxN
<< 2];
void pushup(int rt
)
{
tree
[rt
] = tree
[lsn
] | tree
[rsn
];
return;
}
void build_tree(int rt
, int l
, int r
)
{
if(l
== r
) { tree
[rt
] = 1 << s
[l
- 1] - 'a'; return; }
int mid
= MID
;
build_tree(Lson
);
build_tree(Rson
);
pushup(rt
);
}
void update_point(int rt
, int l
, int r
, int pos
, int val
)
{
if(l
== r
) { tree
[rt
] = val
; return ;}
int mid
= MID
;
if(pos
<= mid
) update_point(Lson
, pos
, val
);
else update_point(Rson
, pos
, val
);
pushup(rt
);
}
int query(int rt
, int l
, int r
, int ql
, int qr
)
{
if(l
>= ql
&& r
<= qr
) return tree
[rt
];
int mid
= MID
;
if(qr
<= mid
) return query(QL
);
else if(ql
> mid
) return query(QR
);
else return query(QL
) | query(QR
);
}
int main()
{
scanf("%s", s
);
int n
= strlen(s
);
scanf("%d", &q
);
build_tree(1, 1, n
);
while(q
-- )
{
int a
; scanf("%d", &a
);
if(a
== 1)
{
int b
; char c
;
scanf("%d", &b
);
getchar();
scanf("%c", &c
);
update_point(1, 1, n
, b
, 1 << c
- 'a');
}
else
{
int b
, c
; scanf("%d%d",&b
, &c
);
int ans
= query(1, 1, n
, b
, c
);
int res
= 0;
for(int i
= 0; i
< 26; i
++ )
{
if((ans
>> i
) & 1)
res
++;
}
printf("%d\n", res
);
}
}
return 0;
}
