2022 年牛客多校第七场 E 题题解

E 题题意：给定 $n$ 个互不相同的数字和一个初始为空的序列 ${a}$ ，依次将其插入到序列的末尾，问至少经过几次相邻交换操作可以让序列符合三分特性（单峰）。 $n \leq 2\times 10^5$ ，对每次插入输出答案。

解法：首先离散化。考虑最终的形态为一高-低-高形态（一个最低值），因而一个数字所处的位置有最低值左侧（L）和最低值右侧（R）两种。统计最终的交换次数等价于统计与一个数字有关的逆序对（或顺序对）数目，取决于所在的位置。

若当前新加入的数字 $a_{i}$ 在 L 侧，其贡献是确定的——它在原序列的左侧，所有比 $a_{i}$ 小的数字个数（不分 L，R 侧）。这是因为无论波谷在哪里，它处于左侧是一定得要移动到所有比它小数字的左侧。若当前数字 $a_{i}$ 在 R 侧，则会随着后续数字的增加而发生改变——当前同时处于 R 侧且比它大的，并且在原序列中在 $i$ 前面的数字个数。显然它只需要和 R 侧的数字进行交换而不涉及 L 侧的数字。 $a_{i}$ 对于总答案的贡献，为处于 L 侧答案与处于 R 侧答案的更小值。显然容易注意到， $a_{i}$ 在 L 侧的答案是固定的，但是在 R 侧的答案会不断增加。

此时考虑加入一个数字，在刚加入这个数字时默认这个数字放在 R 侧。维护两个树状数组 T1，T2 和一个线段树 T，分别维护之前所有的数字（方便查询当前数字 L 侧的答案），在 R 侧的数字（方便查询当前数字在 R 侧的答案），以及一个线段树维护已经有过的数字的 L 侧答案减去 R 侧答案的线段树，以方便统计总答案。考虑加入 $a_{i}$ 后会对这几个树产生什么影响：

T1，T2 更新。
线段树上所有下标大于等于 $a_{i}$ 的 L-R 值减少 $1$ ——由于 $a_{i}$ 的加入使得这部分的 R 侧答案增加了 $1$ 。
若线段树上有 L-R 的值小于等于 $0$ 的下标，证明当前的这个值应当从 R 侧移动到 L 侧，对 T2 和线段树进行更改。

因而可以不用关心具体波谷位置，快速的转移出当前的答案。最后只需要再将全部的值进行翻转—— $a_i \leftarrow n-a_i+1$ 即可得到低-高-低形态的答案，二者取 min 即可。总时间复杂度 $\mathcal O(n \log n)$ 。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+3,inf=1e9;
int n,a[N],b[N];
LL ans[N];
vector<int>res;
IL int in(){
	char c;int f=1;
	while((c=getchar())<'0'||c>'9')
	  if(c=='-') f=-1;
	int x=c-'0';
	while((c=getchar())>='0'&&c<='9')
	  x=x*10+c-'0';
	return x*f;
}
struct segment{
	#define ls k<<1
	#define rs k<<1|1
	int mn[N<<2],add[N<<2];
	IL void pushup(int k){mn[k]=min(mn[ls],mn[rs]);}
	IL void Add(int k,int x){mn[k]+=x,add[k]+=x;}
	IL void pushdown(int k){
		if(add[k]) Add(ls,add[k]),Add(rs,add[k]),add[k]=0;
	}
	void build(int k,int l,int r){
		if(l==r){add[k]=0,mn[k]=inf;return;}
		int mid=l+r>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		add[k]=0,pushup(k);
	}
	void moadd(int k,int l,int r,int ll,int rr,int v){
		if(l>=ll&&r<=rr) return Add(k,v);
		int mid=l+r>>1;
		pushdown(k);
		if(ll<=mid) moadd(ls,l,mid,ll,rr,v);
		if(rr>mid) moadd(rs,mid+1,r,ll,rr,v); 
		pushup(k);
	}
	void find(int k,int l,int r){
		if(mn[k]) return;
		if(l==r) return res.pb(l),void();
		pushdown(k);
		int mid=l+r>>1;
		find(ls,l,mid),find(rs,mid+1,r);
	}
	void modify(int k,int l,int r,int u,int v){
		if(l==r) return mn[k]=v,void();
		int mid=l+r>>1;
		pushdown(k);
		u<=mid?modify(ls,l,mid,u,v):modify(rs,mid+1,r,u,v);
		pushup(k);
	}
}T;
struct BIT{
	int c[N];
	IL void clear(){memset(c,0,sizeof(c));}
	IL int lb(int x){return x&-x;}
	IL void add(int y,int x){
		for(;y<=n;y+=lb(y)) c[y]+=x;
	}
	IL int ask(int y){
		int res=0;
		for(;y;y-=lb(y)) res+=c[y];
		return res;
	}
}T1,T2;
void solve(){
	T1.clear(),T2.clear(),T.build(1,1,n);
	LL now=0;
	for(int i=1;i<=n;++i){
		now+=T2.ask(n)-T2.ask(a[i]);
		T1.add(a[i],1),T2.add(a[i],1);
		T.moadd(1,1,n,a[i],n,-1);
		T.modify(1,1,n,a[i],T1.ask(a[i]-1));
		res.clear(),T.find(1,1,n);
		for(int j=0;j<res.size();++j)
		  T2.add(res[j],-1),T.modify(1,1,n,res[j],inf);
		ans[i]=min(ans[i],now);
	}
}
IL void init(){
	memset(ans,63,sizeof(ans));
	n=in();for(int i=1;i<=n;++i) a[i]=b[i]=in();
	sort(b+1,b+n+1),b[0]=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;
	solve();
	for(int i=1;i<=n;++i) a[i]=n-a[i]+1;
	solve();
	for(int i=1;i<=n;++i) printf("%lld\n",ans[i]);
}
int main()
{
	init();
	return 0;
}