【模板】——求序列逆序对数

Love The Way You Lie 2022-09-01 14:45 102阅读 0赞

## 用归并排序 ##

ll MergeSort(int s[], int left, int middle, int right)
    { 
    	int i = left, j = middle;
    	int b[right - left + 1];
    	int index = 0;
    	ll sum = 0;
    	int t = 0;
    	while (i < middle && j <= right)
    	{ 
    		if (s[i] > s[j])
    		{ 
    			b[index++] = s[j++];
    			t++;
    		}
    		if (s[i] <= s[j] || j == right + 1)
    		{ 
    			sum +=(ll) t * (middle - i);
    			b[index++] = s[i++];
    			t = 0;
    		}
    	}
    	while (i < middle)
    	b[index++] = s[i++];
    	while (j <= right)
    	b[index++] = s[j++];
    	
    	index = 0;
    	for (int m = left; m <= right; m++)
    	s[m] = b[index++];
    	return sum ;
    }
    ll k = 0;
    void Merge(int s[], int low, int high)
    { 
    	if (low < high)
    	{ 
    		int mid = (low + high) / 2;
    		Merge(s, low, mid);
    		Merge(s, mid + 1, high);
    		k += MergeSort(s, low, mid + 1, high);
    	}
    }

## 用树状数组 ##

int a[maxn],tree[4*maxn];
    void update(int x) { 
        for(; x<=n; x+=-x&x)
            tree[x]++;
    }
    int sum(int x) { 
        int acc=0;
        for(; x; x-=x&-x)
            acc+=tree[x];
        return acc;
    }
    for(int i=1; i<=n; i++) { 
            ans+=i-1-sum(a[i]);
            update(a[i]);
        }
    return ans;

发表评论取消回复

表情：

评论列表（有 0 条评论，102人围观）

还没有评论，来说两句吧...

相关阅读

相关计算逆序对数

计算逆序对数数学术语逆序对，数学术语，设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i

冷不防/ 2024年03月31日 13:11/ 0 赞/ 30 阅读

相关【模板】——求序列逆序对数

用归并排序 ll MergeSort(int s[], int left, int middle, int right) { int i =

Love The Way You Lie/ 2022年09月01日 14:45/ 0 赞/ 103 阅读

相关归并排序求逆序数模板

<pre name="code" class="cpp">include <stdio.h> define N 1500 int num;

痛定思痛。/ 2022年08月14日 00:50/ 0 赞/ 151 阅读

相关【日常学习】【归并逆序对】codevs1688 求逆序对题解

题目描述 Description 给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目数据范围：N<=105。Ai<

曾经终败给现在/ 2022年08月09日 12:48/ 0 赞/ 152 阅读

相关利用归并排序求逆序对

在逆序对的问题中，如果采用暴力求解的方法，一般也是有效的，但是O(n2)时间复杂度实在是难以接受的。但是对于逆序对问题，却有一个看似不想关的算法来解决–归并排序。时间复杂度和空

以你之姓@/ 2022年08月04日 15:40/ 0 赞/ 154 阅读

相关采用归并排序思想解决逆序对数问题

//归并排序解逆序对数问题 public class MergeSort { static int count=0; publi

秒速五厘米/ 2022年06月18日 11:20/ 0 赞/ 141 阅读

相关 Ultra-QuickSort 求最小交换次数即求逆序对数树状数组+离散化

首先介绍一下树状数组树状数组(binary indexed tree)，是一种设计新颖的数组结构，它能够高效地获取数组中连续n个数的和。概括说，树状数组通常用于解决以下问题

素颜马尾好姑娘i/ 2022年06月13日 08:45/ 0 赞/ 193 阅读

相关 HDU 4911 Inversion（求逆序对）

bobo has a sequence a 1,a 2,…,a n. He is allowed to swap two adjacent numbers for no mor

逃离我推掉我的手/ 2022年06月09日 08:43/ 0 赞/ 122 阅读

相关树状数组求逆序数模板

以前求逆序数都是用的归并排序，现在发现树状数组求逆序数更简单，常数更小，留个板子，数值较大时需要离散化，用map实更简单，入门参考[https://www.cnblogs.c

忘是亡心i/ 2022年05月15日 18:56/ 0 赞/ 202 阅读

相关逆序对数-剑指offer-Java

题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007

我会带着你远行/ 2021年12月03日 22:47/ 0 赞/ 216 阅读