#大佬求助#

Skies @ 2020-07-19 11:09:06

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N],c[N];
int n;
int ask(int x)
{
    int ans=0;
    for(;x>0;x-=x&-x)ans+=c[x];
    return ans;
}

void add(int x,int y)
{
    for(;x<=n;x+=x&-x)c[x]+=y;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
//      add(i,1);
    }
    int ans=0;
    for(int i=n;i>0;i--)
    {
        ans+=ask(a[i]-1);
        add(a[i],1);
    }
    cout<<ans;
    return 0;
}

by chen_zhe @ 2020-07-19 11:18:57

@骚气呀 1. 离散化

2. 注意开 long long

by Integricode_26 @ 2020-07-19 11:19:14

给你发个模板吧

#include<stdio.h>
using namespace std;
int a[100001],temp[100001];
void merge(int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid && j<=r) 
    {
        if(a[i]<=a[j]) {
            temp[k]=a[i];
            k++,i++;
        }
        else 
        {
            temp[k]=a[j];
            k++,j++;
        }
    }

    while(i<=mid)
    {
        temp[k]=a[i];
        k++,i++;
    }
    while(j<=r)
    {
        temp[k]=a[j];
        k++,j++;
    }
    for(int i=l;i<=r;++i){
        a[i]=temp[i];
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    merge(1,n);
    for(int i=1;i<=n;++i){
        printf("%d ",a[i]);
    }
    return 0;
}

by __蒟蒻__ @ 2020-07-19 11:20:04

cz!

by Integricode_26 @ 2020-07-19 11:20:18

@chen_zhe 是可以的

by Integricode_26 @ 2020-07-19 11:20:33

不过这题我习惯用归排

by critnos @ 2020-07-19 11:20:51

@陈照然666 az

请问图论怎么做啊/fad

by 奥特战士 @ 2020-07-19 11:21:42

orzorz

by Integricode_26 @ 2020-07-19 11:22:02

我图论有点caiji，只是知道这样做，不过没有归排熟，树状数组我也会

by Integricode_26 @ 2020-07-19 11:22:53

总之方法多，但要注意优化，不然凉凉

by critnos @ 2020-07-19 11:23:22

我孤陋寡闻了。。

求大佬给一个图论求逆序对的博客 orz