Submission #2206025

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll INF = 1e9+7;

class BIT {
	int n;
	vector<int> vs;
	public:
	BIT(int size) {
		n = size;
		vs = vector<int>(n);
	}
	//O(log n)
	void add(int k, int a) {
		for(int i = k; i < n; i |= i + 1) vs[i] += a;
	}
	//[s,t) O(log n)
	int sum(int s, int t) {
		if(s > 0) return sum(0, t) - sum(0, s);
		int res = 0;
		for(int i = t - 1; i >= 0; i = (i & (i + 1)) - 1) res += vs[i];
		return res;
	}
};

// 各ノードの情報
template <typename T>
struct node {
	T v, lazy;
	node(){
		v = INF;
		lazy = {};
	}
	// ノードの値の更新
	void merge(T vl, T vr){
		v = min(vl, vr);
	}
	// ノードの値の更新(lazy適用)
	T add(int l, int r, T _v={}){
		T sum = lazy + _v;
		v += sum;
		lazy = 0;
		return sum;
	}
	// 遅延分の変更(加算)
	void addLazy(T v){
		lazy += v;
		// lazy.X += v.X;
		// lazy.Y += v.Y;
	}
};

template <typename T, typename NODE=node<T> >
class SegTree{
	// 遅延分の適応と伝播(現在のノードの値を確定させてLazyを伝搬させる)
	void propLazy(int a, int b, int k, T v={}){
		T lazy = data[k].add(a, b, v);
		if( k < N ){
			data[k*2+0].addLazy(lazy);
			data[k*2+1].addLazy(lazy);
		}
	}
	// セグメントツリーをたどる
	inline T prop(int l, int r, T v, int a, int b, int k=1){
		// 今いるノードの値を確定させる
		propLazy(a, b, k);
		// たどる
		NODE nd;	// 結果保存用(範囲外の場合は初期値が返る)
		if( l <= a && b <= r ){
			// 完全に範囲内の場合
			propLazy(a, b, k, v);
			return data[k].v;
		}else if( l < b && a < r ){
			// 中途半端に含まれる場合
			int m = (a+b) / 2;
			T vl = prop(l,r,v, a, m, k*2);
			T vr = prop(l,r,v, m, b, k*2+1);
			data[k].merge( data[k*2].v, data[k*2+1].v );
			nd.merge( vl, vr );
		}
		return nd.v;
	}

public:
	vector<NODE> data;
	int N;
	SegTree(int _N){
		// _N <= (N = 2^k) を満たすNを見つける
		N = 1;
		while( N < _N ) N<<=1;
		data.resize(N*2);
	}
	// セグメントツリーの更新(指定した場所の値をvに変更)
	void update(int l, T v){
		// auto _v = v;
		// _v.X -= get(l).X;
		// _v.Y -= get(l).Y;
		// prop(l, l+1, _v, 0, N);
		prop(l, l+1, v - get(l), 0, N);
	}
	// セグメントツリーの更新(範囲に加算)
	T add(int l, int r, T v){
		return prop(l,r,v,0,N);
	}
	// 値を取得 [l,r)
	T get(int l, int r){
		return prop(l,r,{},0,N);
	}
	// 値を取得 [l,l+1)
	T get(int l){
		return prop(l,l+1,{},0,N);
	}
};


typedef complex<ll> C;
int main(){
	ios_base::sync_with_stdio(false);
	string S;

	cin >> S;
	int N = S.length();

	int cnt[30]={};
	for(auto c: S) cnt[c-'a']++;

	int odd = 0;
	for(char c='a'; c<='z'; c++) if(cnt[c-'a']%2) odd++;
	if( odd > 1 ){
		cout << -1 << endl;
		return 0;
	}

	vector<SegTree<int>> sg(30, N+1);
	vector<SegTree<int>> Pos(30, N+1);
	BIT btI(N+1);
	BIT btD(N+1);
	rep(i,N){
		int k = S[i] - 'a';
		sg[k].update(i, i);
		Pos[k].update(i, i);
	}

	ll ans = 0;
	string T;
	rep(i,N/2){
		vector<pii> v;
		rep(k,26) if(cnt[k] > 1){
			//ll idx = sg[k].get(i, N+1);
			ll idx = Pos[k].get(0, N+1);
			v.emplace_back(idx, k);
		}
		sort(all(v));
		int k = v[0].Y;
		int ad = btI.sum(0, v[0].X) - btD.sum(0, v[0].X+1);
		ans += v[0].X + ad - i;
		T += 'a' + k;
		cnt[k] -= 2;
		int pos = Pos[k].get(i, N+1);
		sg[k].update(pos, INF);
		Pos[k].update(pos, INF);
		//rep(j,26) sg[j].add(0, pos, 1);
		btI.add(0, 1);
		btD.add(pos, 1);
	}
	if( odd ) rep(k,26) if(cnt[k] % 2){
		T += 'a' + k;
		cnt[k] -= 1;
		//auto idx = sg[k].get(N/2, N+1);
		auto pos = Pos[k].get(0, N+1);
		int ad = btI.sum(0, pos) - btD.sum(0, pos+1);
		//cout << btD.sum(pos, N+1) << endl;
		ans += pos + ad - N/2;
		sg[k].update(pos, INF);
		Pos[k].update(pos, INF);
		//rep(j,26) sg[j].add(0, pos, 1);
		btI.add(0, 1);
		btD.add(pos, 1);
		break;
	}
	rep(i,N/2){
		int k = T[N/2-i-1] - 'a';
		//auto idx = sg[k].get(i+N/2, N+1);
		auto pos = Pos[k].get(0, N+1);
		int ad = btI.sum(0, pos) - btD.sum(0, pos+1);
		ans += pos + ad - (i + N/2 + odd);
		T += 'a' + k;
		sg[k].update(pos, INF);
		Pos[k].update(pos, INF);
		//rep(j,26) sg[j].add(0, pos, 1);
		btI.add(0, 1);
		btD.add(pos, 1);
	}

	//cout << T << endl;
	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result