题目链接

题意分析

我们把所有的坐标按照行进行排序 然后列就成为了一个排列

把题意进行简单的转化之后就是 求排列中有多少个子串 且该子串排序之后是公差为1的等差数列

这道题其实真的很锻炼思维

首先 对于一个字串\([L,R]\) 其中的最大值以及最小值为\(Max,Min\) 那么显而易见的就是\(Max-Min=R-L\)

也就是\(Max-Min+L-R=0\)

一般来说 这种问题我们会考虑扫描右端点 然后每一次扫描求出有多少个符合要求的左端点

由于是排列 所以\(Max-Min+L-R≥0\) 所以我们只需要求左边对应的最小值是否为零 已经为零的数量

考虑使用线段树来维护当前\(Max-Min+L-R\) 但是具体到\(Max\),\(Min\),\(L\),\(R\)的维护

\(L\)：由于变的只是右端点 左端点是不变的 所以我们一开始就可以直接维护上其贡献

\(R\)：右端点每一次移动都会+1 所以我们直接每一次之后对所有都来个-1就可以了

\(Max\)以及\(Min\)：动态移动维护前缀最小值 这不就是单调栈一贯的用法吗？

以维护最大值为例 我们维护一个单调递减的单调栈 假设单调栈的栈顶为top 对应栈顶值为是sta[top]

当前如果出现一个值now大于栈顶元素之后 那么栈元素sta[top-1]对应的位置是le sta[top]对应的位置是ri

[le+1,ri]都要消去最大值sta[top]的影响，而加上新的最大值now的影响

维护最小值同样如此

CODE:

#include
#include
#include
#include
#include
#include
#define N 300080
using namespace std;
int n,tpx,tpy;
long long ans;
int num[N],stx[N],sty[N];
struct Node
{
	int Min,tag;long long cnt;
}tre[N<<2];
void pushup(int now)
{
	if(tre[now<<1].Min>1;
	build(now<<1,le,mid);build(now<<1|1,mid+1,ri);
	tre[now]=tre[now<<1];
}
void update(int now,int lenow,int rinow,int le,int ri,int d)
{
	if(le<=lenow&&rinow<=ri)
	{
		tre[now].Min+=d;
		tre[now].tag+=d;
		return;
	}
	if(tre[now].tag) down(now);
	int mid=(lenow+rinow)>>1;
	if(le<=mid) update(now<<1,lenow,mid,le,ri,d);
	if(mid>1;long long tmp=0;
	if(le<=mid) tmp+=qury(now<<1,lenow,mid,le,ri);
	if(midnum[i])
		update(1,1,n,sty[tpy-1]+1,sty[tpy],num[sty[tpy]]-num[i]),--tpy;
		sty[++tpy]=i;
		ans+=qury(1,1,n,1,i);
//		printf("now [min]=%d\n",tpy);
//		printf("now at %d = %lld\n",i,ans);
	}
	printf("%lld\n",ans);
	return 0;
}