fork download
copy 
  1. #include<iostream>
  2. #include<cstring>
  3. #include<stdio.h>
  4. using namespace std;
  5.  
  6. #define MAX 1000000
  7.  
  8. typedef long int ll;
  9.  
  10. ll tree[4*MAX][27]={0};
  11. char str[MAX+1];
  12.  
  13. void build_tree(int start, int end, ll idx)
  14. {
  15. 	if(start==end)
  16. 	{
  17. 	//	cout<<idx<<endl;
  18. 		int num= str[start]-97;
  19. 		tree[idx][num]++;
  20. 		return;
  21. 	}
  22. 	int mid= (start+end)/2;
  23. 	build_tree(start,mid,1+2*idx);
  24. 	build_tree(mid+1,end,2+2*idx);
  25. //	cout<<idx<<endl;
  26. 	for(int i=0;i<26;i++)
  27. 	 tree[idx][i]= tree[2*idx+1][i] + tree[2*idx+2][i];
  28.  
  29. }
  30.  
  31. int query(int ss, int se, int qs, int qe, ll idx, char ele)
  32. {
  33. 	if(ss>=qs && se<=qe)
  34. 	 {
  35. 	 	//cout<<ss<<" "<<se<<" "<<qs<<" "<<qe<<endl;
  36. 	 	return tree[idx][ele-97];
  37. 	 }
  38.  
  39. 	if(ss>qe || se<qs)
  40. 	return 0;
  41.  
  42. 	int mid= (ss+se)/2;
  43. 	int p= query(ss,mid,qs,qe,1+2*idx,ele)+ query(mid+1,se,qs,qe,2+2*idx,ele);
  44. //	cout<<" for segment : "<<ss<<" "<<se<<" "<<p<<endl;
  45. 	return p;
  46. }
  47.  
  48. int main()
  49. {
  50. 	scanf("%s",str);
  51. 	int len=strlen(str);
  52.  
  53. 	build_tree(0,len-1,0);
  54. 	int i,j;
  55. 	/*
  56. 	for(i=0;i<7;i++)
  57. 	{
  58. 		for(j=0;j<26;j++)
  59. 		{
  60. 			if(tree[i][j]!=0)
  61. 			{
  62. 				//cout<<i<<" : "<<(char)(j+97)<<" "<<tree[i][j]<<endl;
  63. 			}
  64. 		}
  65. 	}
  66. 	*/
  67. 	int low, high,que;
  68. 	scanf("%d",&que);
  69. 	while(que--){
  70. 	char k;
  71. 	cin>>k;
  72. 	scanf("%d %d",&low,&high);
  73. 	low--;
  74. 	high--;
  75. 	printf("%d\n",query(0,len-1,low,high,0,k));
  76. 	}
  77. 	return 0;
  78. }
Success #stdin #stdout 0s 425984KB
comments (?)
stdin
copy 
dhruvisevil
3
d 1 4
i 6 10 
s 2 9
stdout
copy 
1
2
1
https://ideone.com/TiwhbY
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!