fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25. //_ ***************************** START Below *******************************
  26.  
  27.  
  28. // 6 4
  29. // abcaab
  30. // 1 1
  31. // 2 5
  32. // 3 6
  33. // 1 6
  34.  
  35.  
  36. string a;
  37. vector<vector<int>> qr;
  38.  
  39. vector<int> consistency(int n, int q){
  40.  
  41. 	vector<vector<int>> f(n+1, vector<int>(26, 0));
  42.  
  43. 	for(int i=0; i<n; i++){
  44.  
  45. 		for(int j=0; j<26; j++){
  46. 			f[i+1][j] = f[i][j];
  47. 		}
  48.  
  49. 		f[i+1][a[i] - 'a']++;
  50. 	}
  51.  
  52. 	vector<int> ans;
  53.  
  54. 	for(auto& qq : qr){
  55. 		int L = qq[0];
  56. 		int R = qq[1];
  57.  
  58. 		int val = 0;
  59. 		for(int j=0; j<26; j++){
  60.  
  61. 			int ct = f[R][j] - f[L-1][j];
  62.  
  63. 			val += (ct * (ct+1))/2;
  64. 		}
  65. 		ans.push_back(val);
  66.  
  67. 	}
  68.  
  69. 	return ans;
  70.  
  71. }
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86. // string a;
  87. // vector<vector<int>> qr;
  88.  
  89. vector<int> practice(int n, int q){
  90.  
  91. }
  92.  
  93.  
  94.  
  95.  
  96.  
  97. void solve() {
  98.  
  99.     int n, q;
  100.     cin>> n >> q;
  101.  
  102.     cin >> a;
  103.  
  104.     qr.resize(q);
  105.     for(int i=0; i<q; i++) {
  106.     	int x, y;
  107.     	cin >> x >> y;
  108.     	qr[i] = {x,y};
  109.     }
  110.  
  111.     auto ans = consistency(n, q);
  112.     for(auto& t : ans) cout << t << " "; cout << endl;
  113.  
  114.     // auto ans2 = practice(n, q);
  115.     // for(auto& p : ans2) cout << p << " "; cout << endl;
  116.     // cout << endl;
  117.  
  118.  
  119. }
  120.  
  121.  
  122.  
  123.  
  124.  
  125. int32_t main() {
  126.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  127.  
  128.     int t = 1;
  129.     // cin >> t;
  130.     while (t--) {
  131.         solve();
  132.     }
  133.  
  134.     return 0;
  135. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
6 4
abcaab
1 1
2 5
3 6
1 6
stdout
copy 
1 5 5 10
https://ideone.com/4T1299
language:
C++14 (gcc 8.3)
created:
10 hours 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!