Codeforces ECR #146 : E. Chain Chips

本番中test case 62まで来て落ちてる…。
https://codeforces.com/contest/1814/problem/E

問題

1～Nの点が並んでおり、i番と(i+1)番の点には重み付きの辺がある。

初期状態で各点にある駒を、辺に沿って動かすことを考える。
各点に1個ずつ駒がある状態で、かつどの駒も初期位置とは異なる位置に来るようにしたい。
駒の移動コストは辺の重みに一致するとき、移動コストの総和の最小値を求めたい。

辺の重みを変えるクエリが来るので、その都度上記値を求めよ。

解法

各辺を、2個以上左または右方向に移動する駒はない。
SegTreeを使い、区間における駒の移動コストの総和を管理しよう。
その際、各ノードには4つの値を載せて、

• 区間の左端とその外側の駒の行き来があるかどうか
• 区間の右端とその外側の駒の行き来があるかどうか

を持たせればよい。

template<class V,int NV> class SegTree_1 {
public:
	V val[NV*2];
	V comp(V x,V y){
		V a={1LL<<60,1LL<<60,1LL<<60,1LL<<60};
		
		int L0,L1,R0,R1;
		FOR(L0,2) FOR(R0,2) FOR(L1,2) FOR(R1,2) {
			if(R0==0&&L1==0) continue;
			a[L0+R1*2]=min(a[L0+R1*2],x[L0+R0*2]+y[L1+R1*2]);
		}
		return a;
	};
	
	void update(int entry, ll v) {
		entry += NV;
		val[entry][0]=0;
		val[entry][1]=v;
		val[entry][2]=v;
		val[entry][3]=v;
		
		
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<array<ll,4>,1<<20> st;
int N,Q;
ll A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>A[i];
		if(i!=0&&i!=N-2) st.update(i,A[i]);
	}
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		x--;
		A[x]=y;
		if(x!=0&&x!=N-2) st.update(x,A[x]);
		ll a=min({st.val[1][0],st.val[1][1],st.val[1][2],st.val[1][3]});
		if(N==2) {
			a=A[0];
		}
		else {
			a+=A[0]+A[N-2];
		}
		cout<<a*2<<endl;
	}
}

まとめ

コーナーケースで落としてるな…。