自动搬运

查看原文

来自洛谷，原作者为

	FZzzz **

搬运于2025-08-24 22:35:45，当前版本为作者最后更新于2022-03-22 21:19:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

怎么题解区全是莫队，来发 2log 的正解。

考虑分治，每次处理跨过中间点的询问。把两边的部分拉出来排序，考虑若右边有两个位置 $i$ 和 $j$（$a_i<a_j$）在排序后是相邻的，它们会产生怎样的贡献。

• 若左边有 $a_i$ 和 $a_j$ 之间的数，那么一定是从 $i$ 走到左边，走走走再走回 $j$，这样贡献是 $i+j$；
• 否则，就是从 $i$ 直接走到 $j$，这样贡献是 $|i-j|$。

对于最大值和最小值也是类似，考虑左边有没有比它大或者小的。

考虑改写第一种贡献成立的条件。找到分治中点左边最靠右的 $a_i$ 和 $a_j$ 之间的数，那么第一种贡献的条件就是询问左端点在这个位置左边，这是一个一维数点。

对询问的右端点做扫描线，每次插入或删除一个数会插入和删除 $O(1)$ 对这样的 $(i,j)$，相当于我们做动态一维数点，树状数组维护。对于左边的对的贡献也类似维护即可。

更新这样的 $(i,j)$ 需要支持找到当前插入或删除的数的前驱和后继，并支持在另一边找到第一个在某个区间内的数。前者可以 set 维护，后者可以线段树。

但是这样常数很大，也可以右端点从右往左，左端点从左往右，这样只需要删数，可以归并排序和链表维护。

时间复杂度 $O(n\log^2n+m\log n)$，如果你用链表的话瓶颈就是动态一维数点，$n$ 和 $m$ 同阶时可以平衡到 $O\left(\dfrac{n\log^2n}{\log\log n}\right)$。

下面的代码是 2log，提交时和题解提交时可以排到最优解第一并且碾压大部分莫队做法。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline ll read(){
	ll x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') f=1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return f?-x:x;
}
const int maxn=5e5+5;
int n,m,a[maxn],p[maxn],ql[maxn],qr[maxn];
ll c[maxn];
void modify(int x,ll k){
	while(x){
		c[x]+=k;
		x-=x&-x;
	}
}
ll query(int x){
	ll s=0;
	while(x<=n){
		s+=c[x];
		x+=x&-x;
	}
	return s;
}
ll ans[maxn];
vector<int> q[maxn];
int ord[maxn],pre[maxn],suc[maxn],mx[maxn];
void solve(int l,int r,vector<int> vec){
	if(l==r){
		ord[r]=a[r];
		return;
	}
	int mid=l+(r-l)/2;
	vector<int> vec1,vec2,vec3;
	for(int i:vec)
		if(qr[i]<=mid) vec1.push_back(i);
		else if(ql[i]>mid) vec2.push_back(i);
		else vec3.push_back(i);
	solve(l,mid,vec1);
	solve(mid+1,r,vec2);
	int c=l;
	suc[0]=ord[mid+1];
	mx[0]=0;
	while(c<=mid&&ord[c]<ord[mid+1])
		mx[0]=max(mx[0],p[ord[c++]]);
	for(int i=mid+1;i<=r;i++){
		pre[ord[i]]=i==mid+1?0:ord[i-1];
		suc[ord[i]]=i==r?n+1:ord[i+1];
		mx[ord[i]]=0;
		while(c<=mid&&ord[c]<suc[ord[i]])
			mx[ord[i]]=max(mx[ord[i]],p[ord[c++]]);
	}
	pre[n+1]=ord[r];
	for(int i:vec3) q[qr[i]].push_back(i);
	ll res=0;
	auto upd1=[&res](int x,int f){
		int y=suc[x];
		if(x&&y<=n){
			res+=abs(p[x]-p[y])*f;
			modify(mx[x],(p[x]+p[y]-abs(p[x]-p[y]))*f);
		}
		else modify(mx[x],(x?p[x]:p[y])*f);
	};
	upd1(0,1);
	for(int i=mid+1;i<=r;i++) upd1(ord[i],1);
	for(int i=r;i>mid;i--){
		for(int j:q[i]) ans[j]=res+query(ql[j]);
		upd1(pre[a[i]],-1);
		upd1(a[i],-1);
		pre[suc[a[i]]]=pre[a[i]];
		suc[pre[a[i]]]=suc[a[i]];
		mx[pre[a[i]]]=max(mx[pre[a[i]]],mx[a[i]]);
		if(i>mid+1) upd1(pre[a[i]],1);
	}
	for(int i=mid+1;i<=r;i++) vector<int>().swap(q[i]);
	c=mid+1;
	suc[0]=ord[l];
	mx[0]=0;
	while(c<=r&&ord[c]<ord[l]) mx[0]=max(mx[0],n+1-p[ord[c++]]);
	for(int i=l;i<=mid;i++){
		pre[ord[i]]=i==l?0:ord[i-1];
		suc[ord[i]]=i==mid?n+1:ord[i+1];
		mx[ord[i]]=0;
		while(c<=r&&ord[c]<suc[ord[i]])
			mx[ord[i]]=max(mx[ord[i]],n+1-p[ord[c++]]);
	}
	pre[n+1]=ord[mid];
	for(int i:vec3) q[ql[i]].push_back(i);
	auto upd2=[&res](int x,int f){
		int y=suc[x];
		if(x&&y<=n){
			res+=abs(p[x]-p[y])*f;
			modify(mx[x],(-p[x]-p[y]-abs(p[x]-p[y]))*f);
		}
		else modify(mx[x],(x?-p[x]:-p[y])*f);
	};
	upd2(0,1);
	for(int i=l;i<=mid;i++) upd2(ord[i],1);
	for(int i=l;i<=mid;i++){
		for(int j:q[i]) ans[j]+=res+query(n+1-qr[j]);
		upd2(pre[a[i]],-1);
		upd2(a[i],-1);
		pre[suc[a[i]]]=pre[a[i]];
		suc[pre[a[i]]]=suc[a[i]];
		mx[pre[a[i]]]=max(mx[pre[a[i]]],mx[a[i]]);
		if(i<mid) upd2(pre[a[i]],1);
	}
	for(int i=l;i<=mid;i++) vector<int>().swap(q[i]);
	vector<int> tmp;
	c=l;
	for(int i=mid+1;i<=r;i++){
		while(c<=mid&&ord[c]<ord[i]) tmp.push_back(ord[c++]);
		tmp.push_back(ord[i]);
	}
	while(c<=mid) tmp.push_back(ord[c++]);
	for(int i=l;i<=r;i++) ord[i]=tmp[i-l];
}
int main(){
#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	n=read();
	m=read();
	for(int i=1;i<=n;i++) p[a[i]=read()]=i;
	for(int i=1;i<=m;i++){
		ql[i]=read();
		qr[i]=read();
	}
	vector<int> vec;
	for(int i=1;i<=m;i++) vec.push_back(i);
	solve(1,n,vec);
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
#ifdef LOCAL
	fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endif
	return 0;
}

不过我不会告诉你我最开始写了个 set 和线段树的卡了一万年常还 90。