Codeforces Round #796 (Div. 2) F. Sanae and Giant Robot

题目链接

给两个长度为 n n n 的数组 a a a 和 b b b ，以及 m m m 个区间 [ l i , r i ] [li,ri] [li,ri] 。每次你可以从这 m m m 个区间中选择一个满足 ∑ i = l r a i = ∑ i = l r b i sum_{i=l}^ra_i=sum_{i=l}^rb_i ∑i=lr​ai​=∑i=lr​bi​ 的区间 ( l , r ) (l,r) (l,r) ，然后对于 l ≤ i ≤ r l≤i≤r l≤i≤r 令 a i = b i a_i=b_i ai​=bi​ 。问通过上述操作是否可以将 a a a 变为 b b b 。

令 s i = s i − 1 + a i − b i s_i=s_{i-1}+a_i-b_i si​=si−1​+ai​−bi​，则区间 [ l , r ] [l,r] [l,r] 可以交换当且仅当 s l − 1 = s r s_{l−1}=s_r sl−1​=sr​，且交换过后对于 s i = s l − 1 ( l ≤ i ≤ r ) s_i=s_{l−1} (l≤i≤r) si​=sl−1​(l≤i≤r)。目标就是让 s i = 0 s_i=0 si​=0。

因为最后的目标是让所有位置都为零，所以置非零的数没有意义，所以可以将操作看成：对于区间 [ l , r ] [l,r] [l,r]，如果 s l − 1 = s r = 0 s_{l−1}=s_r=0 sl−1​=sr​=0 就将区间内的 s i s_i si​ 都置 0 0 0，最后看还有没有非零的 s i s_i si​ 就可以了。

可以对于每个位置，维护一个以这个位置为端点的区间的集合，然后枚举所有为 s i = 0 s_i=0 si​=0 的位置，再枚举以它为端点的区间，看是否可以将这个区间是否可以操作。

#include
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+9;
int T,n,m;
LL a[N],b[N],s[N];
setnz;
queueq;
vectore[N];
void solve()
{
	cin>>n>>m;
	nz.clear();
	while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
		s[i]=s[i-1]+a[i]-b[i];
		nz.insert(i);
		e[i].clear();
	}
	e[0].clear();
	for(int i=1,x,y;i<=m;i++)
	{
		cin>>x>>y;
		x--;
		e[x].pb(y);
		e[y].pb(x);
	}
	nz.insert(0);
	for(int i=0;i<=n;i++)
		if(!s[i])
		{
			q.push(i);
			nz.erase(i);
		}
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		for(int y:e[x])
		{
			if(s[y]) continue;
			int l=min(x,y),r=max(x,y);
			auto itl=nz.lower_bound(l),itr=nz.upper_bound(r);
			for(auto i=itl;i!=itr;i++)
				s[*i]=0,q.push(*i);
			nz.erase(itl,itr);
		}
	}
	cout<<(nz.empty()?"YESn":"NOn");
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--) solve();
	return 0;
}