제출 #1163428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163428		gelastropod	Ekoeko (COCI21_ekoeko)	C++20	110 / 110	36 ms	14184 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct node {
	int s, e, m, v;
	node *l, *r;
	
	node (int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(e - s + 1) {
		if (s != e)
			l = new node(s, m),
			r = new node(m + 1, e);
	}
	
	void upd(int n) {
		if (s == e) {
			v = 1 - v;
			return;
		}
		if (n <= m)
			l->upd(n);
		else
			r->upd(n);
		v = l->v + r->v;
	}
	
	int qry(int a, int b) {
		if (s > b || e < a)
			return 0;
		if (a <= s && b >= e)
			return v;
		return l->qry(a, b) + r->qry(a, b);
	}
} *root;

signed main() {
	int n;
	string s;
	cin >> n >> s;
	vector<int> freq(26, 0);
	for (int i = 0; i < n; i++) {
		freq[s[i] - 'a']++;
	}
	for (int i = n; i < 2 * n; i++) {
		freq[s[i] - 'a']--;
	}
	for (int i = 0; i <= 26; i++)
		freq[i] /= 2;
	vector<bool> moved(n, false);
	int ans = 0, count = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (freq[s[i] - 'a'] > 0) {
			moved[i] = true;
			count++;
			ans += n - count - i;
			freq[s[i] - 'a']--;
		}
	}
	int orgcount = count;
	string s1 = "";
	for (int i = 0; i < n; i++) {
		if (!moved[i])
			s1 += s[i];
	}
	for (int i = 0; i < n; i++) {
		if (moved[i])
			s1 += s[i];
	}
	for (int i = n; i < 2 * n; i++) {
		s1 += s[i];
	}
	moved = vector<bool>(n, false);
	for (int i = n; i < 2 * n; i++) {
		if (freq[s[i] - 'a'] < 0) {
			moved[i - n] = true;
			ans += i - n + count;
			count--;
			freq[s[i] - 'a']++;
		}
	}
	string crnt, ref;
	for (int i = 0; i < n - orgcount; i++) {
		crnt += s1[i];
	}
	for (int i = n; i < 2 * n; i++) {
		if (moved[i - n])
			crnt += s[i];
	}
	for (int i = n - orgcount; i < n; i++) {
		ref += s1[i];
	}
	for (int i = n; i < 2 * n; i++) {
		if (!moved[i - n])
			ref += s[i];
	}
	vector<queue<int>> indices(26, queue<int>());
	for (int i = 0; i < n; i++)
		indices[ref[i] - 'a'].push(i);
	root = new node(0, n - 1);
	for (int i = 0; i < n; i++) {
		int crntind = indices[crnt[i] - 'a'].front();
		indices[crnt[i] - 'a'].pop();
		root->upd(crntind);
		ans += root->qry(0, crntind);
	}
	cout << ans << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40