自动搬运

查看原文

来自洛谷，原作者为

	ghostdoglzd rp++

搬运于2025-08-24 22:19:15，当前版本为作者最后更新于2020-10-15 20:01:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题

题意概括：

• 有长为$n$的序列 $a[1...n]$,$\forall a[i](0<i\le n),a[i]\le n$。
• 请你按 $j(j=0,1,2,...,n-1)$ 依次输出把大于 $j$ 的 $a[i]$ 变为 $j$ 后逆序对的个数。

思路：

这是一道很好的思考题，我们可以把 $a[1..n]$ 按从小到大的顺序排序，对于每个 $a[i]$，在原序列中它前面比它大的数的个数即为其对 $j=a[i]+1,a[i]+2,...,n$ 时的答案的贡献。然后从 $0$ 到 $(n-1)$ 枚举 $j$。每次枚举先输出答案，再把答案加上等于 $j$ 的 $a[i]$ 的贡献即可。

这个贡献可以利用树状数组维护区间和把复杂度降为 $O(\log n)$ 。具体实现方式为先往树状数组的每一位上放$1$。然后每遍历到一个 $a[i]$,将它在原序列中的位置对应的树状数组值改为 $0$，其贡献即为它在原序列中的位置前还有多少 $1$，即 $query(num[i]-1)$,（$num[i]$ 为 $a[i]$ 在原序列中的位置）。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
inline int rread(){
	int x=0;
	char c=getchar(),o=' ';
	while(c<'0'||c>'9')o=c,c=getchar();
	while(c>='0'&&c<='9')x*=10,x+=(c^48),c=getchar();
	if(o=='-')x=-x;
	return x;
}
inline int lowbit(int x){
	return x&(-x);
}
struct node{
	int a,num;
}nd[100010];
bool operator <(const node& x,const node& y){
	return (x.a==y.a)?x.num<y.num:x.a<y.a;
}
int n,tree[100010];
inline void change(int x,int c){
	while(x<=n){
		tree[x]+=c;
		x+=lowbit(x);
	}
}
inline int query(int x){
	int ans=0;
	while(x>0){
		ans+=tree[x];
		x-=lowbit(x);
	}
	return ans;
}
signed main(){
	n=rread();
	for(int i=1;i<=n;i++){
		nd[i].a=rread();
		nd[i].num=i;
		change(nd[i].num,1);
	}
	sort(nd+1,nd+1+n);
	int ans=0;
	int in=1;
	for(int i=0;i<n;i++){
		cout<<ans<<'\n';
		int t=in;
		while(i==nd[t].a){
			ans+=query(nd[t].num-1);
			change(nd[t].num,-1);
			t++;
		}
		in=t;
	}
	return 0;
}

更新日志

2020.10.16 修改了链接