fork download
copy 
  1. /* Author : Do Thanh Triet - Tran Hung Dao High School for Gifted Student */
  2. /*      Algorithms + Data structures + Arts programming = Program <3      */
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. #define ft first
  9. #define sc second
  10. #define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  11. #define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
  12. #define FORD(i, r, l) for (int i = (r); i >= (l); --i)
  13. #define all(x) x.begin(), x.end()
  14.  
  15. #define endl '\n'
  16. #define int ll
  17.  
  18. using namespace std;
  19. using namespace __gnu_pbds;
  20.  
  21. typedef long long ll;
  22. typedef pair<int, int> ii;
  23.  
  24. const int maxn = 2e5 + 9;
  25. const int N =  2e5 + 9;
  26. const int MOD = 1e9 + 7;
  27. const long long INF = 0x3f;
  28. const long long oo = 1e18 +  9;
  29.  
  30. #define TASK "code"
  31.  
  32. int n, ans = 0;
  33. char a[maxn];
  34.  
  35. int cnt[maxn], cntLef[maxn], cntRig[maxn];
  36.  
  37. char s[maxn], t[maxn];
  38. int ddLef[maxn], ddRig[maxn];
  39.  
  40. queue<int>vec[maxn];
  41.  
  42. int lz[4 * N], st[4 * N];
  43.  
  44. void update(int id, int l, int r, int u, int v, int val) {
  45.  
  46.     if (lz[id]) {
  47.         st[id] += lz[id];
  48.         if (l != r) {
  49.             lz[id * 2 + 1] += lz[id];
  50.             lz[id * 2] += lz[id];
  51.         }
  52.         lz[id] = 0;
  53.     }
  54.     if (l > v || r < u || l > r || u > v) return;
  55.     if (l >= u && r <= v) {
  56.         st[id] += val;
  57.         if  (l != r) {
  58.             lz[id * 2] += val;
  59.             lz[id * 2 + 1] += val;
  60.         }
  61.         return;
  62.     }
  63.  
  64.     int mid = (l + r) >> 1;
  65.     update(id * 2, l, mid, u, v, val);
  66.     update(id * 2 + 1, mid + 1, r, u, v, val);
  67.     st[id] = max(st[id * 2], st[id * 2 + 1]);
  68. }
  69.  
  70. int get(int id, int l, int r, int u, int v) {
  71.     if (lz[id]) {
  72.         st[id] +=lz[id];
  73.         if(l != r) {
  74.             lz[id * 2 + 1] +=lz[id];
  75.             lz[id * 2] +=lz[id];
  76.         }
  77.         lz[id] = 0;
  78.     }
  79.     if (l > v || r < u) return INT_MIN;
  80.     if (l >= u && r <= v) {
  81.         return st[id];
  82.     }
  83.     int mid = (l + r) >> 1;
  84.  
  85.     return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
  86. }
  87.  
  88. void solve() {
  89.     cin >> n;
  90.     FOR(i,1,2 * n) {
  91.         cin >> a[i];
  92.         cnt[a[i] - 'a' + 1]++;
  93.     }
  94.     int tmp = n;
  95.     FOR(i,1,n) {
  96.         cntLef[a[i] - 'a' + 1]++;
  97.         cntRig[a[i + n] - 'a' + 1]++;
  98.     }
  99.     int ans = 0;
  100.     //cout << cnt[4] << ' ' << cntRig[4];
  101.     int ct = 0;
  102.     string outLef = "", outRig = "";
  103.     FORD(i, n, 1) {
  104.         if (cntLef[a[i] - 'a' + 1] > cnt[a[i] - 'a' + 1] / 2) {
  105.             --cntLef[a[i] - 'a' + 1];
  106.             ans += (tmp - i);
  107.             --tmp;
  108.             ++ct;
  109.             ddLef[i] = true;
  110.         }
  111.     }
  112.     tmp = n + 1;
  113.     FOR(i,n + 1, 2 * n) {
  114.         if (cntRig[a[i] - 'a' + 1] > cnt[a[i] - 'a' + 1] / 2) {
  115.             --cntRig[a[i] - 'a' + 1];
  116.             ans += (i - tmp);
  117.             ++tmp;
  118.             ddRig[i] = true;
  119.         }
  120.     }
  121.     ans += ct * ct;
  122.     int c1 = 0, c2 = 0;
  123.     FOR(i,1,n) {
  124.         if (!ddLef[i]) {
  125.             s[++c1] = a[i];
  126.         }
  127.         else {
  128.             outLef = outLef + a[i];
  129.         }
  130.     }
  131.     FOR(i,n + 1, 2 * n) {
  132.         if (ddRig[i]) outRig = outRig + a[i];
  133.     }
  134.     for (char ch : outLef) {
  135.         t[++c2] = ch;
  136.     }
  137.     FOR(i,n + 1, 2 * n) if (!ddRig[i]) t[++c2] = a[i];
  138.     for (char ch : outRig) {
  139.         s[++c1] = ch;
  140.     }
  141.     for (int i = 1; i <= c2; ++i) {
  142.         vec[t[i] - 'a' + 1].push(i);
  143.     }
  144.     FOR(i, 1, c2) {
  145.         update(1,1,c2,i,i,i);
  146.     }
  147.     int cur = 0;
  148.     FOR(i, 1, c1) {
  149.         int pos = vec[s[i] - 'a' + 1].front();
  150.         vec[s[i] - 'a' + 1].pop();
  151.         int realpos = get(1,1,c2,pos,pos);
  152.         ans += realpos - i;
  153.         update(1,1,c2,i,realpos - 1,1);
  154.     }
  155.     cout << ans;
  156. }
  157.  
  158. signed main()
  159. {
  160.     ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  161.     //freopen(TASK ".inp", "r", stdin);
  162.     //freopen(TASK ".out", "w", stdout);
  163.     solve();
  164.     return 0;
  165. }
  166. //Take a deep breath, don't be nervous, read the question slowly and understand the question, the question is often simpler than you think.
  167. /*
  168. Input:
  169.  
  170. */
  171. /*
  172. Output:
  173.  
  174. */
  175.  
Success #stdin #stdout 0.12s 138784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2XdVDq
language:
C++ (gcc 8.3)
created:
2 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!