光荣的梦想

Problem Description

Prince 对他在这片大陆上维护的秩序感到满意，于是决定启程离开艾泽拉斯。在他动身之前，Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代，平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量，平衡瞬间即被打破。KB决定求助于你，帮助他完成这个梦想。
　　一串数列即表示一个世界的状态。
　　平衡是指这串数列以升序排列。而从一串无序序列到有序序列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。

Input Format

第1行为数列中数的个数n（n <= 100000）

第2行为n个数（绝对值不超过100000）。表示当前数列的状态。

Output Format

输出一个整数，表示最少需要交换几次能达到平衡状态。

Algorithm Design

线段树/排序二叉树/平衡树treap

Problem Analysis

因为有“只能交换相邻两个数字”这个条件，所以交换的总次数是数列中逆序对的个数。证明：在一个数列中，维护一个长度为i的从1到i的单调队列，每次i增长1，推入第i+1个数，为保证单调队列，i要进行当前自身的逆序对个数次交换。以此类推，交换的总次数为数列中逆序对的个数，证毕。

线段树

求解逆序对的方法很多，可以处理前缀和，每次记录前i个数中每个数的个数，数字x的逆序对个数即为1~x-1的所有数个数之和，记录每个数的个数原本为O（n），可以用线段树优化为O（log2n）。因为极限数据下数字个数与数字大小差不多，所以觉得离散化没有必要，但是离散化可以避免负数的情况，值得优化。（虽然不离散化的也可以处理负数并且过了…）

线段树打完错了很多次，因为100000^2是个大整数却没有意识到..

排序二叉树

同理啦。。

Source Code

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 
 4 using namespace std;
 5 
 6 int n,place[100010],num[100010];
 7 ll ans;
 8 
 9 pair <int,int> sortnum[100010];
10 
11 struct node
12 {
13     int l,r,add;
14     ll s;
15 #define l(i) seg_tree[i].l
16 #define r(i) seg_tree[i].r
17 #define s(i) seg_tree[i].s
18 #define add(i) seg_tree[i].add
19 #define lkid sub<<1
20 #define rkid sub<<1|1
21 }seg_tree[400040];
22 
23 void build_tree(int sub,int l,int r)
24 {
25     l(sub)=l;
26     r(sub)=r;
27     s(sub)=0;
28     if(l==r)
29         return ;
30     int mid=(l+r)>>1;
31     build_tree(lkid,l,mid);
32     build_tree(rkid,mid+1,r);
33     return ;
34 }
35 
36 void push_down(int sub)
37 {
38     if(!add(sub))
39         return ;
40     s(lkid)+=add(sub)*(r(lkid)-l(lkid)+1);
41     s(rkid)+=add(sub)*(r(rkid)-l(rkid)+1);
42     add(lkid)+=add(sub);
43     add(rkid)+=add(sub);
44     add(sub)=0;
45 }
46 
47 void change(int sub,int l,int r)
48 {
49     if(l(sub)>r||r(sub)<l)
50         return ;
51     if(l(sub)>=l&&r(sub)<=r)
52     {
53         s(sub)+=r(sub)-l(sub)+1;
54         add(sub)++;
55         return ;
56     }
57     push_down(sub);
58     change(lkid,l,r);
59     change(rkid,l,r);
60     s(sub)=s(lkid)+s(rkid);
61     return ;
62 }
63 
64 int query(int sub,int tar)
65 {
66     if(l(sub)>tar||r(sub)<tar)
67         return 0;
68     if(l(sub)==tar&&r(sub)==tar)
69         return s(sub);
70     push_down(sub);
71     return query(lkid,tar)+query(rkid,tar);
72 }
73 
74 int main()
75 {
76     freopen("dream.in","r",stdin);
77     freopen("dream.out","w",stdout);
78     cin>>n;
79     build_tree(1,1,n);
80     for(int i=1;i<=n;i++)
81     {
82         cin>>num[i];
83         sortnum[i]=make_pair(num[i],i);
84     }
85     sort(sortnum+1,sortnum+n+1);
86     for(int i=1;i<=n;i++)
87         place[sortnum[i].second]=i;
88     for(int i=1;i<=n;i++)
89     {
90         change(1,1,place[i]-1);
91         ans+=query(1,place[i]);
92     }
93     cout<<ans<<endl;
94     return 0;
95 }

线段树

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 
 4 using namespace std;
 5 
 6 int n;
 7 ll ans;
 8 
 9 struct node
10 {
11     ll data;
12     int l,r,sum;
13 }tree[100010];
14 
15 void push_into(int sub)
16 {
17     int cpr=1;
18     while(1)
19     {
20         if(tree[sub].data<tree[cpr].data)
21         {
22             ans+=tree[cpr].sum;
23             if(tree[cpr].l)
24                 cpr=tree[cpr].l;
25             else 
26             {
27                 tree[cpr].l=sub;
28                 tree[sub].sum=1;
29                 return;
30             }
31         }
32         else
33         {
34             tree[cpr].sum++;
35             if(tree[cpr].r)
36                 cpr=tree[cpr].r;
37             else 
38             {
39                 tree[cpr].r=sub;
40                 tree[sub].sum=1;
41                 return;
42             }
43         }    
44     }
45     return;
46 }
47 
48 int main()
49 {
50     freopen("dream.in","r",stdin);
51     freopen("dream.out","w",stdout);
52     cin>>n>>tree[1].data;
53     tree[1].sum=1;
54     for(int i=2;i<=n;i++)
55     {
56         cin>>tree[i].data;
57         push_into(i);
58     }
59     cout<<ans<<endl;
60     return 0;
61 }

二叉排序树

 1 #include <bits/stdc++.h>
 2 
 3 #define MAXN 1000001
 4 
 5 int n;
 6 long long ans;
 7 
 8 int read(){
 9     int f=1;
10     char ch=getchar();
11     while(ch<'0'||ch>'9'){
12         f=(ch=='-')?-1:f;
13         ch=getchar();
14     }
15     int get=0;
16     while(ch>='0'&&ch<='9'){
17         get=(get<<1)+(get<<3)+ch-'0';
18         ch=getchar();
19     }
20     return get;
21 }
22 
23 class treap{
24     private:
25         int tot;
26         class leaf{
27             public:
28                 int size,data,pri,cnt,son[2];
29                 void init(int x,int y){
30                     size=1;
31                     data=x;
32                     pri=y;
33                     cnt=1;
34                 }
35 #define size(i) tree[i].size
36 #define data(i) tree[i].data
37 #define pri(i) tree[i].pri
38 #define cnt(i) tree[i].cnt
39 #define son(i,j) tree[i].son[j]
40         }tree[MAXN];
41         void update(int i){
42             size(i)=size(son(i,0))+size(son(i,1))+cnt(i);
43         }
44         void rotate(int &r,int f){
45             int l=son(r,f);
46             son(r,f)=son(l,!f);
47             son(l,!f)=r;
48             update(r);
49             update(r=l);
50         }
51     public:
52         int root;
53         void insert(int &i,int data,long long &cnt){
54             if(!i){
55                 tree[i=++tot].init(data,rand());
56                 return;
57             }
58             if(data==data(i)){
59                 cnt(i)++;
60                 cnt+=size(son(i,1));
61             }
62             else{
63                 int f=data>data(i);
64                 cnt+=(!f)?size(i)-size(son(i,0)):0;
65                 insert(son(i,f),data,cnt);
66                 if(pri(son(i,f))>pri(i))
67                     rotate(i,f);
68             }
69             update(i);
70         }
71 }tree;
72 
73 int main(){
74     freopen("dream.in","r",stdin);
75     freopen("dream.out","w",stdout);
76     srand(time(NULL));
77     n=read();
78     while(n--){
79         int num=read();
80         tree.insert(tree.root,num,ans);
81     }
82     std::cout<<ans<<std::endl;
83     return 0;
84 }

平衡树treap

over~