大家好，欢迎来到IT知识分享网。
逆序对是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。
说人话，就是一个数列中，一个数在你后面，去比你小，则这俩数就是一对逆序对。
怎么做呢？常规的算法是开一个结构体，记录每一个数的值和他在数组中的位置。然后按值从小到大排序。
在开一个标记数组，从1到n循环，对于排好序的数组中的元素i，将其对应的位置i.id标记成1，然后统计一下这个位置后面有多少个1，就是和这个数搭配的逆序对数。
可以这么理解，因为是越小的的数就越先去标记，所以对于一个数 i，比他小的数一定先标记过了，那么在i位置后面的标记一定满足既比他小，位置又比他靠后，不就是逆序对嘛。
而统计在他后面的标记有多少个，就可以用树状数组实现，单点修改，后缀查询。不过习惯是查询前缀，那只要改成从n到1循环就行了（当然从大到小排序也可以）。
不过这还没完，因为要考虑数字相同的情况。
比如1 1 1 1 1，逆序对数是0，但是我们排序的时候没有定义值相同的时候怎么排，是未定义行为，结果就不知道是啥了。
所以要考虑的是，值相同时，是位置靠前的排在前面，还是位置靠后的排在前面。
可以试验一下
若是值靠前的排在前面，那么上述排序结果是1 2 3 4 5，然后从n到1循环。先是a[5]，就vis[5] = 1，统计一下后面，是0；然后a[4]，则vis[4] = 1,统计后面被标记的，发现是1；a[3],vis[3] = 1,ans += 2……这么循环下去，答案就是1 + 2 + 3 + 4= 10,很显然错了。
再试一下位置靠后的排在前面，那么排序结果5 4 3 2 1，从5开始，vis[1] = 1,ans + 0;a[2], vis[2] = 1,ans += 0;a[3], vis[3] = 1,ans += 0……这样下去答案一直就是0了，对了。
所以这么做的话，就应该在值相同的情况下，位置靠后的排在前面。但这却不绝对，只是因为这种写法，若是从大到小循环就不一定了，感兴趣的可以自己试验一下。
给出一种写法
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 #define rep(i ,a, n) for(int i = a; i <= n; ++i) 7 #define per(i, n, a) for(int i = n; i >= a; --i) 8 typedef long long ll; 9 const int maxn = 4e4 + 5; 10 struct Node 11 { 12 int num, id; 13 bool operator < (const Node& other)const 14 { 15 return num < other.num || (num == other.num && id < other.id); 16 } 17 }a[maxn]; 18 int c[maxn], n; 19 int ans = 0; 20 int lowbit(int x) 21 { 22 return x & -x; 23 } 24 void add(int pos, int w) 25 { 26 while(pos <= n) 27 { 28 c[pos] += w; 29 pos += lowbit(pos); 30 } 31 } 32 int sum(int pos) 33 { 34 int ret = 0; 35 while(pos > 0) 36 { 37 ret += c[pos]; 38 pos -= lowbit(pos); 39 } 40 return ret; 41 } 42 int main() 43 { 44 scanf("%d", &n); 45 rep(i, 1, n) {scanf("%d", &a[i].num); a[i].id = i;} 46 sort(a + 1, a + n + 1); 47 per(i, n, 1) 48 { 49 ans += sum(a[i].id); 50 add(a[i].id, 1); 51 } 52 printf("%d\n", ans); 53 return 0; 54 }
上述是一种比较常见的思路，就是按数值大小的顺序插入到对应的位置中。其实也可以按位置的前后插入到对应的大小顺序中。这两种效果相同。
——————————————-18.5.19更新——————————————
这天又做了一道逆序对的题，然后想出了一个更简洁的算法，不用结构体，不用sort。
首先也是要开一个类似于vis[]的数组，vis[x]记录x出现的次数。然后我们从头开始把vis[a[i]]++，这样对于每一次查询a[i]的逆序对，我们只用看位于a[i]后面的已经标记的数有多少个，a[i] + 1的后缀和，因为a[i]后面已经标记的数代表了比a[i]更早出现却比a[i]大的数，就是逆序对的定义嘛。
于是我想用树状数组，但树状数组是求动态前缀和的。于是我就改成了a[i]从后往前插入，这样就把后缀和改成了前缀和。
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 using namespace std; 5 typedef long long ll; 6 const int maxn = 1e5 + 5; 7 int n, a[maxn], c[maxn]; 8 int lowbit(int x) 9 { 10 return x & -x; 11 } 12 void add(int x, int d) 13 { 14 int pos = x; 15 while(pos < maxn) 16 { 17 c[pos] += d; 18 pos += lowbit(pos); 19 } 20 } 21 int sum(int x) 22 { 23 int pos = x, ret = 0; 24 while(pos > 0) 25 { 26 ret += c[pos]; 27 pos -= lowbit(pos); 28 } 29 return ret; 30 } 31 ll ans = 0; 32 int main() 33 { 34 scanf("%d", &n); 35 for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); 36 for(int i = n; i >= 1; --i) 37 { 38 ans += sum(a[i] - 1); 39 add(a[i], 1); 40 } 41 printf("%lld\n", ans); 42 return 0; 43 }
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/30739.html
