题目描述
小 D 正在研究交换。
小 D 认为一个整数序列是好的，当且仅当它先（不严格）上升，后（不严格）下降。
形式化地，我们认为序列 (𝑎_1,𝑎_2,...,𝑎_𝑛) 是好的，当且仅当存在某个 (𝑘∈[1,𝑛])，使得对于任意
(1 ≤𝑖 <𝑘)，有 (𝑎_𝑖 ≤𝑎_𝑖+1)，且对于任意 (𝑘≤𝑖<𝑛)，有 (𝑎_𝑖 ge 𝑎_𝑖+1)。
小 D 得到了一个长度为 𝑛 的序列 (𝑎_1,𝑎_2,...,𝑎_𝑛)，他想让这个序列变成好的。
小 D 每次可以交换相邻的两个元素。因为交换很累，所以小 D 想知道，他最少需要交换多少次。
这下小 D 不会了，请你帮帮他。
subtask1(15pts):(𝑛 ≤ 10)；
subtask2(20pts):(𝑛 ≤ 500)；
subtask3(15pts):(𝑛 ≤ 5000)；
subtask4(15pts):(𝑛 ≤ 10^5)；
subtask5(20pts):({𝑎}) 是一个 ([1,𝑛]) 的排列。
subtask6(15pts):无特殊限制。
对于 100% 的数据，(1≤𝑛≤3×10^5，1≤𝑎_𝑖 ≤𝑛)。
方法
考虑贪心。
对于一个序列，如果我们要让他变好，其最小值一定会被移到最左边或最右边。移到最左边或最右边就取决于移到哪边需要的次数最少。
于是，我们再考虑分治。每次将对序列中最小的数移到最边上，给 (ans) 加上移动次数，并将这个数删掉。这样，我们就又得到了一个序列。对序列进行这样的重复操作，直到 (n) 个数全部被删除，输出 (ans) 即可。
但是，当我们有很多个并列最小的数时，对这些数删除的顺序是有讲究的。每次只能删除最左边或最右边的数，否则一定会产生两个相等的数交换位置的情况。这无疑是无意义的，会使答案不是最优。并且，应删除最左边或最右边中删除所需次数更少的一边。这样，才能保证后面被删除的数是最优的。
时间复杂度：(O(n^2))
优化
观察到 (n) 最大能达到 (3×10^5) ，(n ^ 2) 是肯定卡不过去的。这时候我们便需要优化。
我们可以使用平衡树(fhq-treap)。其实树状数组也可以用，又快又好些，吹普常数大的没边，但我是范浩强吹普死忠粉，我就要用。 维护 (treap) 对一个序列分成三段，一段为要删的数前的数，一段为其自己，一段为其后面的数，启动次数就是前面的数的 (size) 和后面的数的 (size) 取 (min)，然后再将前后的数合并，即将要删掉的数删掉。重复操作即可，细节看代码就行。我对我马蜂的美丽程度还是很自信的。
代码
#include <bits/stdc++.h> using namespace std; #define int long long #define usd unsigned #define el cout << 'n' #define lowbit(x) (x & (-x)) const int ranmod = 1e7; #define random ((rand() * rand()) % ranmod) #define AC return #define AK return 0 #define YS cout << "YES" #define NO cout << "NO" #define Ys cout << "Yes" #define No cout << "No" #define ys cout << "yes" #define no cout << "no" #define ls(i) ch[i][0] #define rs(i) ch[i][1] #define debug(num) cerr << #num << ' ' << num << 'n' // void init(); void main_(); signed main() { ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen(".in", "r", stdin); // freopen(".out", "w", stdout); int t = 1; // cin >> t; while(t--) { // init(); main_(); } AK; } const int mod = 95225987, maxn = 3 * 1e5 + 18; int ch[maxn][2], rnd[maxn], val[maxn], siz[maxn], tot, rt; int add(int num) { tot++; ls(tot) = rs(tot) = 0; rnd[tot] = random; siz[tot] = 1; val[tot] = num; return tot; } void push_up(int i) { siz[i] = siz[ls(i)] + siz[rs(i)] + 1; } int merge(int l, int r) { if(l * r == 0) return l + r; int res = 0; if(rnd[l] < rnd[r]) { res = l; rs(l) = merge(rs(l), r); } else { res = r; ls(r) = merge(l, ls(r)); } push_up(res); return res; } void split(int rt, int v, int &l, int &r) { if(rt == 0) {l = 0, r = 0; AC;} if(val[rt] <= v) { l = rt; split(rs(l), v, rs(l), r); push_up(l); } else { r = rt; split(ls(r), v, l, ls(r)); push_up(r); } } int show(int id) { int a, b, mid; split(rt, id, a, b); split(a, id - 1, a, mid); int res = min(siz[a], siz[b]); debug(siz[a]), debug(siz[b]); rt = merge(a, merge(mid, b)); return res; } int del(int id) { int a, b, mid; split(rt, id, a, b); split(a, id - 1, a, mid); int res = min(siz[a], siz[b]); debug(siz[a]), debug(siz[b]); rt = merge(a, b); return res; } int n, ans = 0; map <int, deque <int> > a; void main_() { cin >> n; for(int i = 1; i <= n; i++) { int num; cin >> num; rt = merge(rt, add(i)); a[num].push_back(i); } for(auto tmp : a) { while(!tmp.second.empty()) { if(tmp.second.size() == 1) { ans += del(tmp.second.front()); tmp.second.pop_front(); } else { int l = show(tmp.second.front()), r = show(tmp.second.back()); if(l <= r) { ans += del(tmp.second.front()); tmp.second.pop_front(); } else { ans += del(tmp.second.back()); tmp.second.pop_back(); } } } } cout << ans; el; } 
