累積和配列 \(b=(b_0,b_1,\ldots,b_N)\) を考えます。すなわち各 \(i\ (0 \leq i \leq N)\) について、\(b_i\) は \(a\) の先頭 \(i\) 項の和を表すこととなります。

すると、高橋くんが与えてくれる情報は以下のように言い換えることが可能です。

• \(i\ (1 \leq i \leq Q)\) 個目の情報: \(a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}=b_{r_i}-b_{l_i-1}\) の値

はじめ、\(b\) の各要素について分かることは \(b_0\) の値が \(0\) であることのみです。よって \(a\) に含まれる全要素の総和 \(a_1+a_2+\cdots+a_N=b_N\) を特定することができるということは、以下と同値です。

• \(b_0\) からいくつかの情報を辿って \(b_N\) に辿り着くことができる。

より厳密な言い方をすると、以下のようになります。

• 頂点に \(0\) から \(N\) までの番号が振られた \(N+1\) 頂点 \(0\) 辺のグラフを用意する。その後、各 \(i\ (1 \leq i \leq Q)\) について頂点 \(l_i-1\) と頂点 \(r_i\) の間に無向辺を貼る。このとき、頂点 \(0\) と頂点 \(N\) が連結である。

これを判定することは、幅優先探索や Union-Find 木などを用いると \(O(N+Q)\) ないし \(O(N+Qα(N))\) 等の計算量で実行可能です。ここで、関数 \(α\) はアッカーマン関数の逆関数を表します。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

//union_find_tree
struct union_find{
    int N;
    vector<int> par, siz;
    union_find(int n) : N(n){
        par.resize(N);
        siz.resize(N, 1);
        for(int i=0; i<N; i++) par[i] = i;
    }
    int root(int X){
        if(par[X] == X) return X;
        return par[X] = root(par[X]);
    }
    bool same(int X, int Y){
        return root(X) == root(Y);
    }
    void unite(int X, int Y){
        X = root(X);
        Y = root(Y);
        if(X == Y) return;
        if(siz[Y] < siz[X]) std::swap(X, Y);
        par[X] = Y;
        siz[Y] += siz[X];
        siz[X] = 0;
    }
};

int main(){
	int N,Q; cin >> N >> Q;
	union_find tree(N+1);
	while(Q--){
		int l,r; cin >> l >> r;
		tree.unite(l-1,r);
	}
	string ans = "No";
	if(tree.same(0,N)) ans = "Yes";
	cout << ans << endl;
}