題目描述

思路分析

????從一個(gè)圖中最少去除多少條邊可以使得圖中無環(huán)。明顯并查集入門題，我們只需要維護(hù)每個(gè)端點(diǎn)的集合，如果兩個(gè)端點(diǎn)在同一個(gè)集合，則說明出現(xiàn)環(huán)，則當(dāng)前邊不進(jìn)行并查集的合并，并且計(jì)數(shù)。

????

代碼展示

因?yàn)樯婕暗絽^(qū)間加操作，一開始考慮差分?jǐn)?shù)組，最終情況就是全部數(shù)為00。這樣每次操作就只修改兩個(gè)數(shù)，且觀察到其下標(biāo)對(duì)?k取模都是相同的。 然后考慮對(duì)原數(shù)組求一遍操作影響，看看子數(shù)組能否利用原數(shù)組的信息，思考了下感覺可行但代碼復(fù)雜。

后來又退回思考原數(shù)組，因?yàn)槭沁B續(xù)的區(qū)間加，假設(shè)sum[i]表示下標(biāo)對(duì)?k取模為?i的所有數(shù)的和。那每次操作就是將?sum的所有數(shù)都?+x。那最終為?0的充分條件就是?sum的所有數(shù)都是一樣的。反過來，也是必要條件。

因此對(duì)于每組詢問，統(tǒng)計(jì)該序列的下標(biāo)對(duì)k取模的所有數(shù)的和，看看是否為同一個(gè)數(shù)即可。

預(yù)處理原數(shù)組的下標(biāo)取模前綴和，每組詢問就兩個(gè)前綴和相減就得到該區(qū)間的下標(biāo)取模前綴和。因?yàn)?span id="s0sssss00s" class="math inline">k只有?10，所以每次詢問的復(fù)雜度就是?O(k)