差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:莫队算法_2 [2021/02/04 15:55]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:莫队算法_2 [2021/08/01 19:50] (当前版本)
jxm2001 [算法例题]
@@ 行 193: / 行 193: @@
 ==== 算法模型 ====
+普通莫队仅适用于当询问得区间拓展/删除都可以 $O(1)$ 维护的情况。
+其中有一种操作难以 $O(1)$ 维护时，可以利用回滚莫队仅维护一种操作，时间复杂度仍为 $O(n\sqrt m)$，只是常数增大。
 ==== 算法实现 ====
+设块大小为 $S$，当询问的左右端点都属于同一个块时，可以 $O(S)$ 暴力处理。
+剩下的询问先按左端点分块，然后按右端点从小到大排序。
-==== 算法例题 ====
+对每个块 $[l,r]$ 中的询问，先初始化当前莫队区间的右端点为 $r$，左端点为 $r+1$。
+莫队区间的右端点仍然单增，于是每个块的右端点移动仍可以 $O(n)$ 维护。
+对莫队区间的左端点每次都从 $r+1$ 开始重新向左拓展，然后每次处理完询问后再回滚到 $r+1$。注意回滚仅回滚左端点不回滚右端点。
+于是每个询问的左端点移动可以 $O(S)$ 维护。总时间复杂仍为 $O\left(ms+\frac {n^2}S\right)$，取 $S=O\left(\frac n{\sqrt m}\right)$，时间复杂度为 $O(n\sqrt m)$。
+另外注意当跑到另一个块时需要消除之前的右端点影响，可以考虑暴力清空(因为只有 $O(S)$ 个块)，也可以回滚上一个块的右端点。
+==== 例题1 ====
 [[https://loj.ac/p/2874|Loj 2874]]
@@ 行 205: / 行 219: @@
 === 题意 ===
+给定一个序列，每个询问序列区间 $[l,r]$。设区间 $[l,r]$ 中数 $i$ 出现 $c_i$ 次，求 $\max(i*c_i)$。
 === 题解 ===
+显然对于区间拓展操作，答案很容易维护，但区间删除操作答案难以维护。
+直接套回滚莫队板子即可。
 <hidden 查看代码>
 <code cpp>
+const int MAXN=1e5+5;
+int blk_sz,a[MAXN],b[MAXN],vis[MAXN];
+struct query{
+	int l,r,idx;
+	bool operator < (const query &b)const{
+		if(l/blk_sz!=b.l/blk_sz)return l<b.l;
+		return r<b.r;
+	}
+}opt[MAXN];
+LL st[MAXN],cur;
+int tp;
+void add(int v){
+	vis[v]++;
+	st[++tp]=cur;
+	cur=max(cur,1LL*vis[v]*b[v]);
+}
+void del(int v){
+	vis[v]--;
+	cur=st[tp--];
+}
+LL ans[MAXN];
+int main()
+{
+	int n=read_int(),q=read_int();
+	blk_sz=n/sqrt(q)+1;
+	_rep(i,1,n)a[i]=b[i]=read_int();
+	sort(b+1,b+n+1);
+	int m=unique(b+1,b+n+1)-b;
+	_rep(i,1,n)a[i]=lower_bound(b+1,b+m,a[i])-b;
+	_for(i,0,q)opt[i].l=read_int(),opt[i].r=read_int(),opt[i].idx=i;
+	sort(opt,opt+q);
+	_for(i,0,q){
+		if(opt[i].l/blk_sz==opt[i].r/blk_sz){
+			_rep(j,opt[i].l,opt[i].r)
+			add(a[j]);
+			ans[opt[i].idx]=cur;
+			for(int j=opt[i].r;j>=opt[i].l;j--)
+			del(a[j]);
+		}
+	}
+	int lef=1,rig=0,lst=-1;
+	_for(i,0,q){
+		if(opt[i].l/blk_sz!=opt[i].r/blk_sz){
+			if(opt[i].l/blk_sz!=lst){
+				while(lef<=rig)del(a[rig--]);
+				lst=opt[i].l/blk_sz;
+				rig=min(lst*blk_sz+blk_sz-1,n);
+				lef=rig+1;
+			}
+			while(rig<opt[i].r)add(a[++rig]);
+			int tlef=lef;
+			while(tlef>opt[i].l)add(a[--tlef]);
+			ans[opt[i].idx]=cur;
+			while(tlef<lef)del(a[tlef++]);
+		}
+	}
+	_for(i,0,q)enter(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+==== 例题2 ====
+[[https://ac.nowcoder.com/acm/contest/11256/I|2021牛客暑期多校训练营5 I]]
+=== 题意 ===
+给定一个长度为 $n$ 的序列 $A$，接下来有 $q$ 个询问。每次询问给定 $l,r,k$，求
+$$
+\sum_{i=0}^{k-1}f(l-i,r+i)(n+1)^i
+$$
+其中 $f$ 定义如下
+$$
+f(l,r)=\max(\{k|\exists x\forall i(0\le i\le k-1\to \exists j(l\le j\le r,a_j=x+i))\})
+$$
+=== 题解 ===
+考虑回滚莫队处理询问，难点在于怎么维护最大的 $k$。
+实际上，这等价于维护数轴上的最长连续线段。可以令 $\text{vl}(x)$ 表示以数 $x$ 为左端点的线段在数轴上的右端点。
+$\text{vr}(x)$ 表示以数 $x$ 为右端点的线段在数轴上的左端点。于是只需要保证每条线段的两个端点的 $\text{vl},\text{vr}$ 正确性即可，不难 $O(1)$ 维护。
+时间复杂度 $O\left(n\sqrt q+\sum k\right)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,mod=998244353;
+int blk_sz,a[MAXN];
+struct query{
+	int l,r,k,idx;
+	bool operator < (const query &b)const{
+		if(l/blk_sz!=b.l/blk_sz)return l<b.l;
+		return r<b.r;
+	}
+}opt[MAXN];
+struct node{
+	int p1,v1,p2,v2,ans;
+}st[MAXN];
+int curlen,vis[MAXN],vl[MAXN],vr[MAXN],tp;
+void add(int v){
+	if(vis[v]++)return;
+	int l=vis[v-1]?vl[v-1]:v;
+	int r=vis[v+1]?vr[v+1]:v;
+	st[++tp]=node{l,vr[l],r,vl[r],curlen};
+	vr[l]=r;
+	vl[r]=l;
+	curlen=max(curlen,r-l+1);
+}
+void del(int v){
+	if(--vis[v])return;
+	vr[st[tp].p1]=st[tp].v1;
+	vl[st[tp].p2]=st[tp].v2;
+	curlen=st[tp].ans;
+	tp--;
+}
+int solve(int l,int r,int k,int n){
+	int ans=curlen,base=1;
+	_for(i,1,k){
+		add(a[l-i]);
+		add(a[r+i]);
+		base=1LL*base*(n+1)%mod;
+		ans=(ans+1LL*curlen*base)%mod;
+	}
+	for(int i=k-1;i;i--){
+		del(a[r+i]);
+		del(a[l-i]);
+	}
+	return ans;
+}
+int ans[MAXN];
+int main()
+{
+	int n=read_int(),q=read_int();
+	_rep(i,1,n)
+	a[i]=read_int();
+	_for(i,0,q){
+		int l=read_int(),r=read_int(),k=read_int();
+		opt[i]=query{l,r,k,i};
+	}
+	blk_sz=n/sqrt(q)+1;
+	sort(opt,opt+q);
+	_for(i,0,q){
+		if(opt[i].l/blk_sz==opt[i].r/blk_sz){
+			_rep(j,opt[i].l,opt[i].r)
+			add(a[j]);
+			ans[opt[i].idx]=solve(opt[i].l,opt[i].r,opt[i].k,n);
+			for(int j=opt[i].r;j>=opt[i].l;j--)
+			del(a[j]);
+		}
+	}
+	int lef=1,rig=0,lst=-1;
+	_for(i,0,q){
+		if(opt[i].l/blk_sz!=opt[i].r/blk_sz){
+			if(opt[i].l/blk_sz!=lst){
+				while(lef<=rig)del(a[rig--]);
+				lst=opt[i].l/blk_sz;
+				rig=min(lst*blk_sz+blk_sz-1,n);
+				lef=rig+1;
+			}
+			while(rig<opt[i].r)add(a[++rig]);
+			int tlef=lef;
+			while(tlef>opt[i].l)add(a[--tlef]);
+			ans[opt[i].idx]=solve(opt[i].l,opt[i].r,opt[i].k,n);
+			while(tlef<lef)del(a[tlef++]);
+		}
+	}
+	_for(i,0,q)enter(ans[i]);
+	return 0;
+}
 </code>
 </hidden>
+===== $\text{bitset}$ 与莫队 =====
+==== 算法例题 ====
+[[https://www.luogu.com.cn/problem/P4688|洛谷p4688]]
+=== 题意 ===
+给定长度为 $n$ 的序列 $a$ 和 $m$ 个询问。
+每个询问给定 $[l_1,r_1],[l_2,r_2],[l_3,r_3]$，不断删去三个区间中的相同元素，直到三个区间不存在相同元素，问三个区间剩下的数的个数和。
+例如，给定序列 $1,1,1,2,3$，询问区间 $[1,3],[2,4],[3,5]$，进行删去操作后三个区间元素为 $\{1\},\{2\},\{2,3\}$。
+=== 题解 ===
+不难发现答案为 $r_1-l_1+r_2-l_2+r_3-l_3+3-s$，其中 $s$ 为公共元素的个数。
+考虑维护每个原询问对应的公共元素的 $\text{bitset}$，初始时全为 $1$，记为 $s_i$。将原询问拆成三个询问区间丢掉莫队。
+$\text{bitset}$ 维护莫队区间元素，记为 $\text{cur}$。每次处理询问只需要将当前询问对应对应 $s_i$ 更新为 $s_i\text{&cur}$ 即可。
+但是不难发现 $\text{bitset}$ 不支持重复元素，于是进行如下改造。
+定义 $b_i$ 为序列 $a$ 中不大于 $a_i$ 的位置的个数，然后当 $a_i$ 在莫队区间第 $c_i$ 次出现时，将 $b_i-c_i$ 加入 $\text{bitset}$。
+另外需要维护 $m$ 个 $s_i$，于是空间复杂度为 $O(\frac {nm}{w})$ 难以承受。考虑将询问分成三份，于是空间复杂度变为原来的 $\frac 13$。
+原时间复杂度 $O(n\sqrt m+\frac{nm}{w})$。另外由于询问分成了三份，于是新时间复杂度为 $O(n\sqrt {3m}+\frac{nm}{w})$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXM=3.5e4;
+bitset<MAXN> qs[MAXM],cur;
+int a[MAXN],b[MAXN],c[MAXN],ans[MAXM];
+int blk_sz,col[MAXN];
+struct query{
+	int l,r,idx;
+	bool operator < (const query &b)const{
+		if(l/blk_sz!=b.l/blk_sz)return l<b.l;
+		return ((l/blk_sz)&1)?(r<b.r):(r>b.r);
+	}
+}q[MAXM*3];
+void add(int v){
+	col[v]++;
+	cur[c[v]-col[v]]=1;
+}
+void del(int v){
+	cur[c[v]-col[v]]=0;
+	col[v]--;
+}
+int main()
+{
+	int n=read_int(),m=read_int();
+	_rep(i,1,n)a[i]=b[i]=read_int();
+	sort(b+1,b+n+1);
+	int nn=unique(b+1,b+n+1)-b;
+	_rep(i,1,n){
+		a[i]=lower_bound(b+1,b+nn,a[i])-b;
+		c[a[i]]++;
+	}
+	_for(i,1,nn)c[i]+=c[i-1];
+	while(m){
+		int qpos=0,qcnt=0;
+		mem(col,0);
+		while(m&&qpos<MAXM){
+			m--;
+			qs[qpos].set();
+			ans[qpos]=0;
+			_for(i,0,3){
+				int l=read_int(),r=read_int();
+				q[qcnt++]=query{l,r,qpos},ans[qpos]+=r-l+1;
+			}
+			qpos++;
+		}
+		blk_sz=n/sqrt(qcnt)+1;
+		sort(q,q+qcnt);
+		cur.reset();
+		int lef=1,rig=0;
+		_for(i,0,qcnt){
+			while(lef>q[i].l)add(a[--lef]);
+			while(rig<q[i].r)add(a[++rig]);
+			while(lef<q[i].l)del(a[lef++]);
+			while(rig>q[i].r)del(a[rig--]);
+			qs[q[i].idx]&=cur;
+		}
+		_for(i,0,qpos)
+		enter(ans[i]-3*qs[i].count());
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具