题目链接：https://codeforces.com/contest/526/problem/F
题目大意：
给出一个排列，查询满足R-L = Max - Min的区间[L,R]个数
题目思路：
考虑单调栈与线段树结合
维护以i结尾的合法的区间个数，所以可以将合法区间表示为：
所以:
所以就看一下z = 0的j有多少个
根据单调栈可以维护一下，每次最大值和最小值修改的区间
对于最小值修改: + 原有最小值 - 现在值
对于最大值修改: - 原有最大值 + 现在值
此时注意到：MAX - MIN >= R - L
所以z>=0
所以我们直接维护最小值出现的个数即为答案
Code:
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF= 1e16;
const int maxn = 3e6+7;
const int mod= 998244353;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll num[maxn];
ll sum[maxn],mx[maxn],lazy[maxn];
void push(int k){
mx[k] = min(mx[k<<1|1],mx[k<<1]);
ll templ = mx[k<<1] == mx[k]?sum[k<<1]:0;
ll tempr = mx[k<<1|1] == mx[k]?sum[k<<1|1]:0;
sum[k] = templ+tempr;
}
void build(int k,int l,int r){
lazy[k] = sum[k] = 0;
mx[k] = INF;
if(l == r) return;
int mid = (l+r)/2;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push(k);
}
void down(int k){
if(lazy[k]!=0){
lazy[k<<1] += lazy[k];
lazy[k<<1|1] += lazy[k];
mx[k<<1] += lazy[k];
mx[k<<1|1] += lazy[k];
lazy[k] = 0;
}
}
void ModifyPos(int k,int l,int r,int pos){
if(l == r){
sum[k] = 1;
mx[k] = 0;
return ;
}
down(k);
int mid = (l+r)/2;
if(pos<=mid) ModifyPos(k<<1,l,mid,pos);
else ModifyPos(k<<1|1,mid+1,r,pos);
push(k);
}
void Modify(int k,int l,int r,int x,int y,ll w){
if(x<=l&&y>=r){
mx[k] += w;
lazy[k] += w;
return;
}
down(k);
int mid = (l+r)/2;
if(x<=mid) Modify(k<<1,l,mid,x,y,w);
if(y>mid) Modify(k<<1|1,mid+1,r,x,y,w);
push(k);
}
struct Mi{
int l,mi;
}s_mi[maxn];
struct Mx{
int l,mx;
}s_mx[maxn];
int main(){
read(n);
int si = 0,sm = 0;
for(int i=1;i<=n;i++){
ll x,y;read(x);read(y);
num[x] = y;
}
build(1,1,n);
ll ans = 0;
for(int i=1;i<=n;i++){
int lastmi = i-1,lastmx = i-1;
ModifyPos(1,1,n,i);
if(i>1) Modify(1,1,n,1,i-1,-1);
/* printf("-------%d-----\n",i);
printf("min:\n");*/
while(si&&s_mi[si].mi>=num[i]){
/// printf("%d %d\n",s_mi[si].l,lastmi);
Modify(1,1,n,s_mi[si].l,lastmi,s_mi[si].mi-num[i]);
lastmi = s_mi[si].l - 1;
si--;
}
///printf("max:\n");
while(sm&&s_mx[sm].mx<=num[i]){
/// printf("%d %d\n",s_mx[sm].l,lastmx);
Modify(1,1,n,s_mx[sm].l,lastmx,-s_mx[sm].mx+num[i]);
lastmx = s_mx[sm].l - 1;
sm--;
}
s_mi[++si] = Mi{lastmi+1,num[i]};
s_mx[++sm] = Mx{lastmx+1,num[i]};
/// debug(sum[1]);
ans += sum[1];
}
printf("%lld\n",ans);
return 0;
}
/***
1
4 2
1 3 1 3
2 4 2 4
***/
