逆序对

求一个序列的逆序对

1.树状数组

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxm=5e5+7;
int n;
ll ans;
int a[maxm],book[maxm];
int c[maxm];
int lowbit(int x)
{
 return x&(-x);
}
void add(int x)
{
 for(;x<=n;x+=lowbit(x))
 c[x]++;
}
int ask(int x)
{
 int ans=0;
 for(;x;x-=lowbit(x))
 ans+=c[x];
 return ans;
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 scanf("%d",a+i),book[i]=a[i];
 sort(book+1,book+n+1);
 int l=unique(book+1,book+n+1)-book-1;
 for(int i=1;i<=n;i++)
 {
  a[i]=lower_bound(book+1,book+l+1,a[i])-book;
  ans+=ask(n)-ask(a[i]);
  add(a[i]);
 }
 printf("%lld\n",ans);
 return 0;
}

2.归并排序

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxm=5e5+7;
int n;
ll ans;
int a[maxm],w[maxm];
void gb(int l,int r)
{
 if(l==r) return;
 int mid=(l+r)>>1;
 gb(l,mid);
 gb(mid+1,r);
 int s=l,t=mid+1,k=l;
 while(s<=mid&&t<=r)
 {
   if(a[s]<=a[t])
   {
     w[k]=a[s];
     k++;
     s++;
   }
   else
   {
     w[k]=a[t];
     k++;
     t++;
     ans+=mid-s+1;
   }
 }
 while(s<=mid)
 w[k++]=a[s++];
 while(t<=r)
 w[k++]=a[t++];
 for(int i=l;i<=r;i++)
 a[i]=w[i];
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 scanf("%d",a+i);
 gb(1,n);
 printf("%lld\n",ans);
 return 0;
}

关于逆序对的DP

1.求逆序对

考虑\(dp[i][j]\)表示前\(i\)个数构成的逆序对为\(j\)个的方案数,考虑每次把\(i\)加进来,可以贡献[0,i-1]的逆序对。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int mo=1e4;
int n,k;
int dp[110][11000];
int main()
{
 scanf("%d%d",&n,&k);
 dp[0][0]=1;
 dp[1][0]=1;
 dp[2][0]=1;
 dp[2][1]=1;
 for(int i=3;i<=n;i++)
 {
  for(int j=0;j<=k;j++)
  {
   for(int kk=0;kk<=i-1&&j-kk>=0;kk++)
   dp[i][j]=(dp[i][j]+dp[i-1][j-kk])%mo;
  }
 }
 printf("%d\n",dp[n][k]);
 return 0;
}

2.逆序对数列

考虑优化上面的dp,其实dp转移可以写成\(\begin{aligned}{} f[i][j]=\sum_{k=max(0,j-i+1)}^{j}f[i-1][k]\end{aligned}\)，所以我们用前缀和优化dp。

我们开一个变量\(\begin{aligned}sum=\sum_{k=max(0,j-i+1)}^jf[i][k]\end{aligned}\)，每次让\(f[i][k]=sum\)即可。

但当\(j-i+1>=0\)时要再最后删掉\(dp[i-1][j-i+1]\)的值,因为他不提供贡献。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int mo=1e4;
int n,k;
int dp[1007][1007];
int main()
{
 scanf("%d%d",&n,&k);
 dp[0][0]=1;
 dp[1][0]=1;
 for(int i=2;i<=n;i++)
 {
    int sum=0;
   for(int j=0;j<=k;j++)
   {
     sum=(sum+dp[i-1][j])%mo;
     dp[i][j]=sum;
     if(j-i+1>=0)
     {
        sum=(sum-dp[i-1][j-i+1]+mo)%mo;
     }
   }
 }
 printf("%d\n",dp[n][k]);
 return 0;
}