自动搬运

查看原文

来自洛谷，原作者为

	suzhikz 我永远喜欢艾莉丝！

搬运于2025-08-24 22:52:21，当前版本为作者最后更新于2025-04-24 20:38:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

感谢喵仔牛奶的数据喵喵喵。

对于这种每次添加一个数的询问，我们先不考虑加数，仅考虑调用一次该函数。

首先，第一次循环会把整个序列中最大的数丢到最前面。

然后第一次操作的交换次数可以暴力计算。

考虑第二次以及后面的所有循环。假设我们现在是第 $i$ 次循环，显然 $1$ 到 $i-1$ 已经按照小到大排序了，然后我们会把 $i$ 前面的每种数和这个位置进行一次交换。这个种类个数我们用树状数组直接维护即可。

那么答案我们就可以 $O(n\log n)$ 快速计算了啊。

接下来考虑加入一个数对答案的影响。

分类讨论下，如果这个数字比前面的最大值小或者等于，那么这个数字只会在最后一个循环用到，然后贡献就是前面的比它大的数的种类个数。

如果这个数字比最大值大。假设现在序列总长度为 $n$。

那么第一次循环这个东西会被交换到最前面。操作次数加一。

然后最后一个数会变成之前的最大值。贡献就是还是一。

然后第 $2$ 到 $n-1$ 次循环需要分类讨论下，如果说 $1$ 到 $n-1$ 最大值只有一个，那么前面 $n-1$ 个数之间的相对大小并没有改变，贡献不会增加。

若最大值有两个以上，假设第二个最大值位置在 $p$，那么发现从 $p$ 到 $n-1$ 中的每个位置，循环到这个位置时，比他大是数字的种类个数会多一个，所以贡献是 $n-p$。

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=1e5+5;
int t,n,a[N],tree[N],cnt[N];
il int lowbit(int x){
	return x&(-x);
}
bool vis[N];
int query(int x){
	int re=0;
	while(x){
		re+=tree[x];x-=lowbit(x);
	}return re;
}
void update(int x,int w){
	if((w==1&&!vis[x])||(w==-1&&vis[x]==1)){
		vis[x]=(w!=-1);
		while(x<=n){
			tree[x]+=w;x+=lowbit(x);
		}
	}
}
int maxx=0;ll ans,ma,po1,po2;
int main(){
	read(t);
	while(t--){
		read(n);for(int i=1;i<=n;i++)read(a[i]);po1=po2=0;
		ans=0;ma=a[1];update(a[1],1);cnt[a[1]]++;
		printf("0");
		for(int i=2;i<=n;i++){
			update(a[i],1);cnt[a[i]]++;
			if(a[i]>ma){
				ans++;ans+=query(n)-query(ma);
				if(po2)
				ans+=i-po2;
				ma=a[i];po1=i;po2=0;
			}else{
				ans+=query(n)-query(a[i]);if(a[i]==ma)if(po2==0)po2=i;
			}
			printf(" %lld",ans);
		}
//		cout<<query(n)<<endl;
		if(t!=0)puts("");
		for(int i=1;i<=n;i++)update(a[i],-1),cnt[i]--;
	}
	return 0;
}