求一个序列的逆序对
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
",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
",ans);
return 0;
}
关于逆序对的DP
考虑(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
",dp[n][k]);
return 0;
}
考虑优化上面的dp,其实dp转移可以写成(egin{aligned}{} f[i][j]=sum_{k=max(0,j-i+1)}^{j}f[i-1][k]end{aligned})，所以我们用前缀和优化dp。
我们开一个变量(egin{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
",dp[n][k]);
return 0;
}
NOIP的逆序对
满分作法：我们发现，当上下两序列中的对应第几大的数在一起时，总和最小。开一个结构体体记录大小和位置，进行排序，这样可以得到两个编号序列，我们定一个序列不动(假设为A)。
记录一个q[b[i]]表示B序列的第i个数的位置应在q[i],此题可知转化为求q数组的逆序对。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxm=1e5+7;
const int mo=99999997;
struct node
{
int id,w;
}a[maxm],b[maxm];
int n;
ll ans=0;
int c[maxm];
int p[maxm];
bool cmp(node a,node b)
{
return a.w<b.w;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int x)
{
for(;x<=n;x+=lowbit(x))
c[x]+=1;
}
int ask(int x)
{
int sum=0;
for(;x;x-=lowbit(x))
sum+=c[x];
return sum;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i].w),a[i].id=i;
for(int i=1;i<=n;i++)
scanf("%d",&b[i].w),b[i].id=i;
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++)
{
p[b[i].id]=a[i].id;
}
for(int i=1;i<=n;i++)
{
ans=(ans+(ask(n)-ask(p[i])+mo)%mo)%mo;
add(p[i]);
}
printf("%lld
",ans);
return 0;
}