# CSES - Range Queries 題解 ## Static Range Sum Queries [題目連結](https://cses.fi/problemset/task/1646) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆詢問： 在 $[a,\ b]$ 區間的和是多少？ ### 限制條件 * $1\leq n,\ q\leq 2\cdot10^5$ * $1\leq x_i\leq 10^9$ * $1\leq a\leq b\leq n$ ### 想法 利用 [前綴和](https://hackmd.io/@Darren0724/HkNKM6YP9#%E5%89%8D%E7%B6%B4%E5%92%8C) 就可以在 $\mathcal{O}(n+q)$ 完成 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Static-Range-Sum-Queries) ## Static Range Minimum Queries [題目連結](https://cses.fi/problemset/task/1647) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆詢問： 在 $[a,\ b]$ 區間的最小值是多少？ ### 限制條件 * $1\leq n,\ q\leq 2\cdot10^5$ * $1\leq x_i\leq 10^9$ * $1\leq a\leq b\leq n$ ### 想法 跟剛剛的那題很像，用一樣的方法試試看。 仔細一想發現不能這樣做，因為取 min 沒有逆運算。 怎麼辦？ [**RMQ**](https://hackmd.io/@Viecon-342524/BkZiRyumn) :arrow_double_up: 詳見 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Static-Range-Minimum-Queries) ## Dynamic Range Sum Queries [題目連結](https://cses.fi/problemset/task/1648) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆操作，一共有兩種： 1. 把 $x_k$ 的值改成 $u$ 2. 在 $[a,\ b]$ 區間的和是多少？ ### 限制條件 * $1 \le n,\ q \le 2 \cdot 10^5$ * $1 \le x_i,\ u \le 10^9$ * $1 \le k \le n$ * $1 \le a \le b \le n$ ### 想法 用一個可以單點改值的線段樹 / BIT 就結束了 [線段樹](https://hackmd.io/@Viecon-342524/rJCk3sCDT) [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Dynamic-Range-Sum-Queries) ## Dynamic Range Minimum Queries [題目連結](https://cses.fi/problemset/task/1649) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆操作，一共有兩種： 1. 把 $x_k$ 的值改成 $u$ 2. 在 $[a,\ b]$ 區間的最小值是多少？ ### 限制條件 * $1 \le n,\ q \le 2 \cdot 10^5$ * $1 \le x_i,\ u \le 10^9$ * $1 \le k \le n$ * $1 \le a \le b \le n$ ### 想法 用一個可以單點改值的線段樹 就結束了 [線段樹](https://hackmd.io/@Viecon-342524/rJCk3sCDT) [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Dynamic-Range-Minimum-Queries) ## Range Xor Queries [題目連結](https://cses.fi/problemset/task/1650) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆詢問： 在 $[a,\ b]$ 區間的 XOR 和是多少？ ### 限制條件 * $1\leq n,\ q\leq 2\cdot10^5$ * $1\leq x_i\leq 10^9$ * $1\leq a\leq b\leq n$ ### 想法 其實跟第一題一樣，因為 XOR 的逆運算是自己， 所以維護好前綴 XOR 再用一樣的方法就好。 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Range-Xor-Queries) ## Range Update Queries [題目連結](https://cses.fi/problemset/task/1651) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆操作，一共有兩種： 1. 把位在 $[a,\ b]$ 區間的值增加 $u$ 2. 在 $x_k$ 的值是多少？ ### 限制條件 * $1 \le n,\ q \le 2 \cdot 10^5$ * $1 \le x_i,\ u \le 10^9$ * $1 \le k \le n$ * $1 \le a \le b \le n$ ### 想法 用一個可以區間加值的線段樹 就結束了 [線段樹](https://hackmd.io/@Viecon-342524/rJCk3sCDT) [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Range-Update-Queries) ## Forest Queries [題目連結](https://cses.fi/problemset/task/1652) ### 題意 給定一個大小為 $n\times n$ 的網格，每格不是空的就是有一棵樹，左上是 $(1,\ 1)$，右下是 $(n,\ n)$。你的任務是回答 $q$ 筆詢問： 給一個長方形，問這裡面有幾棵樹？ ### 限制條件 * $1\leq n\leq 1000$ * $1\leq q\leq 2\cdot 10^5$ * $1 \le y_1 \le y_2 \le n$ * $1 \le x_1 \le x_2 \le n$ ### 想法 也跟第一題很像，只是現在變成二維的。 假設給的網格是 $M(i,\ j)$，$0$ 代表是空的，$1$ 代表他是樹 定義 $P(i,\ j)$ 為從 $(1,\ 1)$ 到 $(i,\ j)$ 這個長方形的和 稍微畫一下圖就可以發現 $P(i,\ j)=M(i,\ j)+P(i-1,\ j)+P(i,\ j-1)-P(i-1,\ j-1)$ ![image](https://hackmd.io/_uploads/HkzFTdpvp.png) 紅色 = 自己這格 + 藍色 + 綠色 - 重複的 現在處理完 $P$ 了，再來要處理詢問 也是畫圖後發現 如果問的長方形左上是 $(x_0,\ y_0)$，右下是 $(x_1,\ y_1)$ 答案就是 $P(x_1,\ y_1)-P(x_1,\ y_0)-P(x_0,\ y_1)+P(x_0,\ y_0)$ ![image](https://hackmd.io/_uploads/r1Z5R_6v6.png) 紅色 = 紫色 - 藍色 - 綠色 + 重複扣的 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Forest-Queries) ## Hotel Queries [題目連結](https://cses.fi/problemset/task/1143) ### 題意 給定一個長度為 $n$ 的陣列 $h_1,\ h_2,\dots,\ h_n$，你的任務是進行 $m$ 筆操作： 給定 $r_i$ ，找到最左邊且值 $>r_i$ 的位置，並輸出該位置 然後把那個位置的值減少 $r_i$ 如果找不到則輸出 $0$ ### 限制條件 * $1 \le n,\ m \le 2 \cdot 10^5$ * $1 \le h_i \le 10^9$ * $1 \le r_i \le 10^9$ ### 想法 維護最大值並 [**線段樹上二分搜**](https://hackmd.io/@Viecon-342524/B1gcf6UMh#%E7%B7%9A%E6%AE%B5%E6%A8%B9%E4%B8%8A%E4%BA%8C%E5%88%86%E6%90%9C) [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Hotel-Queries) ## List Removals [題目連結](https://cses.fi/problemset/task/1749) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是照給定的順序 $p_1,\ p_2,\dots,\ p_n$（$p_i$ 是指當下的 index 而不是原始陣列的）一個一個把陣列裡的元素刪掉，並回報被刪掉的元素。 ### 限制條件 * $1\leq n\leq 2\cdot10^5$ * $1\leq x_i\leq 10^9$ * $1\leq p_i\leq n-i+1$ ### 想法 最直接的想法就是跟他拚了 [rope](https://hackmd.io/@Viecon-342524/SJ1C2BUE9) 直接拿出來用就好 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#List-Removals) ### 另解 也是線段樹上二分搜 維護一個只有 $0/1$ 的線段樹，並支援單點修改和區間和 一開始全部都是 $1$，代表這個數字還沒被刪掉 每一輪要找第 $p_i$ 的位置，就是找第 $p_i$ 個 $1$ 在哪 所以往下遞迴： * 如果左子樹和 $\ge p_i$： 左子樹有超過 $p_i$ 個 $1$，所以往左邊遞迴 * 如果左子樹和 $\le p_i$： 左子樹沒有 $p_i$ 個 $1$，所以要在右子樹找第 $(p_i -左子樹和)$ 個 $1$ [**AC Code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#List-Removals---%E5%8F%A6%E8%A7%A3) ## Salary Queries [題目連結](https://cses.fi/problemset/task/1144) ### 題意 有間公司有 $n$ 員工，每個員工都有薪水 $p_i$，接下來有 $q$ 筆詢問： 1. 把第 $k$ 個員工的薪水從 $p_k$ 改成 $x$ 2. 回答有幾個員工的薪水位於區間 $[a,\ b]$？ ### 限制條件 * $1 \le n,\ q \le 2 \cdot 10^5$ * $1 \le p_i \le 10^9$ * $1 \le k \le n$ * $1 \le x \le 10^9$ * $1 \le a \le b \le 10^9$ ### 想法 觀察後發現只要有一個支援插入、刪除的 BST，然後用 $a$、$b$ 在上面做二分搜找有幾個數字比他們還小，再把結果相減就能完成題目的任務。 C++ 有沒有已經寫好的 BST 呢？ 答案是有的，就是 set, multiset, map，可是他們沒有辦法做詢問 2 回想起自己在[某個地方](https://hackmd.io/@Viecon-342524/SJ1C2BUE9#pbdstree)看過一個叫 pbds::tree 的東西 直接套一套就好 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Salary-Queries) ### 另解 先把所有數字讀進來之後做離散化 對值域開線段樹，第 $p$ 項代表有幾個員工的薪水 $=p$ 修改就做單點修改 詢問只要求 $[a,\ b]$ 的區間和就好 ## Prefix Sum Queries [題目連結](https://cses.fi/problemset/task/2166) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆操作，一共有兩種： 1. 把 $x_k$ 的值改成 $u$ 2. 在 $[a,\ b]$ 區間的最大前綴和是多少？ ### 限制條件 * $1 \le n,\ q \le 2 \cdot 10^5$ * $-10^9 \le x_i,\ u \le 10^9$ * $1 \le k \le n$ * $1 \le a \le b \le n$ ### 想法 線段樹直接存前綴和 把單點改值想成單點加值，因為是存前綴和，所以從 $k$ 以後的每個位置也都要加值 所以需要一個能區間加值、問最大值的線段樹 [**AC code**](https://cses.fi/paste/63c86d235f89b29332d55c/) ## Pizzeria Queries [題目連結](https://cses.fi/problemset/task/2206) ### 題意 在一條街上有 $n$ 個建築，每個建築都有一間 pizza 店和一間公寓，第 $i$ 間建築的 pizza 價格是 $p_i$，而從第 $j$ 間公寓訂第 $i$ 間 pizza 店的 pizza 要花 $p_i+|j-i|$ 元（要付外送費）。 你要回答進行 $q$ 次操作，共有兩種： 1. 把第 $k$ 間店的價格從 $p_k$ 變成 $x$ 2. 回答從第 $i$ 間公寓訂 pizza 最少要花多少錢？ ### 限制條件 * $1 \le n,\ q \le 2 \cdot 10^5$ * $1 \le p_i,\ x \le 10^9$ * $1 \le k \le n$ ### 想法 既然 $|j-i|$ 是固定的，可以一開始就先加好。 維護單點修改，最小值的線段樹，並把第一項加 $1$、第二項加 $2\dots$ 可是還有另外一個方向，所以我們要開第二顆線段樹，並把第一項加 $n$、第二項加 $n-1\dots$ 問的時候拆成兩邊分開問，分別減掉自己這格預先加的值之後再取最小 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Pizzeria-Queries) ## Subarray Sum Queries [題目連結](https://cses.fi/problemset/task/1190) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是做 $m$ 次操作： 把第 $k$ 項改成 $x$，並在每次操作結束後回答最大子陣列和 ### 限制條件 * $1 \le n,\ m \le 2 \cdot 10^5$ * $-10^9 \le x_i \le 10^9$ * $1 \le k \le n$ * $-10^9 \le x \le 10^9$ ### 想法 直接在線段樹上維護每個區間的最大子陣列和，每次更新完就直接回傳根節點的答案。 再來要想的是怎麼合併？ 維護每個點的前綴最大和、後綴最大和、最大子陣列和、總和 當兩個區間合併 * 最大子陣列和 $=\max(左邊的最大子陣列和,\ 右邊的最大子陣列和,\ 左邊的後綴最大和\ +\ 右邊的前綴最大和)$ * 前綴最大和 $=max(左邊的前綴最大和,\ 左邊的總和\ +\ 右邊的前綴最大和)$ * 後綴最大和 $=max(右邊的後綴最大和,\ 右邊的總和\ +\ 左邊的後綴最大和)$ * 總和 $=左邊的總和\ +\ 右邊的總和$ [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Subarray-Sum-Queries) ## Distinct Values Queries [題目連結](https://cses.fi/problemset/task/1734) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆詢問： 在 $[a,\ b]$ 區間有幾個不同的數字？ ### 限制條件 * $1\leq n,\ q\leq 2\cdot10^5$ * $1\leq x_i\leq 10^9$ * $1\leq a\leq b\leq n$ ### 想法 使用 [莫隊](https://hackmd.io/@Darren0724/B1rsi_DAj#%E8%8E%AB%E9%9A%8A%E7%AE%97%E6%B3%95)。 至於區間移動後更新答案 可以離散化後開一個陣列記錄每種數字出現次數 就解決了 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Distinct-Values-Queries) ### 另解 先將詢問照右界排序 注意到右界相同的區間內的重複數字只有最右邊的那個會對答案造成貢獻 所以開一個可單點修改的區間和線段樹，紀錄可以造成貢獻的位置，陣列左到右掃過去。 開一個 map 紀錄每個數字上次出現的位置，每遇到一個數字就更新 map，也在線段樹上更新，保持在相同數字中只有最右邊那個位置是 $1$，其他都是 $0$。 再來處理詢問 一邊往右更新一邊在線段樹上求區間和就好 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Distinct-Values-Queries---%E5%8F%A6%E8%A7%A3) ## Increasing Array Queries [題目連結](https://cses.fi/problemset/task/2416) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆詢問： 在 $[a,\ b]$ 區間中，每一次操作可以把一個 $x_i$ 變成 $x_i+1$。 如果想要讓這個區間變成遞增的，最少需要幾次操作？ ### 限制條件 * $1\leq n,\ q\leq 2\cdot10^5$ * $1\leq x_i\leq 10^9$ * $1\leq a\leq b\leq n$ ### 想法 想想沒有 query 的情況，高度跟答案之間的關係 ![](https://i.imgur.com/deCkVCx.png) 仔細觀察會發現 query 的答案就是粉紅色的部分 紫色的部分是原陣列，所以只要能把整塊的部分預處理好，就可以回傳答案 再看到整塊的部分，每塊高度會更新的地方是下一個比他高的位置，換句話說，直到碰到下一個比他高的位置之前都是同一個值，可以用單調 Stack 維護下一個比自己高的位置。 ![](https://i.imgur.com/U5zRkcj.png) $p$ 的位置存的是它上面的紅色框框圍住的範圍，$q$ 存的是它上面的紅色框框圍住的範圍 而如果一步一步跳顯然會吃 TLE，所以再套一個倍增就可以一次跳很多步了。 複雜度是預處理 $O(n\log n)$ $+$ 詢問 $O(q\log n)=O((n+q)\log n)$ [**AC Code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Increasing-Array-Queries) ## Forest Queries II [題目連結](https://cses.fi/problemset/task/1739) ### 題意 給定一個大小為 $n\times n$ 的網格，每格不是空的就是有一棵樹，左上是 $(1,\ 1)$，右下是 $(n,\ n)$ 你的任務是回答 $q$ 筆詢問，一共有兩種： 1. 把其中一格的樹拔掉 / 種出來 2. 給一個長方形，問這裡面有幾棵樹？ ### 限制條件 * $1\leq n\leq 1000$ * $1\leq q\leq 2\cdot 10^5$ * $1 \le y_1 \le y_2 \le n$ * $1 \le x_1 \le x_2 \le n$ ### 想法 跟 1 很像，但現在多了修改 試著用樹套樹，這邊選 BIT 套 BIT 如果要問 $(1,\ 1)$ 到 $(i, j)$ 這個長方形的和 找出 $i$ 的前綴在哪幾格，再在這幾格裡面問 $j$ 的前綴的和 要修改也差不多 然後用 1 的方法算出答案 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Forest-Queries-II) ## Range Updates and Sums [題目連結](https://cses.fi/problemset/task/1735) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆操作，一共有三種： 1. 把位在 $[a,\ b]$ 區間的值**增加** $x$ 2. 把位在 $[a,\ b]$ 區間的值**設為** $x$ 3. 回答在 $[a,\ b]$ 區間的和是多少？ ### 限制條件 * $1 \le n,\ q \le 2 \cdot 10^5$ * $1 \le x_i,\ x \le 10^9$ * $1 \le a \le b \le n$ ### 想法 這題超麻煩。 懶標要有兩種：設值和加值 關鍵是要確保一個節點同時只會有一種懶標 往下推設值的時候，要確認底下有沒有加值的懶標，有的話把它歸零。 往下推加值的時候，要確認底下有沒有設值的懶標，有的話直接加在它上面。 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Range-Updates-and-Sums) ## Polynomial Queries [題目連結](https://cses.fi/problemset/task/1736) ### 題意 給定一個長度為 $n$ 的陣列 $x_1,\ x_2,\dots,\ x_n$，你的任務是回答 $q$ 筆操作，一共有兩種： 1. 把位在 $[a,\ b]$ 區間的值增加第一個增加 $1$、第二個增加 $2$、第三個增加 $3 \dots$ 3. 回答在 $[a,\ b]$ 區間的和是多少？ ### 限制條件 * $1 \le n,\ q \le 2 \cdot 10^5$ * $1 \le x_i,\ u \le 10^9$ * $1 \le a \le b \le n$ ### 想法 也是區間加值，但是要稍微改一下懶標的形式 改成一對數字 $(a,\ b)$，代表這個區間的最左邊是 $+a$，最右邊 $+b$ 往下推的時候要注意因為一個懶標他的公差不一定是 $1$（可能兩組以上疊加），所以數字要重算 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Polynomial-Queries) ## Range Queries and Copies [題目連結](https://cses.fi/problemset/task/1737) ### 題意 你的任務是維護一個裝滿陣列的 list，這個 list 一開始只有一個長度為 $n$ 的陣列 $t_1,\ t_2,\dots,\ t_n$，你的任務是回答 $q$ 筆操作，一共有三種： 1. 把第 $k$ 個陣列裡第 $a$ 項改成 $x$ 2. 回答在第 $k$ 個陣列裡 $[a,\ b]$ 區間的和是多少？ 3. 複製第 $k$ 個陣列並把他加到 list 的尾端 ### 限制條件 * $1 \le n,\ q \le 2 \cdot 10^5$ * $1 \le t_i,\ x \le 10^9$ * $1 \le a \le b \le n$ ### 想法 [持久化線段樹](https://hackmd.io/@Viecon-342524/B1gcf6UMh#%E6%8C%81%E4%B9%85%E5%8C%96%E7%B7%9A%E6%AE%B5%E6%A8%B9) 裸題 [**AC code**](https://hackmd.io/HjPZBT57Tkmd9xMzKHLPhA?view#Range-Queries-and-Copies)