自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:40:34，当前版本为作者最后更新于2022-10-28 13:54:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解怎么都是 $O(n^2)$ 的……？其实这个题可以 $O(n \log n)$ 的时间复杂度内完成。一个类似的题目是 CF526F。

本题的题意是：统计有多少个区间 $[l,r]$，计区间最大值为 $\max$，区间最小值为 $\min$，区间长度为 $\mathrm{len}=r-l$，满足关系式 $\mathrm{max}-\mathrm{min}=\mathrm{len}$。

进行对原关系式的移项，有 $\mathrm{max}-\mathrm{min}+l=r$。具体而言，考虑套路地枚举区间右端点 $r$ 进行扫描线，求出以 $r$ 为结尾的符合要求的区间个数，然后再求和。而为了满足这一要求，我们需要使用单调栈+线段树维护。考虑到 $\mathrm{max}-\mathrm{min} \geq r-l$，可以使用单调栈维护每个后缀的 $\mathrm{max}$ 和 $\mathrm{min}$，再用线段树维护 $\mathrm{max}-\mathrm{min}-len$ 的最小值以及其出现次数，这个维护就比较简单。时间复杂度 $O(n \log n)$。

本题也可以使用析合树完成。析合树的学习资料请参考 OI-wiki。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int n,a[300050];

struct Seg_Tree
{
	int l,r;
	int tag,val,minv;
}t[1200050];

inline void Push_Up(int id)
{
	t[id].minv=min(t[id<<1].minv,t[id<<1|1].minv);
	t[id].val=(t[id].minv==t[id<<1].minv?t[id<<1].val:0)+(t[id].minv==t[id<<1|1].minv?t[id<<1|1].val:0);
}

inline void Build(int id,int l,int r)
{
	t[id].l=l;
	t[id].r=r;
	if (l==r)
	{
		t[id].minv=l;
		t[id].val=1;
		return;
	}
	int mid=(l+r)>>1;
	Build(id<<1,l,mid);
	Build(id<<1|1,mid+1,r);
	Push_Up(id);
}

inline void Push_Down(int id)
{
	if (t[id].tag)
	{
		t[id<<1].tag+=t[id].tag;
		t[id<<1|1].tag+=t[id].tag;
		t[id<<1].minv+=t[id].tag;
		t[id<<1|1].minv+=t[id].tag;
		t[id].tag=0;
	}
}

inline void Change(int id,int l,int r,int val)
{
	if (l<=t[id].l && t[id].r<=r)
	{
		t[id].tag+=val;
		t[id].minv+=val;
		return;
	}
	Push_Down(id);
	int mid=(t[id].l+t[id].r)>>1;
	if (r<=mid)
		Change(id<<1,l,r,val);
	else if (l>mid)
		Change(id<<1|1,l,r,val);
	else
	{
		Change(id<<1,l,mid,val);
		Change(id<<1|1,mid+1,r,val);
	}
	Push_Up(id);
}

int st1[300050],st2[300050],top1,top2;

long long ans;

int main()
{
	n=read();
	for (int i=1;i<=n;i++)
		a[i]=read();
	Build(1,1,n);
	for (int i=1;i<=n;i++)
	{
		int p=i;
		while (top1 && a[i]<a[st1[top1]])
		{
			Change(1,st1[top1-1]+1,p-1,a[st1[top1]]-a[i]);
			p=st1[top1];
			top1--;
		}
		p=i;
		while (top2 && a[i]>a[st2[top2]])
		{
			Change(1,st2[top2-1]+1,p-1,-a[st2[top2]]+a[i]);
			p=st2[top2];
			top2--;
		}
		st1[++top1]=st2[++top2]=i;
		ans+=t[1].val;
	}
	cout << ans << endl;
	return 0;
}