传送门
题意: 给定一个字符串
修改某个位置的字符查询区间不同的字符种类数思路： 对每一种字符建一棵线段树，维护区间该种字符的个数。 然后就是裸的单点更新区间查询。
#include<iostream> #include<algorithm> #include<cstdio> #include<stdio.h> #include<string.h> #include<queue> #include<cmath> #include<map> #include<set> #include<vector> using namespace std; #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define mem(a,b) memset(a,b,sizeof(a)); #define lowbit(x) x&-x; #define debugint(name,x) printf("%s: %d\n",name,x); #define debugstring(name,x) printf("%s: %s\n",name,x); typedef long long ll; typedef unsigned long long ull; const double eps = 1e-6; const int maxn = 1e5+5; const int mod = 1e9+7; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int sum[maxn<<2][27]; char s[maxn]; void build(int l,int r,int rt){ if(l == r){ for(int i = 0; i < 26; i++) sum[rt][i] = 0; sum[rt][s[l]-'a'] = 1; return; } int mid = (l+r)>>1; build(lson); build(rson); for(int i = 0; i < 26; i++) sum[rt][i] = sum[rt<<1][i] + sum[rt<<1|1][i]; } void update(int l,int r,int rt,int pos,int k,int val){ if(l == r){ // for(int i = 0; i < 26; i++){ // if(i == v) sum[rt][i]--; // } sum[rt][k]+=val; return; } int mid = (l+r)>>1; if(pos <= mid) update(lson,pos,k,val); else update(rson,pos,k,val); for(int i = 0; i < 26; i++) sum[rt][i] = sum[rt<<1][i] + sum[rt<<1|1][i]; } int query(int l,int r,int rt,int L,int R,int k){ if(L <= l && R >= r){ return sum[rt][k]; } int mid = (l+r)>>1; int res = 0; if(L <= mid) res += query(lson,L,R,k); if(R > mid) res += query(rson,L,R,k); return res; } int main() { scanf("%s",s+1); int n = strlen(s+1); build(1,n,1); int q; scanf("%d",&q); int l,r,op; char ss[2]; while(q--){ scanf("%d",&op); if(op == 1){ scanf("%d%s",&l,ss); int id; for(int i = 0; i < 26; i++){ int cnt = query(1,n,1,l,l,i); if(cnt > 0){ id = i; break; } } update(1,n,1,l,ss[0]-'a',1); update(1,n,1,l,id,-1); //printf("up: %d\n",query(1,n,1,1,n,0)); }else{ scanf("%d%d",&l,&r); int ans = 0; for(int i = 0; i < 26; i++){ int cnt = query(1,n,1,l,r,i); if(cnt > 0) ans++; } printf("%d\n",ans); } } }