久違的寫個題解 (?)

題目

題目大意

給你一個序列 $a_1,a_2,\dots,a_n$，一開始 $a_i=i$，接下來有 $q$ 筆操作，每筆操作會把兩個元素交換，在每次操作後輸出序列的逆序數對數量。

• $n \leq 2 \times 10^5$
• $q \leq 5 \times 10^4$

題解

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

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

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

$(t',p',v')$ 的數量，滿足：

• $t' < t \land p' < p \land v' > v_1$，或
• $t' < t \land p' > p \land v' < v_1$

修改後的數量就是把 $v_1$ 換成 $v_2$。

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

如果會同時算到 $(t_2,p,v_2)$ 和 $(t_3,p,v_3)$ 的話，那如果有一個 tuple 是 $(t_3,p,v_2)$，它肯定也會被算到。因此，可以多加一個 tuple $(t_3,p,v_2)$，讓它的權重是 $-1$。

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

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

Code：131468265