Codeforces #796 : Div1 C. Sanae and Giant Robot

ストーリー設定が邪魔だな…。
https://codeforces.com/contest/1687/problem/C

問題

整数列A,Bと、M通りの区間が与えられる。
いずれかの区間を指定し、Aのその区間内の総和が、Bの区間内の総和と等しいとき、Bの内容をAにコピーできる。
AをBに変換できるか答えよ。

解法

S[i]を、A[i]-B[i]のPrefix Sumとする。
区間[L,R]を選択するとき、S[L-1]=S[R]であれば、区間内を全要素S[R]に一致させられる。
この処理を用いてSをすべて0にできればよい。
S[x]=0となるxを見つけ、そこからL-1=xまたはR=xとなる区間を探してS[i]=0となるiを広げて行こう。

int T;
int N,M;
int A[202020],B[202020];
ll S[202020];
int L[202020],R[202020];
vector<int> E[202020];
set<int> vis;

void hoge(int L,int R) {
	vector<int> C;
	while(1) {
		auto it=vis.lower_bound(L);
		if(it==vis.end()||*it>=R) break;
		C.push_back(*it);
		S[*it]=0;
		vis.erase(it);
	}
	FORR(c,C) FORR(e,E[c]) if(S[e]==0) hoge(min(c,e),max(e,c));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&M);
		
		
		FOR(i,N) {
			scanf("%d",&A[i]);
		}
		FOR(i,N) {
			scanf("%d",&B[i]);
			S[i+1]=S[i]+A[i]-B[i];
		}
		vis.clear();
		FOR(i,N+1) {
			vis.insert(i);
			E[i].clear();
		}
		
		
		queue<int> Q;
		FOR(i,M) {
			scanf("%d%d",&x,&y);
			x--;
			E[x].push_back(y);
			E[y].push_back(x);
		}
		
		for(i=1;i<=N;i++) if(S[i]==0) {
			vis.erase(i);
			FORR(e,E[i]) if(S[e]==0) hoge(min(i,e),max(e,i));
		}
		FOR(i,N+1) if(S[i]) break;
		
		if(i==N+1) {
			cout<<"YES"<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		
	}
}

まとめ

最初の言い換えが思いつくかが鍵。