不要在意线段树

线段树绝对没问题

单调栈看调试输出也似乎没什么问题

#include<cstdio>
using namespace std;

#define N 300005

int n;
int a[N];
struct stack_val{int r,v;} maxs_stk[N],mins_stk[N];
int maxs_top,mins_top;
struct node
{
	int l,r;
	int full,aful;
	node *lson,*rson;
	node(){}
	node(int l,int r):l(l),r(r),full(0),aful(0),lson(nullptr),rson(nullptr){}
} *root;

node* new_node(int l,int r){return new node(l,r);}

void upd(node *Node)
{
	int &l=Node->l,&r=Node->r,&full=Node->full,&aful=Node->aful;
	node *&lson=Node->lson,*&rson=Node->rson;
	
	if(l==r)
		return;
	int mid=l+r>>1;
	if(lson==nullptr)
		lson=new_node(l,mid);
	if(rson==nullptr)
		rson=new_node(mid+1,r);
}

void pushup(node *Node)
{
	int &l=Node->l,&r=Node->r,&full=Node->full,&aful=Node->aful;
	node *&lson=Node->lson,*&rson=Node->rson;
	
	if(aful!=0)
		full=r-l+1;
	else if(l<r)
		upd(Node),
		full=lson->full+rson->full;
	else
		full=0;
}

void add(node *Node,int v)
{
	int &l=Node->l,&r=Node->r,&full=Node->full,&aful=Node->aful;
	node *&lson=Node->lson,*&rson=Node->rson;
	
	aful+=v;
	upd(Node);
	pushup(Node);
}

void modify(node *Node,int x,int y,int v)
{
	int &l=Node->l,&r=Node->r,&full=Node->full,&aful=Node->aful;
	node *&lson=Node->lson,*&rson=Node->rson;
	
	if(x<=l&r<=y)
	{
		add(Node,v);
		return;
	}
	if(y<l||r<x)
		return;
	int mid=l+r>>1;
	upd(Node);
	modify(lson,x,y,v);
	modify(rson,x,y,v);
	pushup(Node);
}

int query(){return root->full;}
signed main()
{
	// fclose(stdout);
	fclose(stderr);
	root=new node(1,3e6);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x]=y;
	}
	int ans=0;
	for(int i=n;i>=1;--i)
	{
		modify(root,i+1,n,-1);
		int l=i+1;
		while(maxs_top&&maxs_stk[maxs_top].v<=a[i])
			modify(root,l,maxs_stk[maxs_top].r,a[i]-maxs_stk[maxs_top].v),
			l=maxs_stk[maxs_top].r+1,
			--maxs_top;
		maxs_stk[++maxs_top].v=a[i];
		maxs_stk[maxs_top].r=l-1;
		l=i+1;
		while(mins_top&&mins_stk[mins_top].v>=a[i])
			modify(root,l,mins_stk[mins_top].r,mins_stk[mins_top].v-a[i]),
			l=mins_stk[mins_top].r+1,
			--mins_top;
		mins_stk[++mins_top].v=a[i];
		mins_stk[mins_top].r=l-1;
		fputs("==========\n",stderr);
		fprintf(stderr,"query=%d\n",(n-query())-(i-1));
		for(int j=1;j<=maxs_top;++j)
			fprintf(stderr,"[r=%d,v=%d] ",maxs_stk[j].r,maxs_stk[j].v);
		fputc('\n',stderr);
		for(int j=1;j<=mins_top;++j)
			fprintf(stderr,"[r=%d,v=%d] ",mins_stk[j].r,mins_stk[j].v);
		fputc('\n',stderr);
		// fputs("\n==========\n",stderr);
		ans+=(n-query())-(i-1);
	}
	printf("%d",ans);
	return 0;
}/*
max[i]-min[i]-i+l=0
*/

CF526F