D. Distinct Characters Queries
Description
You are given a string ss consisting of lowercase Latin letters and qq queries for this string.
Recall that the substring s[l;r]s[l;r] of the string ss is the string slsl+1…srslsl+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 c1 pos c (1≤pos≤|s|1≤pos≤|s|, cc is lowercase Latin letter): replace sposspos with cc (set spos:=cspos:=c);
- 2 l r2 l r (1≤l≤r≤|s|1≤l≤r≤|s|): calculate the number of distinct characters in the substring s[l;r]s[l;r].
Input
The first line of the input contains one string ss consisting of no more than 105105 lowercase Latin letters.
The second line of the input contains one integer qq (1≤q≤1051≤q≤105) — the number of queries.
The next qq lines contain queries, one per line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.
output
For each query of the second type print the answer for it — the number of distinct characters in the required substring in this query.
Examples
Input
abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7
Output
3
1
2
正确解法：
原本想着可修改的主席树来着，树状数组加上主席树。
改模板改了好久没过。
操作一：改变某个字符
操作二：统计区间【l，r】不同字符的个数。
26个字母的树状数组：
每次需要for26次，统计这个字母是否在区间内。
1 1 #include <iostream> 2 2 #include <cstdio> 3 3 #include <cmath> 4 4 #include <algorithm> 5 5 #include <set> 6 6 #include <queue> 7 7 #include <stack> 8 8 #include <string> 9 9 #include <cstring> 1010 #include <vector> 1111 #include <map> 1212 //#include <unordered_map> 1313 #define mem( a ,x ) memset( a , x ,sizeof(a) ) 1414 #define rep( i ,x ,y ) for( int i = x ; i<=y ;i++ ) 1515 #define lson l ,mid ,pos<<1 1616 #define rson mid+1 ,r ,pos<<1|1 1717 using namespace std; 1818 typedef long long ll ; 1919 typedef pair<int ,int> pii; 2020 typedef pair<ll ,int> pli; 2121 const int inf = 0x3f3f3f3f; 2222 const int N = 1e5+100; 2323 const ll mod =1e9+7 ; 2424 char s[N],kkk; 2525 int n,m; 2626 int aa,bb,cc; 2727 int bit[30][N]; 2828 int bitsize(int x) 2929 { 3030 return x&(-x); 3131 } 3232 void update(int k,int id,int x) 3333 { 3434 while(id<=n) 3535 { 3636 bit[k][id]+=x; 3737 id+=bitsize(id); 3838 } 3939 } 4040 int query(int k,int id) 4141 { 4242 int ans=0; 4343 while(id>0) 4444 { 4545 ans+=bit[k][id]; 4646 id-=bitsize(id); 4747 } 4848 return ans; 4949 } 5050 int main() 5151 { 5252 scanf("%s",s+1); 5353 n=strlen(s+1); 5454 for(int i=1;i<=n;i++) 5555 { 5656 update(s[i]-'a'+1,i,1); 5757 } 5858 scanf("%d",&m); 5959 while(m--) 6060 { 6161 scanf("%d",&aa); 6262 if(aa==1) 6363 { 6464 scanf("%d %c",&bb,&kkk); 6565 update(s[bb]-'a'+1,bb,-1); 6666 s[bb]=kkk; 6767 update(s[bb]-'a'+1,bb,1); 6868 } 6969 else 7070 { 7171 scanf("%d%d",&bb,&cc); 7272 int ans=0,res; 7373 for(int i=1;i<=26;i++) 7474 { 7575 res=query(i,cc)-query(i,bb-1); 7676 if(res>0) ans++; 7777 } 7878 printf("%d\n",ans); 7979 } 8080 } 8181 8282 return 0; 8383 }
View Code
26个字母的线段树：
1 1 #include <iostream> 2 2 #include <cstdio> 3 3 #include <cmath> 4 4 #include <algorithm> 5 5 #include <set> 6 6 #include <queue> 7 7 #include <stack> 8 8 #include <string> 9 9 #include <cstring> 10 10 #include <vector> 11 11 #include <map> 12 12 //#include <unordered_map> 13 13 #define mem( a ,x ) memset( a , x ,sizeof(a) ) 14 14 #define rep( i ,x ,y ) for( int i = x ; i<=y ;i++ ) 15 15 #define lson l ,mid ,pos<<1 16 16 #define rson mid+1 ,r ,pos<<1|1 17 17 using namespace std; 18 18 typedef long long ll ; 19 19 typedef pair<int ,int> pii; 20 20 typedef pair<ll ,int> pli; 21 21 const int inf = 0x3f3f3f3f; 22 22 const int N = 1e5+100; 23 23 const ll mod =1e9+7 ; 24 24 char s[N],kkk; 25 25 int n,m; 26 26 int aa,bb,cc; 27 27 int tree[30][4*N],ans[30],a[N]; 28 28 void push_up(int rt) 29 29 { 30 30 for(int i=1;i<=26;i++) 31 31 tree[i][rt]=tree[i][rt<<1]+tree[i][rt<<1|1]; 32 32 } 33 33 void build(int rt,int l,int r) 34 34 { 35 35 if(l==r) 36 36 { 37 37 tree[a[l]][rt]++; 38 38 return; 39 39 } 40 40 int mid=l+r >>1; 41 41 build(rt<<1,l,mid); 42 42 build(rt<<1|1,mid+1,r); 43 43 push_up(rt); 44 44 } 45 45 void update(int rt,int p,int x,int y,int l,int r) 46 46 { 47 47 if(l==r) 48 48 { 49 49 tree[x][rt]--; 50 50 tree[y][rt]++; 51 51 return; 52 52 } 53 53 int mid=l+r>>1; 54 54 if(p<=mid) 55 55 update(rt<<1,p,x,y,l,mid); 56 56 else 57 57 update(rt<<1|1,p,x,y,mid+1,r); 58 58 push_up(rt); 59 59 } 60 60 void query(int l,int r,int rt,int L,int R) 61 61 { 62 62 if(r<=R&&L<=l) 63 63 { 64 64 for(int i=1;i<=26;i++) 65 65 ans[i]+=tree[i][rt]; 66 66 return ; 67 67 } 68 68 int mid=l+r>>1; 69 69 if(L<=mid) query(l,mid,rt<<1,L,R); 70 70 if(R>mid) query(mid+1,r,rt<<1|1,L,R); 71 71 } 72 72 int main() 73 73 { 74 74 scanf("%s",s+1); 75 75 n=strlen(s+1); 76 76 for(int i=1;i<=n;i++) 77 77 a[i]=s[i]-'a'+1; 78 78 build(1,1,n); 79 79 scanf("%d",&m); 80 80 while(m--) 81 81 { 82 82 scanf("%d",&aa); 83 83 if(aa==1) 84 84 { 85 85 scanf("%d %c",&bb,&kkk); 86 86 update(1,bb,s[bb]-'a'+1,kkk-'a'+1,1,n); 87 87 s[bb]=kkk; 88 88 } 89 89 else 90 90 { 91 91 scanf("%d%d",&bb,&cc); 92 92 int sum=0; 93 93 memset(ans,0,sizeof(ans)); 94 94 query(1,n,1,bb,cc); 95 95 for(int i=1;i<=26;i++) 96 96 if(ans[i]) 97 97 sum++; 98 98 printf("%d\n",sum); 99 99 } 100100 } 101101 102102 return 0; 103103 }
View Code
统计每个字母的下标。用set来快速删除加入元素。
1 1 #include <iostream> 2 2 #include <cstdio> 3 3 #include <cmath> 4 4 #include <algorithm> 5 5 #include <set> 6 6 #include <queue> 7 7 #include <stack> 8 8 #include <string> 9 9 #include <cstring> 1010 #include <vector> 1111 #include <map> 1212 //#include <unordered_map> 1313 #define mem( a ,x ) memset( a , x ,sizeof(a) ) 1414 #define rep( i ,x ,y ) for( int i = x ; i<=y ;i++ ) 1515 #define lson l ,mid ,pos<<1 1616 #define rson mid+1 ,r ,pos<<1|1 1717 using namespace std; 1818 typedef long long ll ; 1919 typedef pair<int ,int> pii; 2020 typedef pair<ll ,int> pli; 2121 const int inf = 0x3f3f3f3f; 2222 const int N = 1e5+100; 2323 const ll mod =1e9+7 ; 2424 char s[N],kkk; 2525 int n,m; 2626 int aa,bb,cc; 2727 set<int>st[30]; 2828 set<int>::iterator it; 2929 int main() 3030 { 3131 scanf("%s",s+1); 3232 n=strlen(s+1); 3333 for(int i=1;i<=n;i++) 3434 st[s[i]-'a'+1].insert(i); 3535 scanf("%d",&m); 3636 while(m--) 3737 { 3838 scanf("%d",&aa); 3939 if(aa==1) 4040 { 4141 scanf("%d %c",&bb,&kkk); 4242 st[s[bb]-'a'+1].erase(bb); 4343 s[bb]=kkk; 4444 st[s[bb]-'a'+1].insert(bb); 4545 } 4646 else 4747 { 4848 scanf("%d%d",&bb,&cc); 4949 int ans=0; 5050 for(int i=1;i<=26;i++) 5151 { 5252 it=st[i].lower_bound(bb); 5353 if(it==st[i].end()) continue; 5454 if((*it)<=cc) 5555 ans++; 5656 } 5757 printf("%d\n",ans); 5858 } 5959 } 6060 6161 return 0; 6262 }
View Code
哦根据状压的思想，把每个字母变成二进制 （1<<x） 判断是否有这个字母就看二进制那个位置上是否为1
判断字母个数就是看二进制上有多少个1。
如果目前没有这个字母，加上就可以了，如果有了，就不变。
| 很好解决了这个问题。
这样一个线段树就完事了。
1 1 #include <iostream> 2 2 #include <cstdio> 3 3 #include <cmath> 4 4 #include <algorithm> 5 5 #include <set> 6 6 #include <queue> 7 7 #include <stack> 8 8 #include <string> 9 9 #include <cstring> 10 10 #include <vector> 11 11 #include <map> 12 12 //#include <unordered_map> 13 13 #define mem( a ,x ) memset( a , x ,sizeof(a) ) 14 14 #define rep( i ,x ,y ) for( int i = x ; i<=y ;i++ ) 15 15 #define lson l ,mid ,pos<<1 16 16 #define rson mid+1 ,r ,pos<<1|1 17 17 using namespace std; 18 18 typedef long long ll ; 19 19 typedef pair<int ,int> pii; 20 20 typedef pair<ll ,int> pli; 21 21 const int inf = 0x3f3f3f3f; 22 22 const int N = 1e5+100; 23 23 const ll mod =1e9+7 ; 24 24 char s[N],kkk; 25 25 int n,m; 26 26 int aa,bb,cc; 27 27 int tree[4*N],ans[30],a[N]; 28 28 void push_up(int rt) 29 29 { 30 30 tree[rt]=tree[rt<<1]|tree[rt<<1|1]; 31 31 } 32 32 void build(int rt,int l,int r) 33 33 { 34 34 if(l==r) 35 35 { 36 36 tree[rt]=(1<<a[l]); 37 37 return; 38 38 } 39 39 int mid=l+r >>1; 40 40 build(rt<<1,l,mid); 41 41 build(rt<<1|1,mid+1,r); 42 42 push_up(rt); 43 43 } 44 44 void update(int rt,int p,int x,int l,int r) 45 45 { 46 46 if(l==r) 47 47 { 48 48 tree[rt]=1<<x; 49 49 return; 50 50 } 51 51 int mid=l+r>>1; 52 52 if(p<=mid) 53 53 update(rt<<1,p,x,l,mid); 54 54 else 55 55 update(rt<<1|1,p,x,mid+1,r); 56 56 push_up(rt); 57 57 } 58 58 int query(int l,int r,int rt,int L,int R) 59 59 { 60 60 if(r<=R&&L<=l) 61 61 { 62 62 return tree[rt]; 63 63 } 64 64 int mid=l+r>>1,ans=0; 65 65 if(L<=mid) ans|=query(l,mid,rt<<1,L,R); 66 66 if(R>mid) ans|=query(mid+1,r,rt<<1|1,L,R); 67 67 return ans; 68 68 } 69 69 int solve(int x) 70 70 { 71 71 int ans=0; 72 72 while(x) 73 73 { 74 74 if(x%2==1) ans++; 75 75 x/=2; 76 76 } 77 77 return ans; 78 78 } 79 79 int main() 80 80 { 81 81 scanf("%s",s+1); 82 82 n=strlen(s+1); 83 83 for(int i=1;i<=n;i++) 84 84 a[i]=s[i]-'a'; 85 85 build(1,1,n); 86 86 scanf("%d",&m); 87 87 while(m--) 88 88 { 89 89 scanf("%d",&aa); 90 90 if(aa==1) 91 91 { 92 92 scanf("%d %c",&bb,&kkk); 93 93 update(1,bb,kkk-'a',1,n); 94 94 s[bb]=kkk; 95 95 } 96 96 else 97 97 { 98 98 scanf("%d%d",&bb,&cc); 99 99 printf("%d\n",solve(query(1,n,1,bb,cc))); 100100 } 101101 } 102102 103103 return 0; 104104 }
View Code
