ゆるふわ競プロオンサイト #3 : Sweets Distribution(Hard)

先にがっつりEasyを解いてしまい書き直すために。
https://www.hackerrank.com/contests/yfkpo3-1/challenges/sweets-distribution-hard

問題

N要素の4つの整数列A,B,C,Dが与えられる。
[1,N]を4つの長さが正の区間[1,i],[i+1,j],[j+1,k],[k+1,N]に分割したとき、sum(A[1,i])+sum(B[i+1,j])+sum(C[j+1,k])+sum(D[k+1,N])の最大値を求めたい。
さらに、以下Q個のクエリが与えられる。
各クエリ(L,R)では、各数列のL番目とR番目の要素を入れ替える。
各クエリ後の前述の最大値を求めよ。

解法

SegTreeに4*4の行列を乗せる。
その行列は、区間に対し先頭要素と末尾の要素を分割後の何番目の区間に属するかをindexとし、値としてその最大値を持つ。
区間連結に対する行列の合成は容易なので、クエリに対し2要素の値が変化する際、際SegTree上でO(logN)個の区間だけ対応して行列を更新すればよい。

int N,Q;
ll A[202020],B[202020],C[202020],D[202020];

struct Mat {
	ll v[4][4];
};

int NV=1<<19;
Mat val[1<<20];

Mat comp(Mat& A,Mat& B) {
	Mat C;
	int x,y,z;
	FOR(x,4) FOR(y,4) {
		C.v[x][y]=-1LL<<60;
		for(z=x;z<=y;z++) {
			C.v[x][y]=max(C.v[x][y],A.v[x][z]+B.v[z][y]);
			if(z<y) C.v[x][y]=max(C.v[x][y],A.v[x][z]+B.v[z+1][y]);
		}
	}
	return C;
}

void update(int entry) {
	entry += NV;
	while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	FOR(i,N) cin>>C[i];
	FOR(i,N) cin>>D[i];
	
	FOR(i,2*NV) {
		FOR(x,4) FOR(y,4) val[i].v[x][y]=-1LL<<60;
	}
	for(i=NV+N;i<2*NV;i++) val[i].v[3][3]=0;
	FOR(i,N) {
		val[NV+i].v[0][0]=A[i];
		val[NV+i].v[1][1]=B[i];
		val[NV+i].v[2][2]=C[i];
		val[NV+i].v[3][3]=D[i];
		if(i==N-1) val[NV+i].v[2][2]=-1LL<<60;
	}
	for(i=NV-1;i>=1;i--) val[i]=comp(val[i*2],val[i*2+1]);
	while(Q--) {
		cin>>x>>y;
		x--,y--;
		swap(A[x],A[y]);
		swap(B[x],B[y]);
		swap(C[x],C[y]);
		swap(D[x],D[y]);
		val[NV+x].v[0][0]=A[x];
		val[NV+x].v[1][1]=B[x];
		val[NV+x].v[2][2]=C[x];
		val[NV+x].v[3][3]=D[x];
		val[NV+y].v[0][0]=A[y];
		val[NV+y].v[1][1]=B[y];
		val[NV+y].v[2][2]=C[y];
		val[NV+y].v[3][3]=D[y];
		if(y==N-1) val[NV+y].v[2][2]=-1LL<<60;
		update(x);
		update(y);
		cout<<val[1].v[0][3]<<endl;
	}
	
	
	
}

まとめ

EasyとHardで入力形式が変わるの勘弁してほしいな。Q=1とかなら…。