久違的寫個題解 (?)
題目
題目大意
給你一個序列 ，一開始 ，接下來有 筆操作，每筆操作會把兩個元素交換，在每次操作後輸出序列的逆序數對數量。
題解
官解是用分塊做，不過我要用 CDQ 分治。
既然要用 CDQ 分治，就是要想辦法把它變成偏序。我們把交換看成兩次單點修改，我們可以把每個數字對應成 ， 是它出現的時間、 是位置、 是數值，一個單點修改就變成新增一個 tuple。
在做一次修改的時候，為了更新答案，我們會想要知道修改前和修改後，和這個位置構成逆序數對的數有多少個，假設現在時間是 、修改位置是 、舊值是 、新值是 ，那麼修改前的數量會是
的數量，滿足：
修改後的數量就是把 換成 。
注意到我們只有記錄每個數字「出現的時間」，而沒有排除掉應該已經消失的數字。要排除掉很簡單，假設你想要算和 構成逆序數對的數量，如果在某個位置 曾經有過兩個數字，它們對應的是 和 ，如果後者比較新的話，我們就要想辦法把 排除掉。
如果會同時算到 和 的話，那如果有一個 tuple 是 ，它肯定也會被算到。因此，可以多加一個 tuple ，讓它的權重是 。
總的來說，當你在時間 要把 改成 時，如果本來這個位置是 ，那麼你會新增兩個 tuple，一個是 ，權重是 ；一個是 ，權重是 。對每個 tuple 計算，所有和它滿足上述條件的 tuple 的權重和它自己權重的乘積總和，這樣一來，權重是 的那個 tuple 算出來的值會是「新的數量」， 的那個就是負的「舊的數量」，兩者相加就是答案變動的值。要算時間 時的答案，就把所有 的 tuple 算出來的值相加即可。
為了方便，我把交換的兩個單點修改拆成是兩個不同時間，一開始的序列我也把它拆成 個時間，詳細就自己看程式碼啦。
Code：131468265