Description
Solution
- 基础线段树？
- 首先考虑固定一个端点，维护所有另一个端点的mex。
- 根据固定的端点的不同是两种截然不同的做法。
历史版本查询线段树
- 简单来说就是记录一个time，将贡献表示成的一个一次函数。
- 对于修改的tag也是类似的一个一次函数。
固定右端点
- 每一个mex的影响区间是单调的。
- 可以动态维护一个单调栈。
- 单调栈的修改次数是有限的。修改的时候可以用线段树二分。
- 同样维护历史查询的线段树
固定左端点
- 用一个线段树维护右端点对应的mex。
- 考虑左端点往右移的时候，的下一个出现的位置之前的所有位置mex都会与取min。
- 然后我们可以发现由于整个序列的mex是单调的，会分成很多个块，我们暴力对每一个整块取min实际上是可以的，也就是每一次修改mex相同的区间。
- 记录一个区间的最大值，以及区间的mex是否相同即可。
- 对于每一个位置r我们要求所有的l对于它的mex，并且有一些连续的l对于这个r的mex都是一样的，这实际上是一个查询历史版本的线段树。
- 对于一个mex，在r上，它的贡献可以被表示成，即一个关于当前的时间（左端点的位置）的一次函数。
- 对于修改（区间赋值）的时候，可以记一个tag表示修改成什么，tagk为对于k的贡献，tagb为对于b的贡献，即贡献为。注意到由于整个区间在这之前已经完全一样了，所以我们tagk和tagb实际可以表示成增量，修改的时候再乘上区间的长度，这样就可以直接把tagk和tagb下传了。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 1000005
#define maxt 5000005
#define LL long long
using namespace std;
int type,n,m,Q,i,j,k,now,tot,a[maxn],nex[maxn],L[maxn],R[maxn];
struct query{int x,i,t;} q[maxn*2];
int cmp(query a,query b){return a.x<b.x;}
int mex[maxn],bz[maxn];
LL ans[maxn];
void read(int &x){
x=0; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
}
LL tk[maxt],tb[maxt],tagk[maxt],tagb[maxt]; int mx[maxt],tag[maxt],sm[maxt];
void upd(int x){
tk[x]=tk[x<<1]+tk[x<<1^1];
tb[x]=tb[x<<1]+tb[x<<1^1];
mx[x]=max(mx[x<<1],mx[x<<1^1]);
if (sm[x<<1]&&sm[x<<1^1]) sm[x]=mx[x<<1]==mx[x<<1^1];
else sm[x]=0;
}
void maketree(int x,int l,int r){
tag[x]=-1;
if (l==r) {
tk[x]=mx[x]=mex[l],sm[x]=1;
return;
}
int mid=(l+r)>>1;
maketree(x<<1,l,mid),maketree(x<<1^1,mid+1,r);
upd(x);
}
void downtag(int x,int l,int r){
tk[x]+=tagk[x]*(r-l+1),tb[x]+=tagb[x]*(r-l+1),mx[x]=tag[x];
if (l<r){
tagk[x<<1]+=tagk[x],tagb[x<<1]+=tagb[x];
tagk[x<<1^1]+=tagk[x],tagb[x<<1^1]+=tagb[x];
tag[x<<1]=tag[x<<1^1]=tag[x];
}
tag[x]=-1,tagk[x]=tagb[x]=0;
}
void change(int x,int l,int r,int ll,int rr,int d){
if (tag[x]!=-1) downtag(x,l,r);
if (l>rr||r<ll||mx[x]<=d) return;
if (ll<=l&&r<=rr&&sm[x]){
tagk[x]=d-mx[x],tagb[x]=-1ll*now*(d-mx[x]),tag[x]=d;
downtag(x,l,r);
return;
}
int mid=(l+r)>>1;
change(x<<1,l,mid,ll,rr,d),change(x<<1^1,mid+1,r,ll,rr,d);
upd(x);
}
LL find(int x,int l,int r,int ll,int rr){
if (tag[x]!=-1) downtag(x,l,r);
if (l>rr||r<ll) return 0;
if (ll<=l&&r<=rr) return tk[x]*now+tb[x];
int mid=(l+r)>>1;
return find(x<<1,l,mid,ll,rr)+find(x<<1^1,mid+1,r,ll,rr);
}
int main(){
read(type),read(n);
for(i=1;i<=n;i++) {
read(a[i]);
if (a[i]>n) a[i]=n+1;
}
for(i=n;i>=1;i--) {
if (bz[a[i]]) nex[i]=bz[a[i]]; else nex[i]=n+1;
bz[a[i]]=i;
}
read(Q);
for(i=1;i<=Q;i++) {
read(k),L[i]=k; if (k-1) tot++,q[tot].x=k-1,q[tot].t=-1,q[tot].i=i;
read(k),R[i]=k; tot++,q[tot].x=k,q[tot].t=1,q[tot].i=i;
}
sort(q+1,q+1+tot,cmp);
memset(bz,0,sizeof(bz));
for(k=0,i=1;i<=n;i++) {
for(bz[a[i]]=1;bz[k];k++);
mex[i]=k;
}
maketree(1,1,n),k=1;
for(now=1;now<=n;now++) {
for(;k<=tot&&q[k].x==now;k++) ans[q[k].i]+=find(1,1,n,L[q[k].i],R[q[k].i])*q[k].t;
if (now+1<nex[now]) change(1,1,n,now+1,nex[now]-1,a[now]);
change(1,1,n,now,now,0);
}
for(i=1;i<=Q;i++) printf("%lld
",ans[i]);
}