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

1688F
set,2500

The question

give $a,b$ Two sequences , And give $m$ Intervals $[l_i,r_i]$, You can satisfy from them every time ${\sum }_{i=l}^r{a}_i={\sum }_{i=l}^r{b}_i$ Any one of the intervals of , Execute on all numbers in this interval $a_i=b_i$, Ask if you can go through several operations , bring $a$ Sequence sum $b$ The same sequence ？

Ideas

An interval can be selected if and only if the sum of two sequences in this interval is the same , That is, the difference is 0, So use arrays $s_i$ Represents the difference between the prefixes of two arrays , namely $s_i=s_{i-1}+a_i-b_i$, Then interval $[l,r]$ Can be selected if and only if $s_{l-1}=s_r$, And after the operation $s_{l-1}=s_l=...=s_r$, The ultimate goal is to make $s$ The array is all $0$ , So choose $s_{l-1}\ne 0$ It doesn't make sense .

So the question can be translated into ： For interval $[l,r]$ , If $s_{l-1}=s_r=0$ , makes $s_{l-1}=s_l=...=s_r=0$ , Is it possible to make $s$ All for $0$ .

It can be used queue Save array $s$ Have been to 0 The location of ,set Not yet 0 The location of , The sequence traversal has been 0 The side connected by the position of , If the other point is also 0, Then traverse the range within this interval set And add to the queue . If the final team is empty but set Not empty , There is no solution. . Each point can join the queue at most once , Time complexity $O((n+m)\log n)$

Code

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  Express non 0 The location of 
    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";
    }
}