fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef unsigned long long ull;
  5. const double PI = acos(-1.0);
  6. const double  EPS = 1e-8;
  7. const ll MOD = 998244353;
  8. const int N = 100000 + 7;
  9.  
  10. vector<set<char>>seg;
  11. string str;
  12. int q,t,a,b;
  13. char c;
  14. set<char>::iterator it;
  15. void build(int p, int s, int e)
  16. {
  17. 	if (s == e)
  18. 	{
  19. 		seg[p].insert(str[s]);
  20. 		return;
  21. 	}
  22. 	build(p * 2, s, (s + e) / 2);
  23. 	build(p * 2 + 1, (s + e) / 2 + 1, e);
  24. 	it=seg[p*2].begin();
  25. 	for(;it!=seg[p*2].end();it++)
  26.         seg[p].insert(*it);
  27.     it=seg[p*2+1].begin();
  28. 	for(;it!=seg[p*2+1].end();it++)
  29.         seg[p].insert(*it);
  30. }
  31. void update(int p, int s, int e, int i, char v)
  32. {
  33. 	if (s == e)
  34. 	{
  35. 	    seg[p].clear();
  36. 	    seg[p].insert(v);
  37. 		return;
  38. 	}
  39. 	if (i <= (s + e) / 2)
  40. 		update(p * 2, s, (s + e) / 2, i, v);
  41. 	else
  42. 		update(p * 2 + 1, (s + e) / 2 + 1, e, i, v);
  43.     seg[p].clear();
  44. 	it=seg[p*2].begin();
  45. 	for(;it!=seg[p*2].end();it++)
  46.         seg[p].insert(*it);
  47.     it=seg[p*2+1].begin();
  48. 	for(;it!=seg[p*2+1].end();it++)
  49.         seg[p].insert(*it);
  50. }
  51. set<char> get(int p, int s, int e, int a, int b)
  52. {
  53. 	if (s >= a && e <= b)
  54.         return seg[p];
  55. 	if (s > b || e < a)
  56. 		return set<char>();
  57. 	set<char>comp;
  58. 	set<char>st1=get(p * 2, s, (s + e) / 2, a, b),st2=get(p * 2 + 1, (s + e) / 2 + 1, e, a, b);
  59.     it=st1.begin();
  60. 	for(;it!=st1.end();it++)
  61.         comp.insert(*it);
  62.     it=st2.begin();
  63. 	for(;it!=st2.end();it++)
  64.         comp.insert(*it);
  65.     return comp;
  66. }
  67. int main()
  68. {
  69.     cin>>str;
  70. 	scanf("%d", &q);
  71. 	seg.resize(4 * str.size());
  72. 	build(1, 0, str.size() - 1);
  73. 	while(q--)
  74.     {
  75.         scanf("%d%d",&t,&a);
  76.         a--;
  77.         if(t==1)
  78.         {
  79.             scanf(" %c",&c);
  80.             update(1,0,str.size()-1,a,c);
  81.         }
  82.         else
  83.         {
  84.             scanf("%d",&b);
  85.             b--;
  86.             printf("%d\n",get(1,0,str.size()-1,a,b).size());
  87.         }
  88.     }
  89. 	return 0;
  90. }
Runtime error #stdin #stdout 0s 4384KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/D2AmFn
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!