「NOIPシミュレーション」奇襲【線分樹】【単調スタック】

件名:
数列を指定して、どれぐらいの区間が区間の最大+1-区間の最小=区間の長さを満たすことができることを求めますか?
満足条件は、m a x+1−m i n=r+1−l=>m a x−m i n=r−l max＋1−min=r+1−l=max=r-min=r-l max+1−min=r+1−min=r+1−l=>max−min=r−min=r−l=
m a x−m i n＋l=r max-min+l=r max−min+l=r
そこで、エニュメレート・rを考えて、線分樹はm a x−m i＋l max−m i n＋l max−min＋lの値を維持し、区間最小値と最小値の個数を求める.
エニュメレーションr r rの過程で、現在区間にr r rを加えた後の新しい区間のn e w m a x≧m a x,n e w m i n≦m i n newmax\geq max,newmin\leq min newmax≧max,newmin≦min
n e w m a x,n e w m i n newmax,newmin newmax,newminの変化も一部の区間で同時に変化します.だから私達は同様な治療方法で二つの単調なスタックを維持します.一つは単調に増加して、一つは単調に減少します.
変更は区間が同時に変化するので、単調スタックの値に基づいて線分樹を区間修正します.
単調なスタックを使用しているので、時間複雑度計算の原理によって、均等に割り出します.O(n l o g n)O(nlogun)O(nlogn)O(nlogn)

#include 
#include 
#include 
#include 
#include 
#define db double
#define sg string
#define ll long long
#define rel(i,x,y) for(ll i=(x);i=(y);i--)
#define res(i,x) for(ll i=head[x];i;i=nxt[i])
using namespace std;

const ll N=5e4+5;
const ll Inf=1e18;
const ll Mod=1e9+7;
const db Eps=1e-10;

ll n,m,ans,a[N],up[N<<2],down[N<<2],mn[N<<2],cnt[N<<2],lazy[N<<2];

#define lson (p<<1)
#define rson (p<<1|1)

inline ll read() {
	ll x=0;char ch=getchar();bool f=0;
	while(ch>'9'||ch='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return f?-x:x;
}

void maketree(ll p,ll l,ll r) {
	mn[p]=l;cnt[p]=1;
	if(l>1;
		maketree(lson,l,mid);
		maketree(rson,mid+1,r);
	}
}

void pushdown(ll p) {
	if(lazy[p]) {
		lazy[lson]+=lazy[p];
		lazy[rson]+=lazy[p];lazy[p]=0;
	}
}

void update(ll p) {
	ll a=mn[lson]+lazy[lson];
	ll b=mn[rson]+lazy[rson];
	mn[p]=min(a,b);
	cnt[p]=(a==mn[p]?cnt[lson]:0)+(b==mn[p]?cnt[rson]:0);
}

void modify(ll p,ll l,ll r,ll x,ll y,ll z) {
	if(x<=l&&r<=y) {
		lazy[p]+=z;return ;
	}
	
	pushdown(p);
	
	ll mid=l+r>>1;
	
	if(x<=mid) modify(lson,l,mid,x,y,z);
	if(y>mid) modify(rson,mid+1,r,x,y,z);update(p);
}

void File() {
	freopen("raid.in","r",stdin);
	freopen("raid.out","w",stdout);
}

int main() {
	File();
	
	n=read();
	
	memset(a,-1,sizeof(a));
	
	rep(i,1,n) {
		ll x=read(),y=read();a[x]=y;
	}
	
	maketree(1,1,n);
	
  	ll cup=1,cdown=1;up[0]=-1;down[0]=-1;
  	
  	rep(i,1,n) {
  		while(cup>=2&&a[i]=2&a[i]>a[down[cdown-1]
modify(1,1,n，down[cdown-2]+1,down[cdown-1]、-a[down[cdown-1]
cdown--;
)	
up[cup+]=idown[cdown+]=i
modify(1,1,n，up[cup-2]+1,up[cup-1]，-a[up-1]
modify(1,1,n，down[cdown-2]+1,down[cdown-1]，a[down[cdown-1]ans+=cnt[1];
)
printf("%lld"，ans);
return 0;
)