首页 > 代码库 > 【模板】逆序队（树状数组/归并排序）

【模板】逆序队（树状数组/归并排序）

2024-09-09 22:55:18   208人阅读

P1908 逆序对

题目描述

猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

输入输出格式

输入格式：

第一行，一个数n，表示序列中有n个数。

第二行n个数，表示给定的序列。

输出格式：

给定序列中逆序对的数目。

输入输出样例

输入样例#1：
65 4 2 6 3 1
输出样例#1：
11

说明

对于50%的数据，n≤2500

对于100%的数据，n≤40000。

 

两种写法，上代码。

 

树状数组

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>const int MAXN = 40000 + 10;int data[MAXN];int num[MAXN];struct T{    int rank;    int num;}cnt[MAXN];int n;bool cmp(T a, T b){    return a.num > b.num;}inline int lowbit(int k){    return k & (-1 * k);}inline int ask(int k){    int x = 0;    for(;k;k -= lowbit(k))    {        x += data[k];    }    return x;}inline void modify(int k, int num){    for(;k <= n;k += lowbit(k))    {        data[k] += num;    }}inline int read(){    int x = 0;char ch = getchar();char c = 1;    while(ch > ‘9‘ || ch < ‘0‘) c = ch,ch = getchar();    while(ch >= ‘0‘ && ch <= ‘9‘)x = x * 10 + ch - ‘0‘,ch = getchar();    if(c == ‘-‘) x *= -1;    return x;}inline void wri(int k){    if(k)    {        wri(k/10);        putchar(k%10);    }}inline void wright(int k){    if(k < 0) putchar(‘-‘),wri(-1 *k);    else wri(k);}int ans;int main(){    n = read();    for(int i = 1;i <= n;i ++)    {        cnt[i].num = read();        cnt[i].rank = i;    }    std::sort(cnt + 1, cnt + 1 + n, cmp);    for(int i = 1;i <= n;i ++)    {        num[cnt[i].rank] = i;    }    for(int i = 1;i <= n;i ++)    {        ans += ask(num[i]);        modify(num[i], 1);    }    printf("%d", ans);    return 0;}

 

归并排序

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>inline int read(){    int x = 0;char ch = getchar();char c = ch;    while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();    while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘,ch = getchar();    if(c == ‘-‘)x = x * -1;    return x;}inline void wri(int k){    if(k)    {        wri(k / 10);        putchar(k % 10 + ‘0‘);    }}inline void write(int k){    if(k < 0) putchar(‘-‘),k = -1 * k;    wri(k);}const int MAXN = 1000000 + 10;int n;int data[MAXN];int temp[MAXN];int ans;void merge_sort(int x, int y){    if(y - x < 1)return;    int mid =x + (y - x) / 2;    int p = x,q = mid + 1,i = x;    merge_sort(x, mid);    merge_sort(mid + 1, y);    while(p <= mid || q <= y )    {        if((p <= mid && data[p] <= data[q]) || q > y)temp[i++] = data[p++];        else temp[i++] = data[q++],ans += mid - p + 1;    }    for(int i = x;i<= y;i ++)data[i] = temp[i];}int main(){    n = read();    for(int i = 1;i <= n;i ++)    {        data[i] = read();    }    merge_sort(1, n);    write(ans);    return 0;}

 

 

【模板】逆序队（树状数组/归并排序）


联系
我们