题目链接
题意分析
我们把所有的坐标按照行进行排序 然后列就成为了一个排列
把题意进行简单的转化之后就是 求排列中有多少个子串 且该子串排序之后是公差为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<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#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<tre[now<<1|1].Min)
{
tre[now].Min=tre[now<<1].Min;
tre[now].cnt=tre[now<<1].cnt;
}
else if(tre[now<<1|1].Min<tre[now<<1].Min)
{
tre[now].Min=tre[now<<1|1].Min;
tre[now].cnt=tre[now<<1|1].cnt;
}
else if(tre[now<<1].Min==tre[now<<1|1].Min)
{
tre[now].Min=tre[now<<1].Min;
tre[now].cnt=tre[now<<1].cnt+tre[now<<1|1].cnt;
}
}
void down(int now)
{
tre[now<<1].Min+=tre[now].tag;
tre[now<<1|1].Min+=tre[now].tag;
tre[now<<1].tag+=tre[now].tag;
tre[now<<1|1].tag+=tre[now].tag;
tre[now].tag=0;
}
void build(int now,int le,int ri)
{
tre[now].tag=0;
if(le==ri) {tre[now].Min=le;tre[now].cnt=1;return;}
int mid=(le+ri)>>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<ri) update(now<<1|1,mid+1,rinow,le,ri,d);
pushup(now);
}
long long qury(int now,int lenow,int rinow,int le,int ri)
{
if(le<=lenow&&rinow<=ri)
{
if(tre[now].Min==0) return tre[now].cnt;
else return 0;
}
if(tre[now].tag) down(now);
int mid=(lenow+rinow)>>1;long long tmp=0;
if(le<=mid) tmp+=qury(now<<1,lenow,mid,le,ri);
if(mid<ri) tmp+=qury(now<<1|1,mid+1,rinow,le,ri);
return tmp;
}
int main()
{
scanf("%d",&n);
for(int i=1,x,y;i<=n;++i) scanf("%d%d",&x,&y),num[x]=y;
build(1,1,n);
for(int i=1;i<=n;++i)
{
update(1,1,n,1,n,-1);
while(tpx&&num[stx[tpx]]<num[i])
update(1,1,n,stx[tpx-1]+1,stx[tpx],num[i]-num[stx[tpx]]),--tpx;
//这里其实一开始的时候有些疑问
//按照差分的话 我们没有加上原最大值 那么差分累加之后的出现的仍是一个差值而不是一个元素值
//后来发现在区间[L,L]中 L-L=L-L+Max-Min
//而后来的区间都是由此扩展而来 所以我们直接累加移动带来的差值贡献即可
stx[++tpx]=i;
// printf("now [max]=%d
",tpx);
while(tpy&&num[sty[tpy]]>num[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
",tpy);
// printf("now at %d = %lld
",i,ans);
}
printf("%lld
",ans);
return 0;
}