hdu Minimum Inversion Number(逆序数的小知识与线段树)
发布日期:2021-08-16 15:55:43 浏览次数:4 分类:技术文章

本文共 2284 字,大约阅读时间需要 7 分钟。

题解

首先,求逆序数对的思路:
1.得到整个数列后,从前往后扫,统计比a[i]小的,在a[i]后面的有多少个
这样做的话,应该是只有n2的暴力作法,没想到更好的方法
2.统计a[i]前面的,且比它大的数
这样做的话,就可以利用输入的时效性,每输入一个数,就把这个数的num[i]值加1,
然后统计比这个数大的数的num和,
因为这里的和一定是在这个数列中比a[i]大,且在它前面出现的数之和,
然后把把这个和加到总逆序数sum里。
这样做的话直接的暴力作法依然是n2,但是,
我们可以在,统计比这个数大的数的num和这一步进行优化,利用线段树求区间域值的复杂度是logn,
所以总体复杂度就降到了nlogn。
 
再来看这道题,求得初始数列的逆序数后,再求其他排列的逆序数有一个规律,就是
sum = sum + (n - 1 - a[i]) - a[i];
这个自行验证吧,相信很容易得出
 
最后,拓展一下,如果要求正序数怎么办?很简单,无非是大小调一下
再问,如果要求满足i<j<k,且a[i]>a[j]>a[k]的数对总数怎么办?
 
可以从中间的这个数入手,统计a[i]>a[j]的对数m,以及a[j]>a[k]的对数n,m*n就是。。。
要求a[i]>a[j]的个数还是一样的,那么a[j]>a[k]的个数呢?
两种思路:
1.得到a[i]>a[j]的对数后,将数列倒过来后再求a[j]<a[k]的对数
2.更简单的做法是,找到规律发现,n = 整个数列中比a[j]小的数 — 在a[j]前面已经出现的比a[j]小的数的个数
即(假设数列是从1开始的) n = (a[j] -1) - (j - 1 - m )
 
如果不理解模拟一边就明白了。
AC代码:
#include 
       
        #include 
        
         using namespace std; #define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 5555;int sum[maxn<<2];void PushUP(int rt) {
         
 sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void build(int l,int r,int rt) {
 sum[rt] = 0;
 if (l == r) return ;
 int m = (l + r) >> 1;
 build(lson);
 build(rson);}void update(int p,int l,int r,int rt) {
 if (l == r) {
 sum[rt] ++;
 return ;
 }
 int m = (l + r) >> 1;
 if (p <= m) update(p , lson);
 else update(p , rson);
 PushUP(rt);}int query(int L,int R,int l,int r,int rt) {
 if (L <= l && r <= R) {
 return sum[rt];
 }
 int m = (l + r) >> 1;
 int ret = 0;
 if (L <= m) ret += query(L , R , lson);
 if (R > m) ret += query(L , R , rson);
 return ret;}int x[maxn];int main() {
 int n;
 while (~scanf("%d",&n)) {
 build(0 , n - 1 , 1);
 int sum = 0;
 for (int i = 0 ; i < n ; i ++) {
  scanf("%d",&x[i]);
  sum += query(x[i] , n - 1 , 0 , n - 1 , 1);
  update(x[i] , 0 , n - 1 , 1);
 }
 int ret = sum;
 for (int i = 0 ; i < n ; i ++) {
  sum += n - x[i] - x[i] - 1;
  ret = min(ret , sum);
 }
 printf("%d\n",ret);
 }
 return 0;}
View Code

 

转载于:https://www.cnblogs.com/shuaihui520/p/9069092.html

转载地址:https://blog.csdn.net/weixin_30810239/article/details/98614275 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:P2161 [SHOI2009]会场预约 (线段树:线段树上的不重复覆盖数)
下一篇:BZOJ2924 [Poi1998]Flat broken lines 【Dilworth定理 + 树状数组】

发表评论

最新留言

路过,博主的博客真漂亮。。
[***.172.111.71]2022年05月22日 08时42分30秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章