Codeforces #654 Div2 F. Raging Thunder

実装が割と面倒な問題。
https://codeforces.com/contest/1371/problem/F

問題

Nマスの上に左または右の矢印が書かれている。
今各マスにボールを置くことを考える。矢印にそってボールが転がり、両端または矢印の先端に挟まれた場所で停止する。
1か所に固まるボールの最大数を求めたい。

ここで、マスの区間を表すクエリが与えられる。
区間における矢印の向きを反転させ、そのつど上記最大数を求めよ。

解法

SegTreeを用い、区間に反転があったときとないときに(区間の左側に転がり出るボール、右に転がり出るボール、中にとどまるボールの最大数)のTrioを管理しよう。

template<int NV> class SegTree_3 {
public:
	vector<node> V[2];
	vector<int> R;
	SegTree_3(){
		int i,j;
		R.resize(NV*2,0);
		FOR(i,2) {
			V[i].resize(NV*2);
			for(j=NV;j<2*NV;j++) {
				if(i==0) V[i][j].P=1;
				else V[i][j].P=-1;
			}
			for(j=NV-1;j>=1;j--) V[i][j].P=V[i][j*2].P+V[i][j*2+1].P;
		}
	};
	
	node merge(node A,node B) {
		if(A.P==0) return B;
		if(B.P==0) return A;
		
		if(A.M==-1&&B.M==-1) {
			return {abs(A.P),-abs(B.P),0};
		}
		if(A.M==-1) {
			if(B.S==0) {
				if(B.P>0) return {abs(A.P),abs(B.P),0};
				else return {abs(A.P)+abs(B.P),0,-1};
			}
			else {
				if(B.P>0) return {abs(A.P),B.S,max(B.M,abs(B.P))};
				else return {abs(A.P)+abs(B.P),B.S,B.M};
			}
		}
		if(B.M==-1) {
			if(A.S==0) {
				if(A.P>0) return {abs(A.P)+abs(B.P),0,-1};
				else return {A.P,-B.P,0};
			}
			else {
				if(A.S>0) return {A.P,-(B.P+A.S),A.M};
				else return {A.P,-B.P,max(abs(A.S),A.M)};
			}
		}
		
		if(A.S==0 && B.S==0){
			if((A.P>0)==(B.P>0)) {
				return {A.P+B.P,0,0};
			}
			else if(A.P<0) {
				return {A.P,B.P,0};
			}
			else {
				return {A.P-B.P,0,-1};
			}
		}
		else if(A.S==0){
			if(A.P>0) {
				return {A.P+abs(B.P),B.S,B.M};
			}
			else {
				if(B.P<0) return {A.P+B.P,B.S,B.M};
				else return {A.P,B.S,max(B.M,B.P)};
			}
		}
		else if(B.S==0){
			if(B.P>0) {
				if(A.S<0) return {A.P,B.P,max(abs(A.S),A.M)};
				else return {A.P,A.S+B.P,A.M};
			}
			else {
				return {A.P,-abs(A.S)+B.P,A.M};
			}
		}
		else {
			if(A.S<0&&B.P>0) return {A.P,B.S,max({A.M,B.M,abs(A.S),abs(B.P)})};
			else return {A.P,B.S,max({A.M,B.M,abs(A.S)+abs(B.P)})};
		}
	}
	
	
	node getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return {0,0,0};
		
		if(x<=l && r<=y) return V[R[k]][k];
		if(R[k]) {
			R[k]=0;
			R[2*k]^=1;
			R[2*k+1]^=1;
			swap(V[0][k],V[1][k]);
		}
		node A=getval(x,y,l,(l+r)/2,k*2);
		node B=getval(x,y,(l+r)/2,r,k*2+1);
		return merge(A,B);
	}
	
	void update(int x,int y,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			R[k]^=1;
		}
		else if(l < y && x < r) {
			if(R[k]) {
				R[k]=0;
				R[2*k]^=1;
				R[2*k+1]^=1;
			}
			update(x,y,l,(l+r)/2,k*2);
			update(x,y,(l+r)/2,r,k*2+1);
			int i;
			FOR(i,2) {
				V[i][k]=merge(V[i^R[2*k]][2*k],V[i^R[2*k+1]][2*k+1]);
			}
		}
	}
};

まとめ

やりたいことはわかっても、これ本番中に詰め切るのしんどいな。