fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define all(x) x.begin(), x.end()
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace __gnu_pbds;
  9. template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10. template <typename T, typename R> using o_map = tree<T, R, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  11. typedef long long ll;
  12.  
  13. #define inf 1e9
  14. #define MOD 1000000007
  15. #define vint vector<int>
  16. #define vll vector<ll>
  17. #define no cout << "NO" << endl;
  18. #define yes cout << "YES" << endl;
  19.  
  20. void solve() {
  21.     ll n ; cin >> n ;
  22.     string s ; cin >> s ;
  23.     map < char, int > freq ;
  24.     vector < ll > dp(n+1 ,0 ) ;
  25.     for (auto e : s ) freq[e] ++ ;
  26.     dp[n] = freq.size() ;
  27.  
  28.  
  29.     for (int i = n -1 ; i  >= 0 ; i -- ) {
  30.         if (freq[s[i]] == 1 ) dp[i] = dp[i+1] - 1 ;
  31.         else dp[i] = dp[i+1] ;
  32.         freq[s[i]] -=1 ;
  33.     //    cout << dp[i] <<"hhh" <<  endl ;
  34.     }
  35.     ll ans = 0 ;
  36.     for (int  i = 0 ; i<=  n ; i++) ans += dp[i] ;
  37.     cout << ans << endl ;
  38.  
  39. }
  40. int main() {
  41.     ios::sync_with_stdio(false);
  42.     cin.tie(nullptr);
  43.  
  44. #ifndef ONLINE_JUDGE
  45.     freopen("input.txt", "r", stdin);
  46.     freopen("output.txt", "w", stdout);
  47. #endif
  48.  
  49.     int t = 1;
  50.  
  51.     cin >> t;
  52.     while (t--) {
  53.         solve();
  54.     }
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/UmY4Pz
language:
C++ (gcc 8.3)
created:
14 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!