P1908 逆序对

归并排序大法好

一般来说，求逆序数的第一反应应该是归并排序（~~难道不是冒泡暴力吗~~

归并的过程就是递归的过程，每次归并都分成左右两部分，无限分，左右两部分经过递归以后回到此处时各自都是排好序的即[l, mid], [mid + 1, r]的部分都是排好序的，但合起来不一点是排好序的

取区间左端点为l, 右端点为r, 然后使用‘双指针’，i 指向 l，j 指向 r，判断数组的值的大小关系，如果tr[i] > tr[j]，则会产生逆序对，由于两部分内部排好序了所以这一个点会产生(j – mid)个逆序对，及时更新ans即可，如果tr[i] <= tr[j]，则不会产生逆序数，继续循环即可

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 500000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll n, ans;
ll tr[MAX];//待排序数组
ll ar[MAX];//辅助数组

void emerge_sort(ll l, ll r){
    if(l == r)return;
    ll mid = (l + r) / 2;
    emerge_sort(l, mid);
    emerge_sort(mid + 1, r);
    ll i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if(tr[i] <= tr[j])ar[k++] = tr[i++];//i指针左移
        else {
            ar[k++] = tr[j++];//j指针右移
            ans += mid - i + 1;//更新ans
        }
    }
    while(i <= mid)ar[k++] = tr[i++];//如果i没移动完就去移动
    while(j <= r)ar[k++] = tr[j++];//j同理
    for(ll i = l; i <= r; ++i)tr[i] = ar[i];//复原ar数组
}

int main(){
    io;
    cin>>n;
    for(int i = 1; i <= n; ++i)cin>>tr[i];
    emerge_sort(1, n);
    cout<<ans<<endl;
    return 0;
}

树状数组

高级一点的做法就是使用树状数组来维护，当然线段树也可以，不过这里的区间查询的起点用的一直是1，所以就写树状数组，（不会吧不会吧不会真的有人愿意调半个小时的线段树吧⁄(⁄ ⁄ ⁄ω⁄ ⁄ ⁄)⁄

首先，数据大小是1e9，这就必然得使用离散化

离散化其实没有听起来那么高大尚，适用于只涉及到数据间的大小关系，而跟数据是多少没有任何关系的情况，而逆序对恰好满足这个条件

我这里离散化还是比较简单的方法，就从小到大排个序，然后按从大到小的顺序给他们从1开始安排值

对于样例

6
5 4 2 6 3 1
离散化后：
4 1 2 5 3 6

我知道你看到这里有亿点点懵，这是什么阴间东西？慢慢看

num:        5 4 2 6 3 1
id:         1 2 3 4 5 6

after sort: 6 5 4 3 2 1
li san hua: 4 1 2 5 3 6

怎么样是不是豁然开朗（bushi

你可能会问离散化以后该怎么求逆序对？？

此时逆序对的个数就等于找所有满足 $tr[i]>tr[j], i>j$ 的值,就是找位置 i 前面的小于tr[i]的数量，然后加起来即可

这就有树状数组的发挥空间了，我们只需要从头开始遍历，对于每个tr[i]，进行两个操作

update(tr[i])在树状数组的树上给 tr[i] 的位置的+1
sum += getans(tr[i] – 1) 更新答案，减1是因为自己不能和自己构成逆序对

然后最后输出sum就可以了

然后喜提wa！！！

只得到了35分，为什么呢？？是不是觉得思路没有问题

其实是因为这个题加强过数据，那65分的数据都是出现了重复的数字，思考一下为什么有重复的数字上面的方法不行，我们来看一下

num:        6 6 6 6 6 6
id:         1 2 3 4 5 6
li san hua: 1 2 3 4 5 6

这样计算下来其实是0 + 1+2+3+4+5 = 15，而非0 + 0 + 0 + 0 + 0 + 0 = 0，这就是因为重复的数字影响了结果

如何解决呢？？

其实只需要在写排序算法的时候将相同的数字，按从高到低的id给出即可

num:        6 6 6 6 6 6
id:         1 2 3 4 5 6
li san hua: 6 5 4 3 2 1

这样就是0+0+0+0+0+0 = 0了，完美解决！

再交一发，你会发现再次喜提wa

好吧，其实得开longlong(╥﹏╥)

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 500000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll n;
struct ran{
    ll id, x;
}tr[MAX];
ll tree[MAX];

bool cmp(ran a, ran b){//排序
    if(a.x != b.x)return a.x > b.x;
    else return a.id > b.id;
}

inline void update(ll i){
    while (i <= n) {
        tree[i] += 1;
        i += lowbit(i);
    }
}

inline int getans(ll i){
    int ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= lowbit(i);
    }
    return ans;
}

int main(){
    io;
    cin>>n;
    for(int i = 1; i <= n; ++i){
        cin>>tr[i].x;
        tr[i].id = i;
    }
    sort(tr + 1, tr + 1 + n, cmp);
    ll sum = 0;
    for(int i = 1; i <= n; ++i){
        sum += getans(tr[i].id - 1);
        update(tr[i].id);
    }
    cout<<sum<<endl;
    return 0;
}

P1908 逆序对

归并排序大法好

树状数组

发送评论 编辑评论

发送评论编辑评论