差别

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

--- 2020-2021:teams:legal_string:jxm2001:莫队算法_2 [2021/02/07 10:29]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:莫队算法_2 [2021/08/01 19:50] (当前版本)
jxm2001 [算法例题]
@@ 行 207: / 行 207: @@
 莫队区间的右端点仍然单增，于是每个块的右端点移动仍可以 $O(n)$ 维护。
-对莫队区间的左端点每次都从 $i+S+1$ 开始重新向左拓展，然后每次处理完询问后再回滚到 $i+S+1$。注意回滚仅回滚左端点不回滚右端点。
+对莫队区间的左端点每次都从 $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]]
@@ 行 228: / 行 230: @@
 <code cpp>
 const int MAXN=1e5+5;
-int blk_sz,a[MAXN],b[MAXN],col[MAXN],temp[MAXN];
+int blk_sz,a[MAXN],b[MAXN],vis[MAXN];
 struct query{
 	int l,r,idx;
@@ 行 235: / 行 237: @@
 		return r<b.r;
 	}
-}q[MAXN];
+}opt[MAXN];
-LL ans[MAXN],cur,tans;
+LL st[MAXN],cur;
-void add(int v,LL &ans){
+int tp;
-	col[v]++;
+void add(int v){
-	ans=max(ans,1LL*col[v]*b[v]);
+	vis[v]++;
+	st[++tp]=cur;
+	cur=max(cur,1LL*vis[v]*b[v]);
 }
-void del(int v){col[v]--;}
+void del(int v){
+	vis[v]--;
+	cur=st[tp--];
+}
+LL ans[MAXN];
 int main()
 {
-	int n=read_int(),qn=read_int();
+	int n=read_int(),q=read_int();
-	blk_sz=n/sqrt(qn)+1;
+	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,qn)q[i].l=read_int(),q[i].r=read_int(),q[i].idx=i;
+	_for(i,0,q)opt[i].l=read_int(),opt[i].r=read_int(),opt[i].idx=i;
-	sort(q,q+qn);
+	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,qn){
+	_for(i,0,q){
-		if(q[i].l/blk_sz==q[i].r/blk_sz){
+		if(opt[i].l/blk_sz!=opt[i].r/blk_sz){
-			tans=0;
+			if(opt[i].l/blk_sz!=lst){
-			_rep(j,q[i].l,q[i].r){
+				while(lef<=rig)del(a[rig--]);
-				temp[a[j]]++;
+				lst=opt[i].l/blk_sz;
-				tans=max(tans,1LL*temp[a[j]]*b[a[j]]);
+				rig=min(lst*blk_sz+blk_sz-1,n);
+				lef=rig+1;
 			}
-			_rep(j,q[i].l,q[i].r)temp[a[j]]--;
+			while(rig<opt[i].r)add(a[++rig]);
-			ans[q[i].idx]=tans;
+			int tlef=lef;
+			while(tlef>opt[i].l)add(a[--tlef]);
+			ans[opt[i].idx]=cur;
+			while(tlef<lef)del(a[tlef++]);
 		}
-		else{
+	}
-			if(q[i].l/blk_sz!=lst){
+	_for(i,0,q)enter(ans[i]);
-				while(lef<=rig)del(a[lef++]);
+	return 0;
-				lst=q[i].l/blk_sz;
+}
+</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,cur=0;
+				lef=rig+1;
 			}
-			while(rig<q[i].r)add(a[++rig],cur);
+			while(rig<opt[i].r)add(a[++rig]);
-			int tlef=lef;tans=cur;
+			int tlef=lef;
-			while(tlef>q[i].l)add(a[--tlef],tans);
+			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++]);
-			ans[q[i].idx]=tans;
 		}
 	}
-	_for(i,0,qn)enter(ans[i]);
+	_for(i,0,q)enter(ans[i]);
 	return 0;
 }
 </code>
 </hidden>
 ===== $\text{bitset}$ 与莫队 =====
@@ 行 293: / 行 417: @@
 给定长度为 $n$ 的序列 $a$ 和 $m$ 个询问。
-每个询问给定 $[l_1,r_1],[l_2,r_2],[l_3,r_3]$，不断删去三个区间中的相同元素，知道三个区间不存在相同元素，问三个区间剩下的数的个数和。
+每个询问给定 $[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\}$。

CVBB ACM Team

用户工具

站点工具

差别

页面工具