USACO競賽2020-2021新賽季第一場即將開始，為(wei) 方便同學了解題目思路，準備了四期《USACO題解》專(zhuan) 題，本期進入第三期解題思路提供 2019-2020賽季各級別晉級題目題解參考，希望能為(wei) 同學們(men) 提供有用的幫助。
1
Task1
題目：
Farmer John 的 N 頭奶牛（1≤N≤105）站成一排。對於(yu) 每一個(ge) 1≤i≤N，從(cong) 左往右數第 i 頭奶牛的編號為(wei) i。Farmer John 想到了一個(ge) 新的奶牛晨練方案。他給奶牛們(men) M 對整數 (L1,R1)…(LM,RM)，其中 1≤M≤100。他讓她們(men) 重複以下包含 M 個(ge) 步驟的過程 K（1≤K≤109）次：對於(yu) 從(cong) 11到 M 的每一個(ge) i：當前從(cong) 左往右數在位置 Li…Ri的奶牛序列反轉她們(men) 的順序。當奶牛們(men) 重複這一過程 K次後，請對每一個(ge) 1≤i≤N 輸出從(cong) 左往右數第 i 頭奶牛的編號。測試點性質：測試點 2 滿足 N=K=100。測試點 3-5 滿足 K≤103。測試點 6-10 沒有額外限製。
輸入格式（文件名：swap.in）：輸入的第一行包含 N, M 和 K。對於(yu) 每一個(ge) 1≤i≤M，第 i+1 行包含 Li和 Ri，均為(wei) 範圍在 1…N內(nei) 的整數，其中 Li<Ri。
輸出格式（文件名：swap.out）：在第 i 行輸出指令序列執行了 K 次後奶牛序列中從(cong) 左往右數第 i 個(ge) 元素的編號。
輸入樣例：7 2 22 53 7
輸出樣例：1243576初始時，奶牛們(men) 的順序從(cong) 左往右為(wei) [1,2,3,4,5,6,7]。在這一過程的第一步過後，順序變為(wei) [1,5,4,3,2,6,7]。在這一過程的第二步過後，順序變為(wei) [1,5,7,6,2,3,4]。再重複這兩(liang) 個(ge) 步驟各一次可以得到樣例的輸出。
解析：用快速冪去維護置換根據題意，每次操作時都會(hui) 將區間 (L1,R1)…(LM,RM)內(nei) 的奶牛翻轉一次。由於(yu) 這個(ge) 翻轉是固定的，所以每次操作奶牛編號的置換也是固定的。我們(men) 可以預處理出一個(ge) 映射 f(x)表示 x經過置換後變成什麽(me) 。預處理的時間複雜度為(wei) ：O(nm)此時我們(men) 隻需要求 fk(x)f 即可得到答案。通過觀察我們(men) 發現該置換符合結合律。舉(ju) 個(ge) 例子：令 h 表示“先 f 後 g ”的置換。設 f={2,1,4,3} , g={3,1,2,4}。那麽(me) “先 f 後 g ”的映射就是{1,3,4,2} 。則 h 可以表示為(wei) h(x)=g(f(x)) 。這樣我們(men) 就可以使用快速冪去求 fk(x)f 。總的時間複雜度為(wei) ：O(nm+nlog k)。
Task 2
題目：Farmer John 想要給他的奶牛們(men) 建造一個(ge) 三角形牧場。有 N（3≤N≤105）個(ge) 柵欄柱子分別位於(yu) 農(nong) 場的二維平麵上不同的點 (X1,Y1)…(XN,YN)。他可以選擇其中三個(ge) 點組成三角形牧場，隻要三角形有一條邊與(yu) x 軸平行，且有另一條邊與(yu) y 軸平行。FJ 可以組成的所有可能的牧場的麵積之和等於(yu) 多少？
測試點性質：
測試點 2 滿足 N=200。
測試點 3-4 滿足 N≤5000。
測試點 5-10 沒有額外限製。
輸入格式（文件名：triangles.in）：第一行包含 N。以下 N 行每行包含兩(liang) 個(ge) 整數 Xi 和 Yi，均在範圍 −104…104 之內(nei) ，描述一個(ge) 柵欄柱子的位置。
輸出格式（文件名：triangles.out）：由於(yu) 麵積之和不一定為(wei) 整數且可能非常大，輸出麵積之和的兩(liang) 倍模 109+7 的餘(yu) 數。
輸入樣例：40 00 11 01 2
輸出樣例：3柵欄木樁 (0,0)、(1,0) 和 (1,2) 組成了一個(ge) 麵積為(wei) 1 的三角形，(0,0)、(1,0) 和 (0,1) 組成了一個(ge) 麵積為(wei) 0.5 的三角形。所以答案為(wei) 2*(1+0.5)=3。
解析：數據量105，如果依次取枚舉(ju) 三角形的三個(ge) 頂點，複雜度O(n3)，必然超時。題目中說隻關(guan) 心一條邊和x軸重合，另一條邊和y軸重合的三角形，那麽(me) 這兩(liang) 條邊組成了一個(ge) 直角，我們(men) 先嚐試枚舉(ju) 這個(ge) 直角，看看以一個(ge) 點作為(wei) 直角頂點，能組成的所有三角形麵積能否快速求出。
考慮如下圖的樣子:
X點是我們(men) 所求的點，在X的左邊還有A，B，C三個(ge) 點，他們(men) 縱坐標相等。在X的下方還有F，E，D三個(ge) 點，他們(men) 橫坐標相等。那麽(me) 此時以X為(wei) 直角頂點，能組成多少個(ge) 三角形，他們(men) 的麵積的二倍的和是多少呢。我們(men) 設兩(liang) 點之間的線段長度已經用小寫(xie) 字符標在圖上，可以算出，現在的總麵積是：
(a+b+c)*d+(b+c)*d+c*d+(a+b+c)*(d+e)+(b+c)*(d+e)+c*(d+e)+(a+b+c)*(d+e+f)+(b+c)*(d+e+f)+c*(d+e+f)(a+b+c)∗d+(b+c)∗d+c∗d+(a+b+c)∗(d+e)+(b+c)∗(d+e)+c∗(d+e)+(a+b+c)∗(d+e+f)+(b+c)∗(d+e+f)+c∗(d+e+f)=(a+2*b+3*c)*(f+2*e+3*d)=(a+2∗b+3∗c)∗(f+2∗e+3∗d)
這個(ge) 點的值，隻和與(yu) 自己橫坐標相同的點，和與(yu) 自己縱坐標相同的點有關(guan) 。而且有點類似於(yu) 前綴和，可以開一個(ge) 數組，去記錄每個(ge) 橫縱坐標各自積累的和是多少。當又來了一個(ge) 新點，則把這個(ge) 點對應的橫坐標位置的和，加上4倍與(yu) 上一個(ge) 點之間的距離。縱坐標位置的和同理處理，所以我們(men) 發現還需要記錄每行每列出現了幾個(ge) 數字了。再來一個(ge) 新點，就加5倍距離，以此類推。
那麽(me) ，我們(men) 按照x坐標從(cong) 小到大，y坐標從(cong) 小到大的順序，依次去枚舉(ju) 每個(ge) 點i，去做一下上述處理，然後計算結果出來。但是這個(ge) 計算方式隻對目前我們(men) 這種方向的三角形有效，事實上三角形的直角有四個(ge) 方向，分別是衝(chong) 著一二三四四個(ge) 象限的方向。現在我們(men) 處理的，是直角在第三象限的情況。不過並不難處理，隻要改一下點的排序方式，把同樣的事情做4遍就行了。
Task 3題目：Farmer John 的新牛棚的設計十分奇怪：它由編號為(wei) 1…N 的 N 間房間（2≤N≤2500），以及 N−1 條走廊組成。每條走廊連接兩(liang) 間房間，使得每間房間都可以沿著一些走廊到達任意其他房間。牛棚裏的每間房間都裝有一個(ge) 在表盤上印有標準的整數 1…12 的圓形時鍾。然而，這些時鍾隻有一根指針，並且總是直接指向表盤上的某個(ge) 數字（它從(cong) 不指向兩(liang) 個(ge) 數字之間）。奶牛 Bessie 想要同步牛棚中的所有時鍾，使它們(men) 都指向整數 12。然而，她頭腦稍有些簡單，當她在牛棚裏行走的時候，每次她進入一間房間，她將房間裏的時鍾的指針向後撥動一個(ge) 位置。例如，如果原來時鍾指向 5，現在它會(hui) 指向 6，如果原來時鍾指向 12，現在它會(hui) 指向 1。如果 Bessie 進入同一間房間多次，她每次進入都會(hui) 撥動這間房間的時鍾。請求出 Bessie 可能的出發房間數量，使得她可以在牛棚中走動並使所有時鍾指向 12。注意 Bessie 並不撥動她出發房間的時鍾，但任意時刻她再次進入的時候會(hui) 撥動它。時鍾不會(hui) 自己走動；時鍾隻會(hui) 在 Bessie 進入時被撥動。此外，Bessie 一旦進入了一條走廊，她必須到達走廊的另一端（不允許走到一半折回原來的房間）。測試點性質：
測試點 2-7 滿足 N≤100。測試點 8-15 沒有額外限製。
輸入格式（文件名：triangles.in）：輸入的第一行包含 N。下一行包含 N 個(ge) 整數，均在範圍 1…12 之內(nei) ，表示每間房間初始時的時鍾設置。以下 N−1 行每行用兩(liang) 個(ge) 整數 a 和 b 描述了一條走廊，兩(liang) 數均在範圍 1…N 之內(nei) ，為(wei) 該走廊連接的兩(liang) 間房間的編號。
輸出格式（文件名：triangles.out）：輸出出發房間的數量，使得 Bessie 有可能使所有時鍾指向 12。
輸入樣例：411 10 11 111 22 32 4
輸出樣例：1在這個(ge) 例子中，當且僅(jin) 當 Bessie 從(cong) 房間 2 出發時她可以使所有房間的時鍾指向 12（比如，移動到房間 1，2，3，2，最後到 4）。
解析：因為(wei) 題目求起點有多少個(ge) ，那麽(me) 我們(men) 依次枚舉(ju) 每個(ge) 點作為(wei) 起點，把它當做樹根，從(cong) 它出發往孩子走，看看能不能做到。每當Farmer John沿著一條線在樹上走的時候，遇到的每個(ge) 點時間都往前加1。考慮從(cong) 樹上某個(ge) 結點u走到它的孩子v，那麽(me) u和v上的時間都往前加1了。也就是說要改就父子一起改，父子之間的差是不變的。既然題目中是驗證是否能完成，我們(men) 不妨貪心地看，每次不停地從(cong) 父子之間來回走，直到把孩子改成12，這時候根據父子差固定，我們(men) 就能知道u現在是多少。然後再去搞下一個(ge) 孩子，再確定u的值。直到把所有孩子都改好，此時u固定到了某個(ge) 數。回到上一層，再由父親(qin) 把u改成12。那麽(me) 這麽(me) 一輪下來，最後除了根，其他點都是12了。那麽(me) 根如果正好是12，說明是可以的。如果根不是12呢？其實根是1也行，因為(wei) 這樣就最後的時候從(cong) 根的最後一個(ge) 孩子停下，不走回來。這時候根和最後一個(ge) 孩子的時間會(hui) 差一個(ge) 。除了這兩(liang) 種情況，其他都不行。這樣枚舉(ju) 每個(ge) 點做根，每次根確定以後，一遍dfs，總的時間複雜度是O(n2)，不超時。實際寫(xie) 的時候，用一個(ge) c數組表示每個(ge) 點現在的時間，然後用0表示12，這樣每次對12取模就行了，寫(xie) 起來比較方便。最終目標也是把所有點調成0。
2
Task 1題目：Bessie 在過去的 M 天（2≤M≤109）內(nei) 參加了 N 次（1≤N≤105）擠奶。然而，她不太記得她是什麽(me) 時候參加每次擠奶了。對於(yu) 每次擠奶 i=1…N，她知道這次擠奶的時間不早於(yu) 第 Si 天（1≤Si≤M）。此外，Bessie 記得 C 件事，每一件可以用一個(ge) 三元組 (a,b,x) 表示，表示她記得第 b 次擠奶在第 a 次擠奶之後至少 x 天。請幫助 Bessie 計算每次擠奶最早可能的日期。保證 Bessie 沒有記錯；換而言之，存在一種在範圍 1…M 內(nei) 的擠奶時間的安排能夠滿足她的所有記憶。
測試點性質：測試點 2-4 滿足 N,C≤103。測試點 5-10 沒有額外限製。
輸入格式（文件名：timeline.in）：輸入的第一行包含 N、M 和 C。下一行包含 N 個(ge) 空格分隔的整數 S1,S2,…,SN。每個(ge) 數均在範圍 1…M 之內(nei) 。以下 C 行每行包含三個(ge) 整數 a、b 和 x，表示第 b 次擠奶在第 a 次擠奶之後至少 x 天。對於(yu) 每一行，a≠b，a 和 b 在範圍 1…N 內(nei) ，且 x 在範圍 1…M 內(nei) 。
輸出格式（文件名：timeline.out）：輸出 N 行，為(wei) 每次擠奶最早可能的日期。
輸入樣例：4 10 31 2 3 41 2 52 4 23 4 4
輸出樣例：1638第二次擠奶發生在第一次擠奶之後至少五天，所以它不可能發生在第 1+5=6 天前。第四次擠奶發生在第二次擠奶之後至少兩(liang) 天，所以它不可能發生在第 6+2=8 天前。
解析：給定一些如下的不等式，求任意一組不等式的解。ti -tj ≥bSolution：差分約束裸題。首先我們(men) 分析差分約束的本來的式子：ti -tj ≤b左邊的這個(ge) ti -tj 就是差分。我們(men) 首先把這個(ge) 不等式化簡一下，成 ti ≤ tj+bt假設tj已知，我們(men) 可以推出ti的最大值隻可能是tj+b，最小不限。那我們(men) 再次假設如果ti跟 tj'，tj''，tj'''都有關(guan) ，我們(men) 就可以得到三個(ge) 不等式，即一個(ge) 不等式組：
那麽(me) ti滿足所有不等式下的最大值應該是 min{tj'+b，tj''+b，tj''+b}。因為(wei) 要滿足所有不等式，所以必須要取最小值來滿足所有的不等式。注意，我們(men) 上麵提到的 j 都可以模擬成 i的前繼。那麽(me) 我們(men) 可以再次簡化模型。假設有多個(ge) tj 是ti的前繼，那麽(me) 我們(men) 就可以得到一個(ge) 遞推式。ti=min{tj +b}那麽(me) 我們(men) 看一下 SPFA 的遞推式。disti=min{distj +<i，j>}那麽(me) 我們(men) 隻需要找一個(ge) 超級原點super，然後使得他連到 i 的長度是ti即可。最後我們(men) 求一個(ge) 最短路即可，輸出每個(ge) disti 。最後無解的情況隻需要判斷一下負環即可。那麽(me) 我們(men) 看過了tj - ti ≤ b那麽(me) 我們(men) 怎麽(me) 轉化成這一題呢？還是用上麵的思路，就可以得到tj ≥ ti+b然後就可以轉化成上麵推導的模型就可以了 …… 注意 ≥ 和≤ 的性質不同，注意最大值和最小值。這題貌似沒有判負環的地方，注意在執行差分約束造超級原點的時候長度要造為(wei) Si。
Task 2題目：
Bessie 得到了一條一維數軸上的 N 條線段（1≤N≤105）。第 i 條線段包含滿足 li≤x≤ri 的所有實數 x。定義(yi) 一組線段的並為(wei) 所有被至少一條線段所包含的實數 x 的集合。定義(yi) 一組線段的複雜度為(wei) 這組線段的並的連通區域數量。Bessie 想要求出給定的 N 條線段組成的集合的所有 2N 個(ge) 子集的複雜度之和模 109+7 的值。通常你的任務是幫助 Bessie。然而這次，你就是 Bessie，沒人來幫你。請吧！ 測試點性質：測試點 2-3 滿足 N≤16。測試點 4-7 滿足 N≤1000。測試點 8-12 沒有額外限製。
輸入格式（文件名：help.in）：第一行包含 N。以下 N 行每行包含兩(liang) 個(ge) 整數 li 和 ri。保證 li<ri，且所有 li,ri 均為(wei) 1…2N 中的不同整數。
輸出格式（文件名：help.out）：輸出答案模 109+7 的值。
輸入樣例：31 62 34 5
輸出樣例：8所有非空子集的複雜度如下。{[1,6]}⟹ 1,{[2,3]}⟹ 1,{[4,5]}⟹ 1{[1,6],[2,3]}⟹ 1,{[1,6],[4,5]}⟹ 1,{[2,3],[4,5]}⟹ 2{[1,6],[2,3],[4,5]}⟹ 1答案為(wei) 1+1+1+1+1+2+1=8。
解析：先將所有線段按左端點升序排序。fi表示前 i 條線段的所有子集的複雜度之和。如果我們(men) 新添加了一條線段，複雜度會(hui) 怎樣變化呢？不選這條線段。這種情況下，複雜度沒有變化，不包含這條線段的子集的複雜度仍然為(wei) fi。選這條線段。複雜度分兩(liang) 部分：原來的複雜度（這部分不會(hui) 因為(wei) 新選一條線段而減少，因為(wei) 線段已經按左端點排好順序了）和新增加的複雜度（這條線段可能不與(yu) 已有線段形成連通塊）。原來的複雜度仍然為(wei) fi，而選這條線段可能會(hui) 讓部分子集的複雜度 +1。如果之前的線段中有 x 條線段不與(yu) 當前線段相交，則選這 x 條線段的一個(ge) 子集加上當前線段可以讓複雜度在原來子集的複雜度基礎上 +1。根據集合的知識，新增加的複雜度就是 2x 。從(cong) 而得到遞推式：fi=fi-1+(fi-1+2x)=2fi-1+2x 。現在的問題就是計算 x。容易看出，設第 i條線段的左端點為(wei) li，右端點為(wei) ri ，則 x 等於(yu) 右端點小於(yu) ri的線段數量。我們(men) 可以利用前綴和技巧來預處理所有 x 的值。
3
Task 1題目：Farmer John 的農(nong) 場由 N 塊草地（1≤N≤105）和 N−1 條道路組成，滿足每塊草地都能從(cong) 任意其他草地到達。也就是說，這個(ge) 農(nong) 場組成一棵樹。但在與(yu) 不可避免地由樹而生的麻煩的算法問題打了 28 年交道之後，FJ 終於(yu) 認為(wei) 樹形的農(nong) 場太複雜了。他相信在鏈上的算法問題更簡單。所以，他的計劃是將這些道路劃分成若幹條鏈，並將每條鏈交給他值得信任的農(nong) 場工人之一負責。他不關(guan) 心鏈的數量。然而，他希望確保這些鏈都盡可能長，從(cong) 而不會(hui) 有農(nong) 場工人能夠用一個(ge) 漸近效率低下的算法蒙混過關(guan) ！
幫助 Farmer John 求出最大正整數 K，使得道路可以被劃分為(wei) 一些長度至少為(wei) K 的鏈。
測試點性質：在測試點 2-4 中樹組成了一個(ge) “星形”；至多一個(ge) 結點的度大於(yu) 二。測試點 5-8 滿足 N≤103。測試點 9-15 沒有額外限製。
輸入格式（文件名：deleg.in）：第一行包含一個(ge) 整數 N。以下 N−1 行每行包含兩(liang) 個(ge) 空格分隔的整數 a 和 b，表示結點 a 與(yu) b 之間有一條邊。a 和 b 均在範圍 1…N 內(nei) 。
輸出格式（文件名：deleg.out）：輸出 K。
輸入樣例：
8
1 21 31 44 51 66 77 8
輸出樣例：3一種可能的劃分方式如下：2−1−6−7−8,3−1−4−5。解析：給定一棵含有n個(ge) 結點的樹，把它分成若幹條鏈（邊隻能選一次，點可以選多次），使得最短的那條鏈的長度最長是多少。n≤105我們(men) 首先肯定會(hui) 去二分答案L那個(ge) 最長鏈長，關(guan) 鍵是如何判定。我們(men) 這邊利用multiset這個(ge) 東(dong) 東(dong) 來維護，它是什麽(me) 訥？就是一個(ge) 容器，然後加入元素會(hui) 幫你從(cong) 小到大排序，且允許加入重複的元素，且刪增操作是log的。然後我們(men) 就有考慮如何去判定：對於(yu) 一個(ge) 節點u有若幹條從(cong) v連過來的邊，我們(men) 盡量找道兩(liang) 條鏈l1,l2連接使得l1+l2l盡量接近且大於(yu) 等於(yu) L。這個(ge) 還是簡單易懂的。於(yu) 是我們(men) 是兩(liang) 兩(liang) 配對所以u要從(cong) 兒(er) 子節點v連過來並且要有一條邊給自己的父親(qin) 節點fu，那麽(me) 如果從(cong) 兒(er) 子那兒(er) 有奇數條邊那麽(me) 就不管了，如果偶數條邊，我們(men) 強製構造出奇數條邊（即加入一條0邊）。於(yu) 是我們(men) O(nlog2n)做完了這道題目，似乎還可以雙指針優(you) 化到O(nlogn)。
Task 2題目：
Farmer John 的牧場可以被表示為(wei) 一個(ge) N×N 的正方形方陣（1≤N≤300），包含 1≤i,j≤N 內(nei) 的所有位置 (i,j)。對於(yu) 方陣內(nei) 的每個(ge) 方格，如果在這個(ge) 位置上有一頭奶牛，輸入中對應的字符為(wei) '*'，如果這個(ge) 位置沒有奶牛則為(wei) '.'。FJ 相信他的牧場的美麗(li) 程度正比於(yu) 兩(liang) 兩(liang) 距離相等的奶牛三元組的數量。也就是說，她們(men) 組成一個(ge) 等邊三角形。不幸的是，直到最近 FJ 才發現，由於(yu) 他的奶牛都處在整數坐標位置，如果使用歐幾裏得距離進行計算，不可能存在美麗(li) 的奶牛三元組！於(yu) 是，FJ 決(jue) 定改用“曼哈頓”距離。形式化地說，兩(liang) 點 (x0,y0) 和 (x1,y1) 之間的曼哈頓距離等於(yu) |x0−x1|+|y0−y1|。給定表示奶牛位置的方陣，計算等邊三角形的數量。
測試點性質：除了樣例之外有十四個(ge) 測試點，依次滿足 N∈{50,75,100,125,150,175,200,225,250,275,300,300,300,300}。
輸入格式（文件名：triangles.in）：第一行包含一個(ge) 整數 N。對於(yu) 每個(ge) 1≤i≤N，第 i+1 行包含一個(ge) 長為(wei) N 的僅(jin) 由字符 '*' 和 '.' 組成的字符串。第 j 個(ge) 字符描述了是否在位置 (i,j) 存在一頭奶牛。 輸出格式（文件名：triangles.out）：輸出一個(ge) 整數，為(wei) 所求的答案。可以證明答案可以用 32 位有符號整數型存儲(chu) 。
輸入樣例：3*...*.*..
輸出樣例：1有三頭奶牛，並且她們(men) 組成了一個(ge) 等邊三角形，因為(wei) 每對奶牛之間的曼哈頓距離都等於(yu) 二。解析：本題解所涉及知識點僅(jin) 有前綴和。
如上圖，對於(yu) 斜向下45°45°的直線上任意兩(liang) 個(ge) 點（圖中J,K 兩(liang) 點向下做等腰直角t△JHK 並延長JH和KH 做的等腰直角三角形△OHL使△OHL≅△JHK那麽(me) 線段OL上任意一個(ge) 整點(如圖O,N,M,L)與(yu) J,K兩(liang) 點一定形成一個(ge) 曼哈頓等邊三角形證明：首先△OJK 一定是曼哈頓等邊三角形（易證）O每次延OL向下移動一個(ge) 點，它與(yu) J,K的曼哈頓距離不變（橫+1，縱-1）所以線段OL上任意一個(ge) 整點與(yu) J,K兩(liang) 點都可形成曼哈頓等邊三角形上麵的結論非常顯然，我們(men) 可以根據上麵的結論解決(jue) 此題我們(men) 先對每一條斜向下的直線做一個(ge) 前綴和，這樣我們(men) 可以快速計算出一條斜線段上有多少個(ge) *點然後我們(men) 枚舉(ju) 一個(ge) *點（圖中J）和一個(ge) 距離（如圖中線段JH的長）我們(men) 就可以知道其他3個(ge) 點的坐標了（如圖上：K,O,L）如果判斷點（圖中的K）也是*點就用前綴和算出線段（圖中OL）上*點的數量累加答案。但是，明顯我們(men) 要統計的不止斜向下45°這一條直線的一邊上的曼哈頓等邊三角形。所以我們(men) 把整張圖翻轉90°，再做一遍。同理180°和270°也要再做一遍。為(wei) 了避免重複計算，我們(men) 前綴和統計答案時要減去左端點（即f(R)-f(L-1)變為(wei) f(R)-f(L)其實核心思想很簡單，但我好像解釋得太複雜了……時間複雜度O(4∗n 3)
Task 3題目：Bessie 得到了一條一維數軸上的 N 條線段（1≤N≤105）。第 i 條線段包含滿足 li≤x≤ri 的所有實數 x。定義(yi) 一組線段的並為(wei) 所有被至少一條線段所包含的實數 x 的集合。定義(yi) 一組線段的複雜度為(wei) 這組線段的並的連通區域數量的 K 次方（2≤K≤10）。 Bessie 想要求出給定的 N 條線段組成的集合的所有 2N 個(ge) 子集的複雜度之和模 109+7 的值。通常你的任務是幫助 Bessie。然而這次，你就是 Bessie，沒人來幫你。請吧！有 N（2≤N≤2*105）個(ge) 世界，每個(ge) 世界有一個(ge) 傳(chuan) 送門。初始時，世界 i（對於(yu) 1≤i≤N）位於(yu) x 坐標 i，y 坐標 Ai（1≤Ai≤109）。每個(ge) 世界裏還有一頭奶牛。在時刻 0，所有的 y 坐標各不相同，然後這些世界開始墜落：世界 i 沿著 y 軸負方向以 i 單位每秒的速度移動。
在任意時刻，如果兩(liang) 個(ge) 世界在某一時刻 y 坐標相同（可能是非整數時刻），傳(chuan) 送門之間就會(hui) “同步”，使得其中一個(ge) 世界的奶牛可以選擇瞬間傳(chuan) 送到另一個(ge) 世界。對於(yu) 每一個(ge) i，在世界 i 的奶牛想要去往世界 Qi（Qi≠i）。幫助每頭奶牛求出如果她以最優(you) 方案移動需要多少時間。
測試點性質：
測試點 2 滿足 N≤16。
測試點 3-5 滿足 N≤1000, K=2。
測試點 6-8 滿足 N≤1000。
對於(yu) T∈[9,16]，測試點 T 滿足 K=3+(T−9)。
輸入格式（文件名：help.in）：
第一行包含 N 和 K。
以下 N 行每行包含兩(liang) 個(ge) 整數 li 和 ri。保證 li<ri，且所有 li,ri 均為(wei) 1…2N 中的不同整數。
輸出格式（文件名：help.out）：
輸出答案模 109+7 的值。
輸入樣例：
3 2
1 6
2 3
4 5
輸出樣例：
10
所有非空子集的複雜度如下。
{[1,6]}⟹ 1,{[2,3]}⟹ 1,{[4,5]}⟹ 1
{[1,6],[2,3]}⟹ 1,{[1,6],[4,5]}⟹ 1,{[2,3],[4,5]}⟹ 4
{[1,6],[2,3],[4,5]}⟹ 1
答案為(wei) 1+1+1+1+1+4+1=10。
解析：
先考慮 k = 1。考慮DP。首先將所有的線段按照左端點排序，考慮 f[r]表示最右以r結尾的線段集合的連通塊的數量插入一個(ge) 線段[l,r]。對於(yu) 右端點在[1,l-1]的每種情況，都可以使它們(men) 的連通塊加1,再加到f[r]裏麵。對於(yu) 右端點在[l,r]的每種情況，可以直接加到f[r]裏麵，對於(yu) 右端點在[r+1,n]的f[i],要全部*2 (選當前線段或不選)。也就是要一個(ge) 數據結構，支持區間*2,區間求和，顯然線段樹。對於(yu) k != 1, 可以考慮把它的 [0，k]次的結果分別維護，計算的時候用二項式定理合並就好了。就是對於(yu) [1,l-1]的 要把 xk -> (x+1)k再加到f[r]裏，這裏可以用二項式定理把[0,k]次方的結果乘上二項式係數再加起來就好。就是線段樹每個(ge) 點要維護各個(ge) 次方的結果。
【競賽報名/項目谘詢+微信：mollywei007】
評論已經被關(guan) 閉。