題目鏈接 \(Click\) \(Here\)

線段樹合并，沒想到學起來意外的很簡單，一般合并權值線段樹。

建樹方法和主席樹一致，即動態開點。合并方法類似于\(FHQ\)的合并，就是把兩棵樹的信息整合到一個里面。暫時沒寫過定義域不同的線段樹合并，具體方法也想象不出來，寫到了再詳細講吧。

算法復雜度：均攤\(O(NlogN)\)，實際空間時間復雜度都不夠穩定，需要謹慎使用。

#include <bits/stdc++.h> using namespace std;const int N = 200010; #define ll long long #define mid ((l + r) >> 1)int n, pos; ll ANS = 0, ans1 = 0, ans2 = 0;struct node{int sumn, ls, rs; }t[N << 5];int cnt = 0; // void update (int &nown, int l, int r) { if (nown == 0) nown = ++cnt;t[nown].sumn++;if (l != r) {if (pos <= mid) {update (t[nown].ls, l, mid);} else {update (t[nown].rs, mid + 1, r);}} } void merge (int &lx, int rx) {if (lx * rx == 0) {lx = lx + rx; return;}t[lx].sumn += t[rx].sumn;ans1 += 1LL * t[t[lx].rs].sumn * t[t[rx].ls].sumn;ans2 += 1LL * t[t[lx].ls].sumn * t[t[rx].rs].sumn;merge (t[lx].ls, t[rx].ls);merge (t[lx].rs, t[rx].rs); }void solve (int &x) {int t, ls, rs; x = 0;cin >> t;if(t == 0) { solve (ls); solve (rs);ans1 = ans2 = 0;merge (x = ls, rs);ANS += min (ans1, ans2);} else {pos = t;update (x, 1, n);} }int main () {cin >> n;int t = 0;solve (t);cout << ANS << endl;return 0; }

轉載于:https://www.cnblogs.com/maomao9173/p/10554898.html

總結

以上是生活随笔為你收集整理的Luogu P3521 [POI2011]ROT-Tree Rotations的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。