fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define all(v) ((v).begin()),((v).end())
  4. #define vi vector<int>
  5.  
  6. const int N = 1e5 + 5;
  7.  
  8. int n,q,v[N],root, nxt[N];
  9.  
  10. vector<int> b[400];
  11.  
  12. std::map<int, vi> save;
  13.  
  14. void runNxt()
  15. {
  16. 	for (int i = 0; i < n; ++i)
  17. 	{
  18. 		save[v[i]].push_back(i);
  19. 	}
  20. 	for (int i = 0; i < n; ++i)
  21. 	{
  22. 		int idx = *upper_bound(all(save[v[i]]), i);
  23. 		nxt[i] = idx?idx:n + 1;
  24. 	}
  25. }
  26.  
  27. int main(int argc, char const *argv[])
  28. {
  29.  
  30. 	string s; cin>>s;
  31.  
  32. 	n = s.size();
  33.  
  34. 	root=sqrt(n);
  35.  
  36. 	int ct = (n + root - 1) / root;
  37.  
  38. 	for(int i=0; i<n; ++i)
  39. 		v[i] = s[i] - 'a';
  40.  
  41. 	runNxt();
  42.  
  43. 	for(int i=0; i<n; ++i)
  44. 		b[i/root].push_back(nxt[i]);
  45.  
  46. 	for(int i=0; i<ct; ++i)
  47. 		sort(b[i].begin(), b[i].end());
  48.  
  49.  	int q; scanf("%d", &q);
  50.  
  51. 	int T;
  52.  
  53. 	for(int i, l, r; i < q; ++i)
  54. 	{
  55. 		scanf("%d", &T);
  56.  
  57. 		if(T==2)
  58. 		{
  59. 			scanf("%d%d",&l,&r);
  60.  
  61. 			--l;--r;
  62.  
  63. 			int ans=0;
  64.  
  65. 			for(int j=l; j<=r; ++j)
  66. 			{
  67. 				if(j%root==0 && j+root-1<=r)
  68. 				{
  69. 					ans+= upper_bound(b[j/root].begin(), b[j/root].end(), r) - b[j/root].begin();
  70.  
  71. 					j+=root-1;
  72. 				}
  73.  
  74. 				else if(nxt[j] > r)
  75. 				{
  76. 					++ans;
  77. 				}
  78. 			}
  79.  
  80. 			printf("%d\n", ans);
  81. 		}
  82. 		else
  83. 		{
  84. 			char c;
  85.  
  86. 			scanf("%d %c",&l,&c);
  87.  
  88. 			--l;
  89.  
  90. 			v[l] = c - 'a';
  91.  
  92. 			int bucket = l / root;
  93.  
  94. 			b[bucket].clear();
  95.  
  96. 			for(int j=bucket*root; j<n && j<(bucket + 1)*root; ++j)
  97. 				b[bucket].push_back(*upper_bound(all(save[v[j]]), nxt[j]));
  98.  
  99. 			sort(b[bucket].begin(), b[bucket].end());
  100. 		}
  101. 	}
  102.  
  103. }
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7
stdout
copy 
1
3
7
https://ideone.com/rHvdGp
language:
C++14 (gcc 8.3)
created:
4 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!