#796 Div.2 F. Sanae and Giant Robot set *

1688F
set，2500

题意

给出 $a,b$ 两个序列，并给出 $m$ 个区间 $[l_i,r_i]$，每次可以从它们中满足 ${\sum }_{i=l}^r{a}_i={\sum }_{i=l}^r{b}_i$ 的区间中任选一个，对这个区间的所有数执行 $a_i=b_i$，问能否经过若干次操作，使得 $a$ 序列和 $b$ 序列相同？

思路

区间可以被选当且仅当这个区间内两序列和相同，也就是差为0，所以用数组 $s_i$ 表示两个数组前缀和之差，即 $s_i=s_{i-1}+a_i-b_i$，则区间 $[l,r]$ 可以被选当且仅当 $s_{l-1}=s_r$，且操作过后 $s_{l-1}=s_l=...=s_r$，最终目标是令 $s$ 数组全为 $0$ ，因此选 $s_{l-1}\ne 0$ 的没有意义。

所以题可以转化为：对于区间 $[l,r]$ ，如果 $s_{l-1}=s_r=0$ ，则使 $s_{l-1}=s_l=...=s_r=0$ ， 是否可以使 $s$ 全为 $0$ 。

可以用 queue 存数组 $s$ 已经为0的位置，set 存还不是0的位置，依次遍历已经为0的位置所连的边，若另一点也为0，则遍历范围在这个区间内的 set 中元素并加入队列。如果最终队空但 set 未空，则无解。每个点至多加入队列一次，时间复杂度 $O((n+m)\log n)$

代码

int n, m;
int a[maxn], b[maxn], s[maxn];
vector<int> e[maxn];
void solve() {
    cin >> n >> m;
    set<int> se;
    for(int i = 1; i <= n; i++) {
    	cin >> a[i];
    	se.insert(i);
    }
    for(int i = 1; i <= n; i++) {
    	cin >> b[i];
    	s[i] = s[i-1] + a[i] - b[i];
    	e[i].clear();
    }
    e[0].clear();
    //se 表示非0的位置
    for(int i = 1; i <= m; i++) {
    	int x, y;
    	cin >> x >> y;
    	x--;
    	e[x].pb(y);
    	e[y].pb(x);
    }
    queue<int> q;
    for(int i = 0; i <= n; i++) {
    	if(!s[i]) {
    		q.push(i);
    		se.erase(i);
    	}
    }
    while(!q.empty()) {
    	int x = q.front();
    	q.pop();
    	for(int i = 0; i < e[x].size(); i++) {
    		int y = e[x][i];
    		if(s[y]) continue;
    		int l = min(x, y), r = max(x, y);
    		auto itl = se.lower_bound(l), itr = se.upper_bound(r);
    		for(auto it = itl; it != itr; it++) {
    			s[*it] = 0;
    			q.push(*it);
    		}
    		se.erase(itl, itr);
    	}
    }
    if(!se.empty()) {
    	cout << "NO\n";
    }
    else {
    	cout << "YES\n";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53