【2022NOI模拟赛01】漏网之鱼 做题记录

给定一个长度为 $n$ 的序列 $a$，有 $q$ 次询问，每次询问给定 $L,R$，求

$\sum\limits_{l=L}^{R}\sum\limits_{r=l}^{R} \operatorname{mex}(\{a_l,a_{l+1},a_{l+2},\dots,a_r\})$

其中 $\operatorname{mex}(S)$ 表示 $S$ 中最小的未出现的非负整数。

$1\le n,q\le 10^6$。

考虑只有一次询问的时候怎么做，首先 $l=1$ 时每个 $[l,r]$ 的 $\operatorname{mex}$ 是可以 $O(n)$ 预处理的，那么接下来考虑把 $l$ 往右移，即删掉 $a_l$ 后每个 $[l,r]$ 的 $\operatorname{mex}$。

不如设当前 $[l,i]$ 的 $\operatorname{mex}$ 为 $me_i$，那么删除 $a_l$ 相当于让 $me_{[l+1,nxt_{l}-1]}$ 对 $a_l$ 取 $\min$，其中 $nxt_{l}$ 为 $a_l$ 下一次出现的位置。

不难发现可以用线段树维护 $me$，由于 $me$ 有单调性，所以区间取 $\min$ 可以通过线段树二分找到 $>a_l$ 的后缀来转换成区间赋值。那么只有一个询问就可以在 $O(n\log n)$ 的时间内解决。

考虑有多个询问的情况，显然一次询问 $[L,R]$ 可以拆成 $l\in[1,R],r\in[L,R]$ 的答案减掉 $l\in[1,L-1],r\in[L,R]$ 的答案，那么问题就变成要求 $l\in[1,x],r\in[L,R]$ 的答案。

考虑把询问离线下来，按照 $x$ 升序排序，然后把 $l$ 从 $1$ 往右移动。这样问题就变成了要求 $[L,R]$ 的 $me$ 的历史和（每次修改后的值累加的结果，可以看作是在时间维上做前缀和）。

维护历史和有很多种写法，比较通用的是给每个位置维护一个一次函数 $k\times tme+b$，其中 $tme$ 表示当前时间，$k$ 存的是上一次修改之后的 $me_i$。在时间 $i$ 修改一个位置的 $me$ 为 $x$ 的时候，设 $b'$ 为新的 $b$，$k'$ 为新的 $k$，那么有：

$b'=i\times (k-x)+b\\ k'=x$

注意到这个东西只有在区间内每个位置的 $k$ 都相等时才可以用区间加快速维护，但是不难发现一个区间改完之后区间内的每个位置的 $k$ 就会变成一样的，所以每次修改暴力找到所有区间内 $k$ 相等的区间是对的，这样做每一次修改的时间复杂度均摊为 $O(\log n)$，那么总时间复杂度就是 $O((n+q)\log n)$。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=1000005;

struct ask
{
	int l,r,bse,id;
};

struct node
{
	long long ks,bs;
	long long mnk,mxk,tk,tb;
};

int IDX;
int n,q,a[S];
node tr[S<<2];
vector<ask> vec[S];
bool vis[S];
int b[S],lst[S],nxt[S];
long long ans[S];

inline void upd(int u)
{
	tr[u].ks=tr[u<<1].ks+tr[u<<1|1].ks;
	tr[u].bs=tr[u<<1].bs+tr[u<<1|1].bs;
	tr[u].mnk=min(tr[u<<1].mnk,tr[u<<1|1].mnk);
	tr[u].mxk=max(tr[u<<1].mxk,tr[u<<1|1].mxk);
}

void build(int u,int l,int r)
{
	if(l==r) return tr[u].ks=tr[u].mnk=tr[u].mxk=b[l],void();
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	upd(u);
}

inline void addtag(int u,int l,int r,long long k,long long b)
{
	int siz=r-l+1;
	tr[u].ks+=k*siz,tr[u].bs+=b*siz;
	tr[u].mnk+=k,tr[u].mxk+=k;
	tr[u].tk+=k,tr[u].tb+=b;
}

inline void dwntag(int u,int l,int r)
{
	if(tr[u].tk==0&&tr[u].tb==0) return;
	int mid=l+r>>1;
	addtag(u<<1,l,mid,tr[u].tk,tr[u].tb);
	addtag(u<<1|1,mid+1,r,tr[u].tk,tr[u].tb);
	tr[u].tk=tr[u].tb=0;
}

int quepos(int u,int l,int r,int L,int R,long long k)
{
	if(l>R||r<L||tr[u].mxk<=k) return -1;
	if(l==r) return l;
	dwntag(u,l,r);
	int mid=l+r>>1;
	if(L<=mid&&tr[u<<1].mxk>k) return quepos(u<<1,l,mid,L,R,k);
	return quepos(u<<1|1,mid+1,r,L,R,k);
}

void upda(int u,int l,int r,int L,int R,int tme,long long k)
{
	if(l>R||r<L) return;
	if(l>=L&&r<=R&&tr[u].mxk==tr[u].mnk)
	{
		int len=r-l+1;
		addtag(u,l,r,k-tr[u].mxk,tme*(tr[u].mxk-k));
		return;
	}
	dwntag(u,l,r);
	int mid=l+r>>1;
	if(L<=mid) upda(u<<1,l,mid,L,R,tme,k);
	if(R>=mid+1) upda(u<<1|1,mid+1,r,L,R,tme,k);
	upd(u);
}

long long quer(int u,int l,int r,int L,int R,int x)
{
	if(l>R||r<L) return 0;
	if(l>=L&&r<=R) return 1ll*tr[u].ks*x+tr[u].bs;
	dwntag(u,l,r);
	int mid=l+r>>1;
	long long res=0;
	if(L<=mid) res+=quer(u<<1,l,mid,L,R,x);
	if(R>=mid+1) res+=quer(u<<1|1,mid+1,r,L,R,x);
	return res;
}

int main()
{
	scanf("%d",&IDX);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=min(a[i],n+1);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		vec[r].push_back((ask){l,r,1,i});
		if(l>1) vec[l-1].push_back((ask){l,r,-1,i});
	}
	for(int i=1,p=0;i<=n;i++)
	{
		vis[a[i]]=true;
		while(vis[p]) p++;
		b[i]=p;
	}
	build(1,1,n);
	for(int i=0;i<=n+1;i++) lst[i]=n+1;
	for(int i=n;i>=1;i--)
	{
		nxt[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(ask u:vec[i])
		{
			ans[u.id]+=u.bse*quer(1,1,n,u.l,u.r,i);
		}
		int lb=i+1,rb=nxt[i]-1;
		if(lb<=rb)
		{
			int pos=quepos(1,1,n,lb,rb,a[i]);
			if(pos!=-1) upda(1,1,n,pos,rb,i,a[i]);
		}
		upda(1,1,n,i,i,i,0);
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}