CF526F Pudding Monsters

转换一下题意，就是给你一个排列，问有多少个区间重新排列后是连续的。其实这是一个套路题，还有一个强化版：给你一个序列（元素小于1e9），问有多少个区间重新排列后是连续（相邻元素差不超过1）的。

首先我们考虑一个区间什么时候是连续的，很显然区间连续的条件是$max-min+1=cnt$，其中$cnt$为元素种类数。划一下式子，就是$max-min+1-cnt=0$。我们可以考虑用线段树维护这个东西。对于一个固定的$r$，线段树上的$l$的值就是$max-min+1-cnt$。

考虑向后移动一步$r$到$r'$时，答案如何变化：令$last$为下标最大的大于$a[r']$的坐标。那么$[last,r']$这个区间的$max$会发生变化。我们需要做的就是把这个区间原来的$max$减掉，加上新的$max$（即$a[i]$）。具体实现就是：区间原来的$max$可以用一个单调栈维护，利用线段树进行区间修改即可。$min$值维护同理。

接着考虑$cnt$的修改。令$last'$为上一个$a[i]$元素的位置。加入$a[i]$会使区间$(last,i]$的$cnt$都加上1。线段树直接操作即可。

确定了$r'$，进行完所有修改之后，就能查询答案了。不难发现，我们维护的东西（$max-min+1-cnt$）的最小值为$0$。且只有这个式子出现0的时候代表这个区间满足条件。那我们维护一下最小值个数即可。

感觉还是一个序列数据结构计数题常用套路：固定其中一个端点，维护另一个端点在各个位置的值。然后移动固定的端点并考虑移动后会让各个位置的值发生那些更改。

加强版代码：

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=1e5+100;
const int inf=1e9+100;
int a[maxn];
int mxstk[maxn],mistk[maxn],mxtop,mitop;//栈里面放的是id
struct segment_tree{//维护 max-min+1-cnt
	int mi[maxn<<2],micnt[maxn<<2],tag[maxn<<2];
	segment_tree(){memset(mi,0x3f,sizeof(mi));}//?
	void push_down(int rt){
		mi[ls]+=tag[rt];mi[rs]+=tag[rt];
		tag[ls]+=tag[rt];tag[rs]+=tag[rt];
		tag[rt]=0;
	}	
	void push_up(int rt){
		mi[rt]=min(mi[ls],mi[rs]);
		micnt[rt]=0;
		if(mi[rt]==mi[ls])micnt[rt]+=micnt[ls];
		if(mi[rt]==mi[rs])micnt[rt]+=micnt[rs];
	}
	void upd(int l,int r,int rt,int tl,int tr,int val){
		if(tl<=l&&r<=tr){mi[rt]+=val;tag[rt]+=val;return;}
		push_down(rt);
		int mid=(l+r)>>1;
		if(tl<=mid)upd(l,mid,ls,tl,tr,val);
		if(tr>=mid+1)upd(mid+1,r,rs,tl,tr,val);
		push_up(rt);
	}
	pii query(int l,int r,int rt,int tl,int tr){
		if(tl<=l&&r<=tr){return mk(mi[rt],micnt[rt]);}
		push_down(rt);
		int mid=(l+r)>>1;
		int mi=inf,cnt=0;pii tmp;
		if(tl<=mid){tmp=query(l,mid,ls,tl,tr);if(tmp.fi<mi)cnt=0,mi=tmp.fi;cnt+=(mi==tmp.fi)?tmp.se:0;}
		if(tr>=mid+1){tmp=query(mid+1,r,rs,tl,tr);if(tmp.fi<mi)cnt=0,mi=tmp.fi;cnt+=(mi==tmp.fi)?tmp.se:0;}
		return mk(mi,cnt);
	}
	void build(int l,int r,int rt){
		if(l==r){mi[rt]=1;micnt[rt]=1;return;}
		int mid=(l+r)>>1;
		build(l,mid,ls);build(mid+1,r,rs);
		push_up(rt);
	}
}t;
map<int,int>last;
int pre[maxn];
int main(){
	int n;scanf("%d",&n);
	rep(i,1,n)scanf("%d",&a[i]),pre[i]=last[a[i]],last[a[i]]=i;
	t.build(1,n,1);ll ans=0;
	rep(i,1,n){
		while(mxtop&&a[mxstk[mxtop]]<=a[i]){
			t.upd(1,n,1,(mxtop==1)?1:(mxstk[mxtop-1]+1),mxstk[mxtop],a[i]-a[mxstk[mxtop]]);mxtop--;
		}
		while(mitop&&a[mistk[mitop]]>=a[i]){
			t.upd(1,n,1,(mitop==1)?1:(mistk[mitop-1]+1),mistk[mitop],-(a[i]-a[mistk[mitop]]));mitop--;
		}
		mistk[++mitop]=i;mxstk[++mxtop]=i;
	//	cout<<((!pre[i])?1:(pre[i]+1))<<endl;
		t.upd(1,n,1,(!pre[i])?1:(pre[i]+1),i,-1);
		pii tmp=t.query(1,n,1,1,i);
		if(!tmp.fi)ans+=tmp.se;
	}
	cout<<ans;
	return 0;
}