诩亢锹蹿题目描述小 D 正在研究交换。小 D 认为一个整数序列是好的当且仅当它先不严格上升后不严格下降。形式化地我们认为序列是好的当且仅当存在某个使得对于任意有且对于任意有。小 D 得到了一个长度为 ?? 的序列他想让这个序列变成好的。小 D 每次可以交换相邻的两个元素。因为交换很累所以小 D 想知道他最少需要交换多少次。这下小 D 不会了请你帮帮他。subtask1(15pts):subtask2(20pts):subtask3(15pts):subtask4(15pts):subtask5(20pts):是一个的排列。subtask6(15pts):无特殊限制。对于 100% 的数据。方法考虑贪心。对于一个序列如果我们要让他变好其最小值一定会被移到最左边或最右边。移到最左边或最右边就取决于移到哪边需要的次数最少。于是我们再考虑分治。每次将对序列中最小的数移到最边上给加上移动次数并将这个数删掉。这样我们就又得到了一个序列。对序列进行这样的重复操作直到个数全部被删除输出即可。但是当我们有很多个并列最小的数时对这些数删除的顺序是有讲究的。每次只能删除最左边或最右边的数否则一定会产生两个相等的数交换位置的情况。这无疑是无意义的会使答案不是最优。并且应删除最左边或最右边中删除所需次数更少的一边。这样才能保证后面被删除的数是最优的。时间复杂度优化观察到最大能达到是肯定卡不过去的。这时候我们便需要优化。我们可以使用平衡树。其实树状数组也可以用又快又好些吹普常数大的没边但我是范浩强吹普死忠粉我就要用。 维护对一个序列分成三段一段为要删的数前的数一段为其自己一段为其后面的数启动次数就是前面的数的和后面的数的取然后再将前后的数合并即将要删掉的数删掉。重复操作即可细节看代码就行。我对我马蜂的美丽程度还是很自信的。代码#includeusing 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;