ABC238E - Range Sums

考え方

$0$$,1, 2, ..., N$を頂点とするグラフで考える．

「$(l, r)$が与えられる」を「頂点$(l - 1)$と頂点$r$の間に（無向）辺が張られる」と読み替えれば，

\begin{aligned}
& a_{1} + a_{2} + \cdots a_{N} \text{が計算できる} \\
&\Leftrightarrow 0 \text{と} N \text{が連結である}
\end{aligned}

となる．

【具体例】
例えば

\begin{aligned}
a_{3} + a_{4} + a_{5}
\end{aligned}

がわかっているとき，

\begin{aligned}
a_{6} + a_{7}
\end{aligned}

が与えられると

\begin{aligned}
(a_{3} + a_{4} + a_{5}) + (a_{6} + a_{7})
\end{aligned}

がわかるので，頂点$5$と$7$をマージする，ということである．

入力例を具体的に考えないとミスりそう．．．

---

したがって，UnionFindで$(l, r)$が与えられたら$(l - 1, r)$をマージしていき，最後に$0, N$が同じグループに属しているかどうかを判定すれば良い．
【参考】UnionFind木 - 競プロはじめました

回答例

N, Q = map(int, input().split())

# --- UnionFind ---
p = [-1] * (N + 1)
def root(x):
  if p[x] < 0:
    return x
  p[x] = root(p[x])
  return p[x]
 
def unite(x, y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  p[x] += p[y]
  p[y] = x
# --- UnionFind ---

for _ in range(Q):
  l, r = map(int, input().split())
  unite(l - 1, r)
  
print('Yes' if root(0) == root(N) else 'No')