Codeforces #1011 : Div2 F2. Serval and Colorful Array (Hard Version)

思ったよりコードが少なくて済んだ。
https://codeforces.com/contest/2085/problem/F2

問題

N要素の整数列Aが与えられる。
Aの各要素は1～Kのいずれかである。

Aの隣接要素のswapを繰り返し、Aの長さKの連続部分列として、1～Kが1個ずつ含まれるものを作りたい。
最小swap回数はいくらか。

解法

先に連続部分列の位置が決まっている場合、そこに詰める値は、K/2個は部分列の真ん中より左側から、残りは右側から拾うことになる。
このことから、値毎に連続部分列の位置がどこであれば、。左/右からswap何回で部分列に入れられるかを考えよう。
これは区間に同じ値を足しこむBITを使い、位置毎の総swapを求めることで行える。

int T,N,K;
int A[404040];
vector<int> P[404040];

template<class V, int ME> class BIT_r {
public:
	V bit[2][1<<ME];
	BIT_r(){clear();};
	void clear() {ZERO(bit);};
	
	void update(int entry, V val0, V val1) {
		entry++;
		while(entry <= 1<<ME) bit[0][entry-1]+=val0, bit[1][entry-1] += val1, entry += entry & -entry;
	}
	V total(int entry) {
		if(entry<0) return 0;
		int e=entry++;
		V v0=0,v1=0;
		while(entry>0) v0+=bit[0][entry-1], v1+=bit[1][entry-1], entry -= entry & -entry;
		return e*v0+v1;
	}
	void add(int L, int R, V val) { // add val to L<=x<=R
		update(L,val,-val*(L-1));
		update(R+1,-val,val*R);
	}
};
BIT_r<ll,21> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,K) P[i].clear();
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
			P[A[i]].push_back(i);
			bt.add(i,i,-bt.total(i));
		}
		FOR(i,K) {
			x=P[i][0];
			bt.add(0,0,x);
			bt.add(1,x,-1);
			x=P[i].back();
			bt.add(x+1,N-1,1);
			FOR(j,P[i].size()-1) {
				x=P[i][j];
				y=P[i][j+1];
				bt.add(x+1,y-1,1);
				bt.add((x+y)/2+1,y,-2);
				bt.add(y,y,1);
				if((y-x)%2) {
					bt.add((x+y)/2+1,(x+y)/2+1,1);
				}	
			}
		}
		ll ret=1LL<<60;
		FOR(i,N) ret=min(ret,bt.total(i));
		FOR(i,K) ret-=abs(i-(K-1)/2);
		cout<<ret<<endl;
		
	}
}

まとめ

これ部分点必要だったのかな…。