0%

Codeforces 785E 帶修改逆序數對

久違的寫個題解 (?)

題目

題目大意

給你一個序列 ,一開始 ,接下來有 筆操作,每筆操作會把兩個元素交換,在每次操作後輸出序列的逆序數對數量。

題解

官解是用分塊做,不過我要用 CDQ 分治。

既然要用 CDQ 分治,就是要想辦法把它變成偏序。我們把交換看成兩次單點修改,我們可以把每個數字對應成 是它出現的時間、 是位置、 是數值,一個單點修改就變成新增一個 tuple。

在做一次修改的時候,為了更新答案,我們會想要知道修改前和修改後,和這個位置構成逆序數對的數有多少個,假設現在時間是 、修改位置是 、舊值是 、新值是 ,那麼修改前的數量會是

的數量,滿足:

  • ,或

修改後的數量就是把 換成

注意到我們只有記錄每個數字「出現的時間」,而沒有排除掉應該已經消失的數字。要排除掉很簡單,假設你想要算和 構成逆序數對的數量,如果在某個位置 曾經有過兩個數字,它們對應的是 ,如果後者比較新的話,我們就要想辦法把 排除掉。

如果會同時算到 的話,那如果有一個 tuple 是 ,它肯定也會被算到。因此,可以多加一個 tuple ,讓它的權重是

總的來說,當你在時間 要把 改成 時,如果本來這個位置是 ,那麼你會新增兩個 tuple,一個是 ,權重是 ;一個是 ,權重是 。對每個 tuple 計算,所有和它滿足上述條件的 tuple 的權重和它自己權重的乘積總和,這樣一來,權重是 的那個 tuple 算出來的值會是「新的數量」, 的那個就是負的「舊的數量」,兩者相加就是答案變動的值。要算時間 時的答案,就把所有 的 tuple 算出來的值相加即可。

為了方便,我把交換的兩個單點修改拆成是兩個不同時間,一開始的序列我也把它拆成 個時間,詳細就自己看程式碼啦。

Code:131468265