fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6. int main() {
  7. 	int n ; cin>>n;
  8. 	vector<char>arr(n);
  9. 	for(int i = 0 ; i<n;i++) cin>>arr[i];
  10.  
  11.     vector<vector<int>>prefix(n,vector<int>(26,0));
  12. 	prefix[0][arr[0]-'a']++; 
  13.  
  14.     for(int i = 1 ; i<n;i++){
  15.       for(int j = 0 ;j<26;j++){
  16. 		int e = arr[i] -'a';
  17. 		prefix[i][j] = (e==j)+ prefix[i-1][j] ;
  18. 		           	}
  19. 	}
  20. 	int q; cin>>q;
  21. 	for(int i = 0 ; i<q;i++){
  22. 		int l,r;cin>>l>>r;
  23. 		int count = 0 ; 
  24. 	//after precomputing in O(N) for q operations it only take O(N) time at max to find count 
  25. 	for(int j = 0 ; j<26;j++){
  26. 		int num = (l == 0) ? prefix[r][j] : prefix[r][j] - prefix[l - 1][j];
  27. 	    count += num * (1 + num) / 2;
  28.        }
  29.     cout<<count<<endl;
  30. 	}
  31.  
  32.  
  33. 	// your code goes here
  34.  
  35.  
  36. 	return 0;
  37. }
  38.  
  39.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
6
a b c a a b
4
0 1 
1 4
2 5
1 5
stdout
copy 
2
5
5
7
https://ideone.com/82RAUb
language:
C++ (gcc 8.3)
created:
2 days 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!