ABC351

A：

題意

思路：

直接按題意模擬，求出 \(\Sigma A\) 和 \(\Sigma B\) 再相減便是差，因為要獲勝所以再 \(+1\) 即可。
代碼

B:

題意

思路：

直接按照題意 \(N^2\) 枚舉即可。
代碼

C：

題意

思路：

直接按照題意模擬即可。
代碼

D:

請 lrx 講解。

F：

題意

思路：

題意十分簡單，就是求 \(\Sigma_{i=1}^N\Sigma_{j=i+1}^N\max(a_j-a_i,0)\) 直接暴力做是 \(O(N^2)\) 的不可通過。
考慮優化，轉化為對于每一個 \(i,1\leq i\leq N\) 求 \([i+1,N]\) 中大約等于 \(A_i\) 的總和減去 \([i+1,N]\) 中大于等于 \(a_i\) 的個數乘 \(a_i\)。
即：\(\Sigma_{j=i+1}^N S+=[a_j>a_i],\Sigma_{j=i+1}^N s+=[a_j>a_i]*a_j\) 那么結果應該加上 \(s-S\times a_i\)
但是直接做仍然是 \(O(N^2)\) 的，所以可以用權值線段樹進行優化，但是因為 \(a_i\leq 10^8\) 所以直接線段樹行不通，得先離散化后再用權值線段樹實現。
具體的：令權值線段樹上的每一個點 \(i，t_i\) 表示 \(i\) 這個值出現的次數，\(s_i\) 表示 \(t_i\times i\) 那么訪問的時候就可以訪問 \(\Sigma_{rank_i+1}^N\) 的總和了。
權值線段樹的代碼
不難發現可以用平衡樹做，平衡樹的代碼
因為是單點修改，區間查詢，所以可以用權值樹狀數組實現，權值樹狀數組代碼