自动搬运

查看原文

来自洛谷，原作者为

	All_Wrong_Answer 不拿蓝钩不改签

搬运于2025-08-24 22:19:50，当前版本为作者最后更新于2025-02-17 20:11:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路与算法：

线段树。

先观察，发现一个数在执行完它的排序步骤后不会对接下来的排序产生影响，由于题目需要分大于等于 $\frac{n+1}{2}$ 下取整的值和大于这个值两种，所以线段树的 $sum$ 要有两个，一个是把这个数从当前位置向前移到指定位置所需步数，另一个则是向后移动到指定位置所需的步数。

线段树定义与建树：

struct xds{
	int l;
	int r;
	int sum1,sum2;//两个方向到指定位置的步数 
	int add1,add2;//同理，有两个sum当然就需要两个懒标记 
	void oin1(int a,int b){
		l=a;
		r=b;
		add1=add2=0;
	}
	void oin2(int c){
		sum1=(c-1);
		sum2=(x-c);
		//初始化输入时的位置 
	}
	
}tre[500005];//线段树 

void js(int q,int l,int r){
	tre[q].oin1(l,r);
	if(l==r) {
		tre[q].oin2(l);
		return ;
	}
	int mid=l+r>>1;
	js(q*2,l,mid);
	js(q*2+1,mid+1,r);
}//建树，与模板基本无异 

接下来处理区间加法，显然的，在一个数向前移动以实现排序时，会对这个数位置后面的所有数的 $sum_2$ 产生 $-1$ 的贡献，对这个数前面的所有数的 $sum_1$ 产生 $-1$ 的贡献，这个很显然，不懂的画个图模拟一下样例即可。

区间加：

void qjjf(int q,int ml,int mr,int k,int t){
	if(ml<=zqj&&mr>=yqj){
		if(t==1){
			tre[q].sum1+=((yqj-zqj+1)*k);
		    tre[q].add1+=k;
		}
		else{
			tre[q].sum2+=((yqj-zqj+1)*k);
		    tre[q].add2+=k;
		}
		//分辨对sum1操作还是对sum2操作 
		return ;
	}
	pushdown(q);
	int mid=(zqj+yqj)/2;
	if(ml<=mid) qjjf(left,ml,mr,k,t);
	if(mr>mid) qjjf(right,ml,mr,k,t);
}

最后是单点查询，很简单，与模板无异：

int qjqh(int q,int mb,int dc){
	if(zqj==mb&&yqj==mb){
		if(dc<=(x+1)/2) return tre[q].sum1;//判断这个数是向前移还是向后移的 
		else return tre[q].sum2;
	}
	pushdown(q);
	int mid=(zqj+yqj)/2;
	if(mb<=mid) return qjqh(left,mb,dc);
	if(mb>mid) return qjqh(right,mb,dc); 
}

一点细节：

1. 在输出距离时与 $0$ 取大值，防止输出负数。
2. pushdown 要同时处理两个 $sum$ 的值。
3. 对位置不要直接写成输入时的值了，记得映射一个位置。
4. 本题不用处理区间和，不用写 pushup。

完整代码：

#include <bits/stdc++.h>
using namespace std;

#define left q*2
#define right q*2+1
#define zqj tre[q].l
#define yqj tre[q].r

int x;
int m[100005];

int wz[100005];

struct xds{
	int l;
	int r;
	int sum1,sum2;//两个方向到指定位置的步数 
	int add1,add2;//同理，有两个sum当然就需要两个懒标记 
	void oin1(int a,int b){
		l=a;
		r=b;
		add1=add2=0;
	}
	void oin2(int c){
		sum1=(c-1);
		sum2=(x-c);
		//初始化输入时的位置 
	}
	
}tre[500005];//线段树 

void pushdown(int q){
	if(tre[q].add1!=0){
		tre[q*2].sum1+=((tre[q*2].r-tre[q*2].l+1)*tre[q].add1);
		tre[q*2].add1+=tre[q].add1;
		tre[q*2+1].sum1+=((tre[q*2+1].r-tre[q*2+1].l+1)*tre[q].add1);
		tre[q*2+1].add1+=tre[q].add1;
	}
	if(tre[q].add2!=0){
		tre[q*2].sum2+=((tre[q*2].r-tre[q*2].l+1)*tre[q].add2);
		tre[q*2].add2+=tre[q].add2;
		tre[q*2+1].sum2+=((tre[q*2+1].r-tre[q*2+1].l+1)*tre[q].add2);
		tre[q*2+1].add2+=tre[q].add2;
	}
	tre[q].add1=tre[q].add2=0;
}

void js(int q,int l,int r){
	tre[q].oin1(l,r);
	if(l==r) {
		tre[q].oin2(l);
		return ;
	}
	int mid=l+r>>1;
	js(q*2,l,mid);
	js(q*2+1,mid+1,r);
}//建树，与模板基本无异 
void qjjf(int q,int ml,int mr,int k,int t){
	if(ml<=zqj&&mr>=yqj){
		if(t==1){
			tre[q].sum1+=((yqj-zqj+1)*k);
		    tre[q].add1+=k;
		}
		else{
			tre[q].sum2+=((yqj-zqj+1)*k);
		    tre[q].add2+=k;
		}
		//分辨对sum1操作还是对sum2操作 
		return ;
	}
	pushdown(q);
	int mid=(zqj+yqj)/2;
	if(ml<=mid) qjjf(left,ml,mr,k,t);
	if(mr>mid) qjjf(right,ml,mr,k,t);
}

int qjqh(int q,int mb,int dc){
	if(zqj==mb&&yqj==mb){
		if(dc<=(x+1)/2) return tre[q].sum1;//判断这个数是向前移还是向后移的 
		else return tre[q].sum2;
	}
	pushdown(q);
	int mid=(zqj+yqj)/2;
	if(mb<=mid) return qjqh(left,mb,dc);
	if(mb>mid) return qjqh(right,mb,dc); 
}

signed main(){
	cin>>x;
	for(int i=1;i<=x;i++){
		cin>>m[i];
		wz[m[i]]=i;//映射位置 
	}
	js(1,1,x);
	int s=0;
	int mq1=0,mq2=x+1;
	while(1){
		if(s==x) break;
		if(s%2==0){
			mq1++;
			cout<<max(0,qjqh(1,wz[mq1]/*不要写成m[mq1]，下同*/,mq1))<<endl;
			if(wz[mq1]!=x) qjjf(1,wz[mq1]+1,x,-1,1);//对后面数的sum1产生贡献 
			if(wz[mq1]!=1) qjjf(1,1,wz[mq1]-1,-1,2);//对前面数的sum2产生贡献 
			s++;
		} 
		else{
			mq2--;
			cout<<max(0,qjqh(1,wz[mq2],mq2))<<endl;
			if(wz[mq2]!=1) qjjf(1,1,wz[mq2]-1,-1,2);//对前面数的sum2产生贡献 
			if(wz[mq2]!=x) qjjf(1,wz[mq2]+1,x,-1,1);//对后面数的sum1产生贡献 
			s++;
		}
	}
	return 0; 
}