Poj2299 Ultra-QuickSort（另附本质不同逆序对）

Description

给定一个长度为 n(n≤5*10^5) 的序列 a，如果只允许进行比较和交换相邻两个数的操作
求至少需要多少次交换才能把 a 从小到大排序。

Input

The input contains several test cases.
Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence.
Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999,
the i-th input sequence element.
Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op,
the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

Sample Output

6
0

线段树大法好！

我一个不会离散化的蒟蒻在wa了6遍后终于学会了看题，然后苦逼的发现了999999999才是真正的数据范围

只好向旁边的大佬请教离散化

没想到还挺简单的，很短：

1 for(int i=1;i<=n;i++)scanf("%d",&x[i].num),x[i].id=i;
2         sort(x+1,x+n+1,cmp);
3         for(int i=1;i<=n;i++)a[x[i].id]=i;

其实就是把原来的数排序，然后按照大小关系安上新的值。

别看此题说的有多玄学，其实就是逆序对

举个例子吧：

1 2 3 4 5 6 7 8是个有序的数列，假如把3和8调换位置

得到1 2 8 4 5 6 7 3，此时逆序对的个数是5，仔细观察是不是只要5步就可以有序

理性的我讲不出，但是你现在是不是可以感性的理解为什么是逆序对的个数了

所以先离散化处理一下，线段树跑一遍逆序对就行了

代码（long long也是坑点）：

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,m,a[500001];
 5 long long ans;
 6 struct o{int num,id;}x[500001];
 7 struct oo{int a,b,v;}s[2000001];
 8 bool cmp(o a,o b)
 9 {
10     return a.num<b.num;
11 }
12 void build(int x,int l,int r)
13 {
14     s[x].a=l,s[x].b=r;s[x].v=0;
15     if(l==r)return ;
16     build(x<<1,l,l+r>>1);
17     build(x<<1|1,(l+r>>1)+1,r);
18 }
19 void change(int x,int y)
20 {
21     s[x].v++;
22     if(s[x].a==s[x].b)return ;
23     int mid=s[x].a+s[x].b>>1;
24     if(y<=mid)change(x<<1,y);
25     else change(x<<1|1,y);
26 }
27 void get(int x,int y)
28 {
29     if(y>s[x].b)return ;
30     if(y<s[x].a)
31     {
32         ans+=s[x].v;
33         return ;
34     }
35     get(x<<1,y);
36     get(x<<1|1,y);
37 }
38 int main()
39 {
40     while(scanf("%d",&n))
41     {
42         if(!n)break;
43         ans=0;
44         build(1,1,500010);
45         for(int i=1;i<=n;i++)scanf("%d",&x[i].num),x[i].id=i;
46         sort(x+1,x+n+1,cmp);
47         for(int i=1;i<=n;i++)a[x[i].id]=i;
48         for(int i=1;i<=n;i++)
49         {
50             change(1,a[i]);
51             get(1,a[i]);
52         }
53         printf("%lld
",ans);
54     }
55 }

被旁边大佬写的树状数组吊锤啊。。呜呜呜！

接下来引进本质不同的逆序对：

Description

给定一个序列a1,a2,…,an，如果存在iaj，那么我们称之为逆序对，求逆序对的数目

Input

第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
N<=10^5。Ai<=10^5

Output

两行，第一行为所有逆序对总数，第二行为本质不同的逆序对总数。

Sample Input

Sample Output

3
1

本质不同的逆序对就是把数列中的多次出现的数都看做只出现了1次（语文被狗吃了），得到的逆序对个数（就是不同的数组成的逆序对个数），希望大家能看懂。

那么怎么处理呢，这个就要考虑离线了（因为你不能知道这个数什么时候首次出现，什么时候最后出现，这样才能确定能以他作为逆序对的范围）

所以我们需要离线处理出来每个数第一次出现位置，和最后一次出现位置

当某个数首次出现把他加入线段树（单点修改），最后一次出现时求出包含该数的逆序对（query）

全部加起来就是答案了

也就是普通的逆序对改一点点

代码如下：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 void read(int &x) {
 7     char ch; bool ok;
 8     for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
 9     for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
10 }
11 struct oo
12 {
13     int a,b,num;
14 }s[400001];
15 int n,m,d[100001],used[100001],f[100001];long long ans,k,sum;
16 void build(int now,int x,int y)
17 {
18     s[now].a=x,s[now].b=y;
19     s[now].num=0;
20     if(x==y)
21         return;
22     else
23     {
24         build(now*2,x,x+y>>1);
25         build(now*2+1,(x+y>>1)+1,y);
26         s[now].num=s[now<<1].num+s[(now<<1)+1].num;
27     }
28 }
29 void change(int now,int x)
30 {
31     s[now].num++;
32     if(s[now].a==s[now].b)return;
33     int mid=s[now].a+s[now].b>>1;
34     if(x>mid)change(now*2+1,x);
35     else change(now*2,x);
36 }
37 void get(int now,int x)
38 {
39     if(s[now].b<x)return ;
40     if(s[now].a>x)
41         ans+=s[now].num;
42     else
43     {
44         if(s[now].a==s[now].b)return ;
45         int mid=s[now].a+s[now].b>>1;
46         get(now*2+1,x);
47         get(now*2,x);
48     }
49 }
50 int main()
51 {
52     read(n);
53     for(int i=1;i<=n;i++)
54     {
55         read(d[i]),m=max(m,d[i]);
56         if(f[d[i]]==0)f[d[i]]=i;
57         used[d[i]]=i;
58     }
59     build(1,0,m);
60     for(int i=1;i<=n;i++)
61     {
62         change(1,d[i]);
63         get(1,d[i]);
64     }
65     printf("%lld
",ans);
66     ans=0;
67     build(1,0,m);
68     for(int i=1;i<=n;i++)
69     {
70         if(f[d[i]]==i)change(1,d[i]);
71         if(used[d[i]]==i)get(1,d[i]);
72     }
73     printf("%lld",ans);
74 }