Luogu P1908 逆序对

• 归并排序

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=5e5+5;
int n,a[N],b[N];
LL ans;
void merge(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int x=l,y=mid+1,z=l;
    while(x<=mid&&y<=r)
    {
        if(a[x]>a[y])
        {
            b[z++]=a[y++];
            ans+=mid-x+1;
        }
        else b[z++]=a[x++];
    }
    while(x<=mid) b[z++]=a[x++];
    while(y<=r) b[z++]=a[y++];
    for(int i=l;i<=r;i++) a[i]=b[i];
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    merge(1,n);
    printf("%lld\n",ans);
    return 0;
}

• 树状数组

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=5e5+5;
struct number
{
    int pos,val;
}a[N];
int n,r[N],c[N];
LL ans;
bool cmp(number a,number b)
{
    if(a.val==b.val) return a.pos<b.pos;
    else return a.val<b.val;
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x)
{
    for(;x<=n;x+=lowbit(x)) c[x]++;
    return;
}
int sum(int x)
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=c[x];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        a[i].pos=i;
        scanf("%d",&a[i].val);
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) r[a[i].pos]=i;
    for(int i=1;i<=n;i++)
    {
        add(r[i]);
        ans+=i-sum(r[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

Luogu P5149 会议座位

这道题就是求逆序对，加了一步字符串的转化

• 归并排序

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,b[N],c[N];
char ch[5];
LL ans;
map< string,int > a;
void merge(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int x=l,y=mid+1,z=l;
    while(x<=mid&&y<=r)
    {
        if(b[x]>b[y])
        {
            c[z++]=b[y++];
            ans+=mid-x+1;
        }
        else c[z++]=b[x++];
    }
    while(x<=mid) c[z++]=b[x++];
    while(y<=r) c[z++]=b[y++];
    for(int i=l;i<=r;i++) b[i]=c[i];
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>ch;
        a[ch]=i;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>ch;
        b[i]=a[ch];
    }
    merge(1,n);
    printf("%lld\n",ans);
    return 0;
}

• 树状数组

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#define LL long long
using namespace std;
const int N=1e5+5;
struct meet
{
    int pos,val;
}b[N];
int n,c[N],d[N];
char ch[5];
LL ans;
map< string,int > a;
bool cmp(meet a,meet b)
{
    if(a.val==b.val) return a.pos<b.pos;
    else return a.val<b.val;
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x)
{
    for(;x<=n;x+=lowbit(x)) c[x]++;
    return;
}
int sum(int x)
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=c[x];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>ch;
        a[ch]=i;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>ch;
        b[i].pos=i;
        b[i].val=a[ch];
    }
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++) d[b[i].pos]=i;
    for(int i=1;i<=n;i++)
    {
        add(d[i]);
        ans+=i-sum(d[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

逆序对

原文：https://www.cnblogs.com/Hawking-llfz/p/11468820.html