题意
题意：求所有区间的mex和。mex值为没有在该区间出现过的最小非负整数。
-
先求出1为起点的区间的mex值（递增），用它构造一棵线段树
-
后：
用线段树维护当前固定左端点的区间的解的和和最大值，然后更新下一个左端点a[i+1]的区间，那么a[i]就要删除，发现以a[i+1]为左端点的区间所有mex值要把之前第一个mex大于a[i]的位置到下一个a[i]的位置所有值设置为a[i]。
举个例子： 3 2 1 0 2 3 1
左端点是a[1] = 3 , mex: 0 0 0 4 4 4 4
左端点是a[2] = 2 , mex: 0 0 0 3 3 4 4
…
可以发现当左端点是a[2] = 2时，[2,3]的mex都是0< a[1] = 3，然后mex[4] = 4 > a[1] = 3的位置4到 a[6] = a[1] = 3的位置6的解都是a[1]，所以这里直接区间更新。
（摘自：https://blog.csdn.net/hyczms/article/details/48143365 ） -
因为pushdown忘记下传区间max导致调题2小时
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#define int long long
using namespace std;
const int maxn=200003;
int n,f[maxn],keep[maxn],ans,to[maxn];
int max(int a,int b){return a>b?a:b;}
map<int,int>vis,mm;
struct node{int l,r,sum,flag,mx;}a[maxn<<2];
void pushup(int x){a[x].sum=a[x<<1].sum+a[x<<1|1].sum,a[x].mx=max(a[x<<1].mx,a[x<<1|1].mx);}
void pushdown(int x)
{
if(a[x].flag==-1) return;
a[x<<1].flag=a[x].flag,a[x<<1].sum=a[x].flag*(a[x<<1].r-a[x<<1].l+1),a[x<<1].mx=a[x].flag;
a[x<<1|1].flag=a[x].flag,a[x<<1|1].sum=a[x].flag*(a[x<<1|1].r-a[x<<1|1].l+1),a[x<<1|1].mx=a[x].flag;
a[x].flag=-1;
}
void build(int x,int left,int right)
{
a[x].l=left,a[x].r=right,a[x].flag=-1;
if(left==right) return a[x].mx=a[x].sum=keep[left],void();
int mid=left+right>>1;
build(x<<1,left,mid),build(x<<1|1,mid+1,right);
pushup(x);
}
void modify(int x,int left,int right,int d)
{
if(a[x].r<left||a[x].l>right) return;
if(left<=a[x].l&&right>=a[x].r) return a[x].sum=d*(a[x].r-a[x].l+1),a[x].mx=a[x].flag=d,void();
pushdown(x);
modify(x<<1,left,right,d),modify(x<<1|1,left,right,d);
pushup(x);
}
int query(int x,int val)//查找第一个大于等于 val的数的位置
{
if(a[x].mx<val) return -1;
if(a[x].l==a[x].r) return a[x].l;
pushdown(x);
return val<=a[x<<1].mx?query(x<<1,val):query(x<<1|1,val);
}
void getfirst()
{
vis.clear();
for(int i=1,cnt=0;i<=n;++i)
{
vis[f[i]]=1;
while(vis[cnt]) ++cnt;
keep[i]=cnt;
}
}
signed main()
{
// freopen("tmp.in","r",stdin);
while(scanf("%lld",&n)&&n)
{
mm.clear();
memset(to,0,sizeof(to));
for(int i=1;i<=n;++i)
{
scanf("%lld",&f[i]);
if(mm[f[i]]) to[mm[f[i]]]=i;//to[a]表示下一个a的出现位置
mm[f[i]]=i;
}
getfirst(),build(1,1,n),ans=a[1].sum;
for(int i=2;i<=n;++i)
{
modify(1,i-1,i-1,0);
int tmpl=query(1,f[i-1]+1),tmpr=!to[i-1]?n:to[i-1]-1;
if(tmpl!=-1) modify(1,tmpl,tmpr,f[i-1]);
ans+=a[1].sum;
if(!a[1].sum) break;
}
cout<<ans<<'
';
}
return 0;
}