关键词：
【Problem description】
Prince 对他在这片大陆上维护的秩序感到满意，于是决定启程离开艾泽拉斯。在他动身之前，Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代，平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量，平衡瞬间即被打破。KB决定求助于你，帮助他完成这个梦想。
一串数列即表示一个世界的状态。
平衡是指这串数列以升序排列。而从一串无序序列到有序序列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。
【Input format】
第1行为数列中数的个数n（n <= 100000）
第2行为n个数（绝对值不超过100000）。表示当前数列的状态。
【Output format】
输出一个整数，表示最少需要交换几次能达到平衡状态。
【Algorithm design】
线段树/排序二叉树
【Problem analysis】
因为有“只能交换相邻两个数字”这个条件，所以交换的总次数是数列中逆序对的个数。证明：在一个数列中，维护一个长度为i的从1到i的单调队列，每次i增长1，推入第i+1个数，为保证单调队列，i要进行当前自身的逆序对个数次交换。以此类推，交换的总次数为数列中逆序对的个数，证毕。
线段树
求解逆序对的方法很多，可以处理前缀和，每次记录前i个数中每个数的个数，数字x的逆序对个数即为1~x-1的所有数个数之和，记录每个数的个数原本为O（n），可以用线段树优化为O（log2n）。因为极限数据下数字个数与数字大小差不多，所以觉得离散化没有必要，但是离散化可以避免负数的情况，值得优化。（虽然不离散化的也可以处理负数并且过了…）
线段树打完错了很多次，因为100000^2是个大整数却没有意识到..
排序二叉树
同理啦。。
【Source code】
线段树（非离散）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,num;
ll ans;
struct node
int l,r,add;
ll s;
#define l(i) seg_tree[i].l
#define r(i) seg_tree[i].r
#define s(i) seg_tree[i].s
#define add(i) seg_tree[i].add
#define lkid sub<<1
#define rkid sub<<1|1
seg_tree[800040];
void build_tree(int sub,int l,int r)
l(sub)=l;
r(sub)=r;
s(sub)=0;
if(l==r)
return ;
int mid=(l+r)>>1;
build_tree(lkid,l,mid);
build_tree(rkid,mid+1,r);
return ;
//建树函数
void push_down(int sub)
if(!add(sub))
return ;
s(lkid)+=add(sub)*(r(lkid)-l(lkid)+1);
s(rkid)+=add(sub)*(r(rkid)-l(rkid)+1);
add(lkid)+=add(sub);
add(rkid)+=add(sub);
add(sub)=0;
//扩散函数
void change(int sub,int l,int r)
if(l(sub)>r||r(sub)<l)
return ;
if(l(sub)>=l&&r(sub)<=r)
s(sub)+=r(sub)-l(sub)+1;
add(sub)++;
return ;
push_down(sub);
change(lkid,l,r);
change(rkid,l,r);
s(sub)=s(lkid)+s(rkid);
return ;
//修改区间
void query(int sub,int tar)
if(l(sub)>tar||r(sub)<tar)
return ;
if(l(sub)==tar&&r(sub)==tar)
ans+=s(sub);
return ;
push_down(sub);
query(lkid,tar);
query(rkid,tar);
s(sub)=s(lkid)+s(rkid);
return ;
//查找单点
int main()
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
cin>>n;
build_tree(1,1,200010);
for(int i=1;i<=n;i++)
cin>>num;
num+=100001;
change(1,1,num-1);
query(1,num);
//加上100000防止负数
cout<<ans<<endl;
return 0;
线段树（离散）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,place[100010],num[100010];
ll ans;
pair <int,int> sortnum[100010];
struct node
int l,r,add;
ll s;
#define l(i) seg_tree[i].l
#define r(i) seg_tree[i].r
#define s(i) seg_tree[i].s
#define add(i) seg_tree[i].add
#define lkid sub<<1
#define rkid sub<<1|1
seg_tree[400040];
void build_tree(int sub,int l,int r)
l(sub)=l;
r(sub)=r;
s(sub)=0;
if(l==r)
return ;
int mid=(l+r)>>1;
build_tree(lkid,l,mid);
build_tree(rkid,mid+1,r);
return ;
//建树函数
void push_down(int sub)
if(!add(sub))
return ;
s(lkid)+=add(sub)*(r(lkid)-l(lkid)+1);
s(rkid)+=add(sub)*(r(rkid)-l(rkid)+1);
add(lkid)+=add(sub);
add(rkid)+=add(sub);
add(sub)=0;
//标记下传函数
void change(int sub,int l,int r)
if(l(sub)>r||r(sub)<l)
return ;
if(l(sub)>=l&&r(sub)<=r)
s(sub)+=r(sub)-l(sub)+1;
add(sub)++;
return ;
push_down(sub);
change(lkid,l,r);
change(rkid,l,r);
s(sub)=s(lkid)+s(rkid);
return ;
//修改函数
int query(int sub,int tar)
if(l(sub)>tar||r(sub)<tar)
return 0;
if(l(sub)==tar&&r(sub)==tar)
return s(sub);
push_down(sub);
return query(lkid,tar)+query(rkid,tar);
//查找函数
int main()
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
cin>>n;
build_tree(1,1,n);
for(int i=1;i<=n;i++)
cin>>num[i];
sortnum[i]=make_pair(num[i],i);
sort(sortnum+1,sortnum+n+1);
for(int i=1;i<=n;i++)
place[sortnum[i].second]=i;
//找到编号为i的数在升序中的位置
for(int i=1;i<=n;i++)
change(1,1,place[i]-1);
ans+=query(1,place[i]);
//加上逆序对个数
cout<<ans<<endl;
return 0;
排序二叉树：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll ans;
struct node
ll data;
int l,r,sum;
tree[100010];
void push_into(int sub)
int cpr=1;
while(1)
if(tree[sub].data<tree[cpr].data)
ans+=tree[cpr].sum;
if(tree[cpr].l)
cpr=tree[cpr].l;
else
tree[cpr].l=sub;
tree[sub].sum=1;
return;
else
tree[cpr].sum++;
if(tree[cpr].r)
cpr=tree[cpr].r;
else
tree[cpr].r=sub;
tree[sub].sum=1;
return;
return;
int main()
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
cin>>n>>tree[1].data;
tree[1].sum=1;
for(int i=2;i<=n;i++)
cin>>tree[i].data;
push_into(i);
cout<<ans<<endl;
return 0;
测试工程师的光荣与梦想
天地不仁，以万物为刍狗。圣人不仁，以百姓为刍狗。－《老子》正式开始之前，插个无耻的广告，推荐小伙伴们读读彼得.德鲁克和杰克.韦尔奇的书籍，开卷有益，尤其是身处管理岗位的小伙伴们，也许会有常读常新的感触哦... 查看详情
测试工程师的光荣与梦想
业精于勤而荒于嬉，行成于思而毁于随。——韩愈如果你讨厌长文的话，请忽略所有，直接前往最后一段，那是我最想说的话。如果你对测试人员的地位问题比较感兴趣，不妨细细读来。笔者在不同的公司都遇到过同一个... 查看详情
测试工程师的光荣与梦想
水之积也不厚，则其负大舟也无力。－庄子前两篇主要谈了谈测试的成长与瓶颈，并未涉及到测试工作本身的内容，从本篇起，笔者将与大家就测试的实际工作内容与大家一起交流与探讨。测试的实际工作千差万别，各个细分领... 查看详情
游戏测试工程师的光荣与梦想－百炼成钢
（一）百炼成钢天行健，君子以自强不息；地势坤，君子以厚德载物。－《周易》前言开篇名义：做测试的这么多，能形成自己测试体系的有几个？现在整个测试行业可谓欣欣向荣，从业人员在不断增多，各种新技术，新思维也... 查看详情
惠斯通电桥：一段光荣（或者不那么光荣）历史(代码片段)
闪电的驯服者：电学的历史WheatstoneBridge:A(NotSo)HonorableHistory 01惠斯通桥一、前言 欧姆定律为什么变得众所周知起来，部分原因和查尔斯·惠斯通有关系。惠斯通在其论文中描写了欧姆定律是如何帮助他在1843年设计了... 查看详情
他89岁，拿下人生第3个博士学位，横跨医学物理学，只为“实现儿时梦想”
...一种怎样的体验？还是在医学职涯已功成名就，光荣退休之后。最近，新晋物理学博士弗雷德·斯坦纳老爷子凭借自己的传奇经历，在社交网络上引发热议。事实上，这个物理学博士已经是他拿到的第3个博士... 查看详情
互联网架构介绍--from光荣之路
互联网架构介绍：1最初是前端一个web加一个DB的结构 这种结构，web容易挂掉，业务就会终止，由于高可用的需求，出现了下面这样的架构、2加了一个web，两个web之间是主备的关系，一个挂了，另一个来代替，用来解决... 查看详情
转载-有雷一起扛！关于研发流程的制定from光荣之路
背景对于研发人员来说，研发流程的重要性想必每个研发人员都很了解，但是如果在项目初期没有明确制定好研发流程，可以想象后期的工作开展是多么不易。我曾经被借调过到一个项目组，该组从项目的初期就没有一个明确的... 查看详情
新中国首位mit计算机博士高光荣教授逝世，美团创始人王兴曾是他的学生
...与计算机工程系终身教授、数据流体系结构的先驱人物高光荣逝世，享年76岁。高光荣先生于1945年出生，1968年获得清华大学电气工程学士学位，1980年在华中科大读研期间出国学习，于1982年获美 查看详情
高光荣教授逝世：他是新中国首位mit计算机博士，开创数据流体系结构
...息：著名计算机科学家、美国特拉华大学终身教授高光荣已与世长辞，享年76岁。高光荣是中华人民共和国第一位获得麻省理工学院计算机博士学位的学者，毕生致力于数据流架构领域研究，是该领域的奠基者与... 查看详情
关于梦想
...，当我们走进这个纷繁的世界时，心中都藏着一个美好的梦想。为了这个梦想，我们立下坚定的信念，我们有着不屈的意志和不懈的努力。 当我们走上自己的梦想之路时，我们发现自己的梦想之路又是那么的艰难，那么的遥远... 查看详情
你有梦想吗？华为云学院助你实现梦想
明天便是世界梦想日，问问自己：我有梦想吗？我最想实现的梦想是什么？作为这个世界小小的一员，想要努力提升自我，在这个世界发光发亮，却不知道何去何从？实现梦想，要忠于内心，持续坚持，在通向梦想的路上，或许... 查看详情
场景编程集锦-吉米的总统梦想(代码片段)
...景描述 吉米是太平洋岛国一个贫苦家庭的孩子，他的梦想就是当总统，引领国家走向富强之路。 开学的第一堂课上，老师用白色的粉笔在黑板上写下了“我的梦想”，同学们都陷入了思考。大卫的梦想是当一名科学家，... 查看详情
梦想之源
...博文的冲动，是因为，来到北京才发现，在大都市，拥有梦想的人太多，太多，有能力的人也有太多太多。可是又有几个人能够遵循自己最初的梦想前进着，实现自己最初的渴望呢，现在即将要毕业的我，也是满怀梦想与期待想... 查看详情
人生最精彩的不是实现梦想的瞬间，而是坚持梦想的过程
更新一下今天的学习进度：以后每天都会更新，倘若有啥感悟想说的话也会一起发出来，希望更多的人能和我一起坚持下去： 1.每天背诵50个英文单词，复习巩固了55个单词,进度： 2246/3486 2.《王者归来》两个... 查看详情
坚持梦想，让每一个梦想都开花
...是一名演员，像奥黛丽赫本一样。妈妈告诉我，你的三个梦想都会实现。我从小就是不受老师待见的调皮姑娘，小学时可以说是受尽老师折辱。最后到了我妈不给老师送购物卡她就不评我三好的 查看详情
在追寻梦想的路上，我们都一样
在追寻梦想的路上，我们都一样在追寻梦想的路上，我们都一样，一样迷茫，一样孤独，一样焦虑，一样困惑。可是，好在那些经历过得曲折都成为酝酿梦想的能量和养分，最终我们都找到了属于自己的梦想，并且还在为之继续... 查看详情
51cto博客旧版首页截图纪念
...期服役，将告别历史舞台，但它也承载了我们很多作者的光荣与梦想、承载了我们很多阅读的时光。特将旧版首页截图保存，以作留念。650)this.width=650;"src="https://s4.51cto.com/wyfs02/M00/9B/95/wKioL1lkqErA4SUxAARe 查看详情