北京中學國慶模擬賽 #2

《北京中學國慶模擬賽 #2》這篇在博客園熱度很高，講的正是大家天天碰到的事。下面幫你把要點捋出來，結尾有能直接抄的結論。

T0 sub 待更新。 [代碼示例略] T1 square 題目大意 給定 \(n\) 個軸對齊矩形，第 \(i\) 個矩形爲 \([xa_i, xb_i] \times [ya_i, yb_i]\) 。支持 \(q\) 次操作： Q l r ：詢問 \([l,r]\) 號矩形是否存在公共點。 C l r x y ：將 \([l,r]\) 號矩形整體平移 \((x,y)\) ，即 \(xa,xb\) 都加 \(x\) ， \(ya,yb\) 都加 \(y\) 。 核心思路 一組矩形的交集非空，當且僅當它們 橫座標區間有公共部分 且 縱座標區間有公共部分 。 橫座標區間 \([xa_i, xb_i]\) （ \(i\in[l,r]\) ）有公共部分的充要條件是： \[\max_{i\in[l,r]} xa_i \le \min_{i\in[l,r]} xb_i \] 這是因爲所有區間交起來是 \([\max xa,\ \min xb]\) ，它非空當且僅當左端點 \(\le\) 右端點（等號時它們只在邊界上接觸，仍算有公共點）。縱座標同理： \[\max_{i\in[l,r]} ya_i \le \min_{i\in[l,r]} yb_i \] 於是問題轉化爲：對任意區間 \([l,r]\) ，快速求四個量 \(\max xa,\ \min xb,\ \max ya,\ \min yb\) 。 對於修改 C l r x y ：區間內每個矩形的 \(xa,xb\) 同時加 \(x\) ，所以 \(\max xa\) 和 \(\min xb\) 都加 \(x\) ；同理 \(\max ya,\min yb\) 都加 \(y\) 。這恰好是線段樹的 區間加 。

T0 sub 待更新。 [代碼示例略] T1 square 題目大意 給定 \(n\) 個軸對齊矩形，第 \(i\) 個矩形爲 \([xa_i, xb_i] \times [ya_i, yb_i]\) 。支持 \(q\) 次操作： Q l r ：詢問 \([l,r]\) 號矩形是否存在公共點。 C l r x y ：將 \([l,r]\) 號矩形整體平移 \((x,y)\) ，即 \(xa,xb\) 都加 \(x\) ， \(ya,yb\) 都加 \(y\) 。 核心思路 一組矩形的交集非空，當且僅當它們 橫座標區間有公共部分 且 縱座標區間有公共部分 。 橫座標區間 \([xa_i, xb_i]\) （ \(i\in[l,r]\) ）有公共部分的充要條件是： \[\max_{i\in[l,r]} xa_i \le \min_{i\in[l,r]} xb_i \] 這是因爲所有區間交起來是 \([\max xa,\ \min xb]\) ，它非空當且僅當左端點 \(\le\) 右端點（等號時它們只在邊界上接觸，仍算有公共點）。縱座標同理： \[\max_{i\in[l,r]} ya_i \le \min_{i\in[l,r]} yb_i \] 於是問題轉化爲：對任意區間 \([l,r]\) ，快速求四個量 \(\max xa,\ \min xb,\ \max ya,\ \min yb\) 。 對於修改 C l r x y ：區間內每個矩形的 \(xa,xb\) 同時加 \(x\) ，所以 \(\max xa\) 和 \(\min xb\) 都加 \(x\) ；同理 \(\max ya,\min yb\) 都加 \(y\) 。這恰好是線段樹的 區間加 。 線段樹維護 開兩棵線段樹（橫、縱各一棵），每棵結點存兩個值和懶標記： 橫向樹： \(mx\) 表示區間 \(\max xa\) ， \(mn\) 表示區間 \(\min xb\) ， \(tag\) 爲懶標記。

T0 sub 待更新。 [代碼示例略] T1 square 題目大意 給定 \(n\) 個軸對齊矩形，第 \(i\) 個矩形爲 \([xa_i, xb_i] \times [ya_i, yb_i]\) 。支持 \(q\) 次操作： Q l r ：詢問 \([l,r]\) 號矩形是否存在公共點。 C l r x y ：將 \([l,r]\) 號矩形整體平移 \((x,y)\) ，即 \(xa,xb\) 都加 \(x\) ， \(ya,yb\) 都加 \(y\) 。 核心思路 一組矩形的交集非空，當且僅當它們 橫座標區間有公共部分 且 縱座標區間有公共部分 。 橫座標區間 \([xa_i, xb_i]\) （ \(i\in[l,r]\) ）有公共部分的充要條件是： \[\max_{i\in[l,r]} xa_i \le \min_{i\in[l,r]} xb_i \] 這是因爲所有區間交起來是 \([\max xa,\ \min xb]\) ，它非空當且僅當左端點 \(\le\) 右端點（等號時它們只在邊界上接觸，仍算有公共點）。縱座標同理： \[\max_{i\in[l,r]} ya_i \le \min_{i\in[l,r]} yb_i \] 於是問題轉化爲：對任意區間 \([l,r]\) ，快速求四個量 \(\max xa,\ \min xb,\ \max ya,\ \min yb\) 。 對於修改 C l r x y ：區間內每個矩形的 \(xa,xb\) 同時加 \(x\) ，所以 \(\max xa\) 和 \(\min xb\) 都加 \(x\) ；同理 \(\max ya,\min yb\) 都加 \(y\) 。這恰好是線段樹的 區間加 。 線段樹維護 開兩棵線段樹（橫、縱各一棵），每棵結點存兩個值和懶標記： 橫向樹： \(mx\) 表示區間 \(\max xa\) ， \(mn\) 表示區間 \(\min xb\) ， \(tag\) 爲懶標記。 縱向樹： \(my\) 表示區間 \(\max ya\) ， \(ny\) 表示區間 \(\min yb\) ， \(tag\) 爲懶標記。

T0 sub 待更新。 [代碼示例略] T1 square 題目大意 給定 \(n\) 個軸對齊矩形，第 \(i\) 個矩形爲 \([xa_i, xb_i] \times [ya_i, yb_i]\) 。支持 \(q\) 次操作： Q l r ：詢問 \([l,r]\) 號矩形是否存在公共點。 C l r x y ：將 \([l,r]\) 號矩形整體平移 \((x,y)\) ，即 \(xa,xb\) 都加 \(x\) ， \(ya,yb\) 都加 \(y\) 。 核心思路 一組矩形的交集非空，當且僅當它們 橫座標區間有公共部分 且 縱座標區間有公共部分 。 橫座標區間 \([xa_i, xb_i]\) （ \(i\in[l,r]\) ）有公共部分的充要條件是： \[\max_{i\in[l,r]} xa_i \le \min_{i\in[l,r]} xb_i \] 這是因爲所有區間交起來是 \([\max xa,\ \min xb]\) ，它非空當且僅當左端點 \(\le\) 右端點（等號時它們只在邊界上接觸，仍算有公共點）。縱座標同理： \[\max_{i\in[l,r]} ya_i \le \min_{i\in[l,r]} yb_i \] 於是問題轉化爲：對任意區間 \([l,r]\) ，快速求四個量 \(\max xa,\ \min xb,\ \max ya,\ \min yb\) 。 對於修改 C l r x y ：區間內每個矩形的 \(xa,xb\) 同時加 \(x\) ，所以 \(\max xa\) 和 \(\min xb\) 都加 \(x\) ；同理 \(\max ya,\min yb\) 都加 \(y\) 。這恰好是線段樹的 區間加 。 線段樹維護 開兩棵線段樹（橫、縱各一棵），每棵結點存兩個值和懶標記： 橫向樹： \(mx\) 表示區間 \(\max xa\) ， \(mn\) 表示區間 \(\min xb\) ， \(tag\) 爲懶標記。 縱向樹： \(my\) 表示區間 \(\max ya\) ， \(ny\) 表示區間 \(\min yb\) ， \(tag\) 爲懶標記。 由於同一棵樹裏兩個值共享同一個加法標記，每次區間加只需把 \(mx,mn\) 一起加 \(v\) 。

T0 sub 待更新。 [代碼示例略] T1 square 題目大意 給定 \(n\) 個軸對齊矩形，第 \(i\) 個矩形爲 \([xa_i, xb_i] \times [ya_i, yb_i]\) 。支持 \(q\) 次操作： Q l r ：詢問 \([l,r]\) 號矩形是否存在公共點。 C l r x y ：將 \([l,r]\) 號矩形整體平移 \((x,y)\) ，即 \(xa,xb\) 都加 \(x\) ， \(ya,yb\) 都加 \(y\) 。 核心思路 一組矩形的交集非空，當且僅當它們 橫座標區間有公共部分 且 縱座標區間有公共部分 。 橫座標區間 \([xa_i, xb_i]\) （ \(i\in[l,r]\) ）有公共部分的充要條件是： \[\max_{i\in[l,r]} xa_i \le \min_{i\in[l,r]} xb_i \] 這是因爲所有區間交起來是 \([\max xa,\ \min xb]\) ，它非空當且僅當左端點 \(\le\) 右端點（等號時它們只在邊界上接觸，仍算有公共點）。縱座標同理： \[\max_{i\in[l,r]} ya_i \le \min_{i\in[l,r]} yb_i \] 於是問題轉化爲：對任意區間 \([l,r]\) ，快速求四個量 \(\max xa,\ \min xb,\ \max ya,\ \min yb\) 。 對於修改 C l r x y ：區間內每個矩形的 \(xa,xb\) 同時加 \(x\) ，所以 \(\max xa\) 和 \(\min xb\) 都加 \(x\) ；同理 \(\max ya,\min yb\) 都加 \(y\) 。這恰好是線段樹的 區間加 。 線段樹維護 開兩棵線段樹（橫、縱各一棵），每棵結點存兩個值和懶標記： 橫向樹： \(mx\) 表示區間 \(\max xa\) ， \(mn\) 表示區間 \(\min xb\) ， \(tag\) 爲懶標記。 縱向樹： \(my\) 表示區間 \(\max ya\) ， \(ny\) 表示區間 \(\min yb\) ， \(tag\) 爲懶標記。 由於同一棵樹裏兩個值共享同一個加法標記，每次區間加只需把 \(mx,mn\) 一起加 \(v\) 。 建樹時把 \(xa\) 放進 \(mx\) 、 \(xb\) 放進 \(mn\) （縱向樹放 \(ya,yb\) ），然後按操作執行。

建議先收藏再實操：挑其中一個點今天就試試，跑通了再看下一個。知識只有過手纔是你的，你準備先試哪一點？ 來源｜博客園《北京中學國慶模擬賽 #2》，https://www.cnblogs.com/zhenghaoqi/p/23204041.html