注意到 DAG 連同性的充要條件與單調(diào)性，之后就轉(zhuǎn)成數(shù)據(jù)結(jié)構(gòu)題了。

首先注意到圖是一個(gè) DAG，那么我們考慮什么情況下是合法的。發(fā)現(xiàn)首先是 \(1\) 必須是唯一的一個(gè)入度為 \(0\) 的點(diǎn)，且所有點(diǎn)的入度不為 \(0\) 即可。雖然直接想到了但是補(bǔ)一個(gè)證明：

1.必要性。如果存在一個(gè)入度為 \(0\) 且非 \(1\) 的點(diǎn)，那么也就是說沒有有向邊可以到達(dá)，故非法。
2. 充分性。因?yàn)槌?\(1\) 外沒有入度為 \(0\) 的點(diǎn)，所以這些點(diǎn)將屬于同一個(gè)連通塊，而有因?yàn)榫腥攵龋也淮嬖诃h(huán)，所以故一定可以到達(dá)所有的點(diǎn)。

那么我們之后觀察到，對(duì)于一個(gè)區(qū)間，如果它包含了一個(gè)合法區(qū)間那么它也一定是合法的，所以我們至少希望求出每一個(gè) \(l\) 所對(duì)應(yīng)的最短區(qū)間 \([i,r_i]\)。之后我們只需要判斷對(duì)于一個(gè)詢問我們能否只使用 \(X\) 次來至少包含一個(gè) \([i,r_i]\)。即：

那么我們發(fā)現(xiàn)這樣 \(L\) 只需要擴(kuò)張到 \(i\) 即可，即 \(k=L-i\)，其中 \(L-X\leq i\leq L\)。那么轉(zhuǎn)成

那么就變成了定值，只需要隨便用一個(gè)數(shù)據(jù)結(jié)構(gòu)維護(hù)一下 RMQ 即可。

之后看如何維護(hù) \(r_i\)。由單調(diào)性想到雙指針。由于新加入的點(diǎn)都在 \([i,r_i]\) 之中所以我們只需要維護(hù)每個(gè)點(diǎn)目前的最大值即可。之后再看一下全局最小值是否大于等于 \(i\) 即可。用線段樹維護(hù)全局最小值與單點(diǎn)修改。