T1 自然数
首先预处理以一为左端点所有的 mex 值，然后插入线段树中。
考虑如何修改，左端点右移一位，相当于把那一位的数删掉了，记录下一个出现这个数的位置为 pos ，那么i 到 pos 之间所有大于 x 的 mex 都要修改为 x。
剩下的就是线段树基本操作了。
#include<bits/stdc++.h>
#define N 200010
#define int long long
using namespace std;
int n,jie,a[N];
long long ans;
int tree[N<<2],sum[N<<2],minn[N<<2],tag[N<<2],tong[N],ji,c[N],nxt[N],maxn[N<<2];
struct jj
{int ai,id;}p[N];
inline void pushup(int x)
{ sum[x]=sum[x<<1]+sum[x<<1|1];
minn[x]=min(minn[x<<1],minn[x<<1|1]);
maxn[x]=max(maxn[x<<1],maxn[x<<1|1]);
}#include<bits/stdc++.h>
#define N 200010
#define int long long
using namespace std;
int n,jie,a[N];
long long ans;
int tree[N<<2],sum[N<<2],minn[N<<2],tag[N<<2],tong[N],ji,c[N],nxt[N],maxn[N<<2];
struct jj
{int ai,id;}p[N];
inline void pushup(int x)
{ sum[x]=sum[x<<1]+sum[x<<1|1];
minn[x]=min(minn[x<<1],minn[x<<1|1]);
maxn[x]=max(maxn[x<<1],maxn[x<<1|1]);
}
inline void pushdown(int x,int l,int r)
{ minn[x<<1]=minn[x<<1|1]=maxn[x<<1]=maxn[x<<1|1]=tag[x<<1]=tag[x<<1|1]=tag[x];
int mid=(l+r)>>1;sum[x<<1]=tag[x]*(mid-l+1);sum[x<<1|1]=tag[x]*(r-mid);tag[x]=-1;
}
inline void build(int x,int l,int r)
{ if(l==r){sum[x]=minn[x]=maxn[x]=c[l];return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
pushup(x);
}
inline int query(int x,int l,int r,int L,int R)
{ if(l>=L and r<=R)return sum[x];
int mid=(l+r)>>1,res=0;if(tag[x]!=-1)pushdown(x,l,r);
if(mid<R)res+=query(x<<1|1,mid+1,r,L,R);
if(mid>=L)res+=query(x<<1,l,mid,L,R);
return res;
}
inline void update(int x,int l,int r,int L,int R,int val)
{ if(L>R)return;
if(l>=L and r<=R and minn[x]>=val){maxn[x]=minn[x]=val;sum[x]=val*(r-l+1);tag[x]=val;return;}
int mid=(l+r)>>1;if(tag[x]!=-1)pushdown(x,l,r);
if(mid<R and maxn[x<<1|1]>val)update(x<<1|1,mid+1,r,L,R,val);
if(mid>=L and maxn[x<<1]>val)update(x<<1,l,mid,L,R,val);
pushup(x);
}
signed main()
{ freopen("mex.in","r",stdin);
freopen("mex.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;++i)scanf("%lld",&a[i]),p[i]=(jj){a[i],i};
int zhi=0;
for(int i=1;i<=n;++i)
{ if(a[i]<=n)tong[a[i]]=1;
while(tong[zhi])++zhi;
c[i]=zhi;
}
memset(tong,0,sizeof(tong));memset(tag,-1,sizeof(tag));
for(int i=n;i;--i)if(a[i]<=n){nxt[i]=tong[a[i]];tong[a[i]]=i;}
build(1,1,n);
for(int i=1;i<=n;++i)
{ ans+=query(1,1,n,i,n);
if(a[i]<=n)
{ int pos=nxt[i];
if(!pos)pos=n+1;
update(1,1,n,i,pos-1,a[i]);
}
}
printf("%lld\n",ans);
}
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
pushup(x);
}
inline int query(int x,int l,int r,int L,int R)
{ if(l>=L and r<=R)return sum[x];
int mid=(l+r)>>1,res=0;if(tag[x]!=-1)pushdown(x,l,r);
if(mid<R)res+=query(x<<1|1,mid+1,r,L,R);
if(mid>=L)res+=query(x<<1,l,mid,L,R);
return res;
}
inline void update(int x,int l,int r,int L,int R,int val)
{ if(L>R)return;
if(l>=L and r<=R and minn[x]>=val){maxn[x]=minn[x]=val;sum[x]=val*(r-l+1);tag[x]=val;return;}
int mid=(l+r)>>1;if(tag[x]!=-1)pushdown(x,l,r);
if(mid<R and maxn[x<<1|1]>val)update(x<<1|1,mid+1,r,L,R,val);
if(mid>=L and maxn[x<<1]>val)update(x<<1,l,mid,L,R,val);
pushup(x);
}
signed main()
{ freopen("mex.in","r",stdin);
freopen("mex.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;++i)scanf("%lld",&a[i]),p[i]=(jj){a[i],i};
int zhi=0;
for(int i=1;i<=n;++i)
{ if(a[i]<=n)tong[a[i]]=1;
while(tong[zhi])++zhi;
c[i]=zhi;
}
memset(tong,0,sizeof(tong));memset(tag,-1,sizeof(tag));
for(int i=n;i;--i)if(a[i]<=n){nxt[i]=tong[a[i]];tong[a[i]]=i;}
build(1,1,n);
for(int i=1;i<=n;++i)
{ ans+=query(1,1,n,i,n);
if(a[i]<=n)
{ int pos=nxt[i];
if(!pos)pos=n+1;
update(1,1,n,i,pos-1,a[i]);
}
}
printf("%lld\n",ans);
}
T2 钱仓
贪心，一定存在中转点，一定存在一个分界点满足只向一遍运输，这个分界点就是最大子段和的起点。
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n,c[N],sum[N],nxt[N],maxn,id,tmp,t[N],ans,old[N];
signed main()
{ freopen("barn.in","r",stdin);
freopen("barn.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;++i)scanf("%lld",&c[i]);
for(int i=1;i<=n;++i)
{ tmp+=c[i];
if(tmp<i-id)id=i,tmp=0;
}
++id;
for(int i=id;i<=n;++i)t[i-id+1]=c[i];for(int i=1;i<id;++i)t[i+n-id+1]=c[i];
int zhi1=n;
for(int i=n;i;--i)
{ if(zhi1>i)zhi1=i;
while(!t[zhi1])--zhi1;
if(!t[i])ans+=(i-zhi1)*(i-zhi1),--t[zhi1];
}
printf("%lld\n",ans);
}