qoj14458. 調(diào)色濾鏡

平面 \([1,10^9]\times[1,10^9]\) 上有 \(n\) 個(gè)點(diǎn)，點(diǎn) \(i\) 位于 \((x,y)\)，有顏色 \(c_i\in [0,9]\)。

有 \(q\) 次操作，每次對(duì)平面上一個(gè)矩形范圍內(nèi)的點(diǎn)的顏色作用映射 \(f:[0,9]\rightarrow[0,9]\)。

保證矩形兩兩之間要么包含要么不交。

要求求出每個(gè)點(diǎn)在 \(q\) 次操作后的顏色。

首先由于矩形之間兩兩不交，不難發(fā)現(xiàn)他們之間的包含構(gòu)成了一個(gè)森林的結(jié)構(gòu)。

我們加入第 \(q+1\) 操作，覆蓋整個(gè)平面，\(f=x\rightarrow x\)。顯然不影響答案。

那么這時(shí)就構(gòu)成了一顆以 \(q+1\) 為根的樹。

那么怎么建樹呢？具體來(lái)說(shuō)，我們掃描線。

在一個(gè) set 中維護(hù)當(dāng)前截面上的所有矩形的上下邊界。

當(dāng)我們遇到一個(gè)矩形 \(i\) 的左邊界時(shí)，我們查詢其上邊界的后繼，設(shè)其為矩形 \(j\) 的邊 \(j'\)。

• 假如 \(j'\) 是一個(gè)上邊界，那么 \(j\) 就是 \(i\) 的父親。
• 假如 \(j'\) 是一個(gè)下邊界，那么 \(j\) 就是 \(i\) 的兄弟，意味著 \(j\) 的父親是 \(i\) 的父親。

類似地，當(dāng)我們遇到一個(gè)點(diǎn) \(i\)，我們查詢 \(y_i\) 的后繼 \(j'\)。

• 假如它是 \(j\) 的上邊界，那么點(diǎn) \(i\) 位于矩形 \(j\) 內(nèi)。
• 假如它是 \(j\) 的下邊界，那么點(diǎn) \(i\) 位于矩陣 \(j\) 的父親內(nèi)。

假如一個(gè)點(diǎn) \(i\) 位于矩形 \(j\) 內(nèi)，說(shuō)明有且僅有 \(j\) 的祖先對(duì) \(i\) 產(chǎn)生影響。

我們對(duì)生成的整棵樹進(jìn)行 dfs，那么通過 dfs 到一個(gè)點(diǎn)時(shí)所有操作的映射復(fù)合，我們可以 \(O(1)\) 地確定答案。

矩形的 dfn 序不一定等于插入順序，所以這實(shí)際上要求一個(gè)支持從中間插入刪除的數(shù)據(jù)結(jié)構(gòu)維護(hù)映射復(fù)合。那么線段樹就可以完成這樣的操作。

總時(shí)間復(fù)雜度 \(O(nd\log n+q\log n)\)，其中 \(d=10\)。

code