Loj 2461 完美的队列

分块 + two pointer.

一个数被加入到队列 $i$ 中后,队列 $i$ 再进行 $a_i$ 次 push 操作,这个数就会被 pop 出来.

考虑对于每次操作 $j$ ,求出一个 $ed(j)$ ,表示在进行了 $(j,ed(j)]$ 内的操作后,操作 $j$ 加入的每个 $x$ 都被 pop 出来了.

对于同一个 $x$ ,将 $(j,ed(j)]$ 这些区间取并,就可以得到这个 $x$ 对每次询问的贡献,那么只需要设法求出每个 $ed(j)$ .

将序列每 $\sqrt n$ 个元素分成一块,对于每次操作 $(l_j,r_j,x_j)$ ,分别考虑整块部分的 $i$ 和边角部分的 $i$ 对 $ed(j)$ 的贡献.

枚举每个整块,对于包含了这一块的所有 $j$ ,每个该块中的 $x_j$ 被完全弹出的时间是递增的,可以用 two pointer 处理.

记录两个指针 $j,k$ ,表示当前考虑了操作 $(j,k]$ 带来的影响.

设 $b(i)$ 表示第 $i$ 个队列再被 push $b(i)$ 次, $x_j$ 就会被弹出,记录一个 $cov$ 表示这一块被整体 pop 了 $cov$ 次.

$k$ 增大,加入一个操作时,若它完整覆盖了该块, $cov$ 增加 $1$ ,否则,将这次操作与这一块的交集部分的 $b(i)$ 都减少 $1$ .

$b(i)$ 初始都为对应的 $a(i)$ ,维护一个 $mx=\max b(i)$ ,当 $mx\le cov$ 时,说明已被完全弹出, $k$ 可以去更新 $ed(j)$ .

$j$ 增大,撤销一个操作时,维护方法类似,将 $cov$ 减少 $1$ ,或将交集部分的 $b(i)$ 都增加 $1$ .

每次修改 $cov$ 是 $O(1)$ 的,修改交集部分的 $b(i)$ 是 $O(\sqrt n)$ 的.

每个操作最多完全覆盖 $O(\sqrt n)$ 个整块,最多与 $2$ 个整块有交集,但未完全覆盖,于是这部分时间复杂度为 $O(m\sqrt n)$ .

再来考虑边角部分的贡献,需要在处理整块贡献的同时维护出一些信息.

设 $s(i)$ 表示前 $i$ 次操作完全覆盖了当前块 $s(i)$ 次.

设 $c(i)$ 表示第 $i$ 个完全覆盖当前块的操作编号.

设 $d(i)$ 表示第 $i$ 个与当前块有交集,但未完全覆盖的操作编号.

设 $e(i)$ 表示第 $e(i)$ 次操作结束后,恰好完全覆盖了该块 $i$ 次.

枚举块内每个位置 $i​$ ,考虑它作为边角部分被覆盖的贡献.

用 two pointer 维护两个指针 $j,k$ ,表示当前考虑了操作 $(d(j),d(k)]$ 的影响,并维护 $mx$ 表示 $i$ 被覆盖的次数.

向后跳时,整块覆盖的次数可以由前缀和 $s$ 算出,交集部分覆盖的次数可以直接由 $d$ 存储的操作编号判断.

当 $mx\le 0$ 时,说明位置 $i$ 上的 $x_j$ 已经被 pop 出去了,此时可以更新答案.

若 $mx=0$ ,说明恰好是由操作 $d(k)$ 弹出去的,否则是 $d(k)$ 之前整块操作弹出的,用维护的 $c,e$ 数组可以找出答案.

设第 $i$ 块的数组 $d$ 大小为 $t_i$ ,则这部分的时间复杂度为 $O(\sum \sqrt n\cdot t_i)=O(\sqrt n\cdot \sum t_i)=O(m\sqrt n)$ .

于是整个算法的时间复杂度为 $O(m\sqrt n)$ .

Copy

//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
void upd(int &x,const int &y)
{
	x=max(x,y);
}
const int MAXN=2e5+10;
int n,m,a[MAXN],b[MAXN],c[MAXN],cn,d[MAXN],dn,e[MAXN],s[MAXN];
int B,lp[MAXN],rp[MAXN],bel[MAXN];
int l[MAXN],r[MAXN],x[MAXN],ed[MAXN],ans[MAXN];
vector<pair<int,int> > vec[MAXN];
int main()
{
	n=read(),m=read();
	B=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		bel[i]=(i-1)/B+1;
		lp[bel[i]]=(bel[i]-1)*B+1;
		rp[bel[i]]=bel[i]*B;
	}
	rp[bel[n]]=n;
	for(int i=1;i<=m;++i)
	{
		l[i]=read();
		r[i]=read();
		x[i]=read();
	}
	for(int id=1;id<=bel[n];++id)
	{
		int L=lp[id],R=rp[id],cov=0,mx=0;
		for(int i=L;i<=R;++i)
			upd(mx,b[i]=a[i]);
		cn=dn=0;
		for(int j=1,k=0;j<=m;++j)
		{
			if(l[j]<=L && R<=r[j])
				--cov;
			else if(l[j]<=R && r[j]>=L)
			{
				int li=max(L,l[j]),ri=min(R,r[j]);
					for(int i=li;i<=ri;++i)
						--b[i];
				mx=0;
				for(int i=L;i<=R;++i)
					upd(mx,b[i]);
			}
			while(k<=m && mx>cov)
			{
				++k;
				if(l[k]<=L && R<=r[k])
					++cov;
				else if(l[k]<=R && r[k]>=L)
				{
					int li=max(L,l[k]),ri=min(R,r[k]);
					for(int i=li;i<=ri;++i)
						--b[i];
					mx=0;
					for(int i=L;i<=R;++i)
						upd(mx,b[i]);
				}
			}
			s[j]=s[j-1];
			if(l[j]<=L && R<=r[j])
				upd(ed[j],k),s[c[++cn]=j]++;
			else if(l[j]<=R && r[j]>=L)
				d[++dn]=j,e[dn]=cn;
		}
		for(int i=L;i<=R;++i)
		{
			mx=a[i];
			for(int j=1,k=0;j<=dn;++j)
			{
				mx+=s[d[j]]-s[d[j-1]];
				if(l[d[j]]<=i && i<=r[d[j]])
				{
					++mx;
					while(k<dn && mx>0)
					{
						++k;
						mx-=s[d[k]]-s[d[k-1]];
						mx-=(l[d[k]]<=i && i<=r[d[k]]);
					}
					if(mx>0)
					{
						if(mx>s[m]-s[d[k]])
							ed[d[j]]=m+1;
						else
							upd(ed[d[j]],c[e[k]+mx]);
					}
					else
					{
						if(l[d[k]]<=i && i<=r[d[k]])
							upd(ed[d[j]],mx<0?c[e[k]+mx+1]:d[k]);
						else
							upd(ed[d[j]],c[e[k]+mx]);
					}
				}
			}
		}
	}
	for(int i=1;i<=m;++i)
	{
		vec[x[i]].push_back(make_pair(i,1));
		vec[x[i]].push_back(make_pair(ed[i],-1));
	}
	for(int i=1;i<=100000;++i)
	{
		sort(vec[i].begin(),vec[i].end());
		int tmp=0,siz=vec[i].size();
		for(int j=0;j<siz;++j)
		{
			int cur=tmp;
			tmp+=vec[i][j].second;
			for(int k=j+1;k<siz && vec[i][k].first==vec[i][j].first;++k)
				tmp+=vec[i][k].second,j=k;
			if(cur==0 && tmp>0)
				++ans[vec[i][j].first];
			else if(cur>0 && tmp==0)
				--ans[vec[i][j].first];
		}
	}
	for(int i=1;i<=m;++i)
		printf("%d\n",ans[i]+=ans[i-1]);
	return 0;
}