CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:莫队算法_1 [2021/02/01 22:57]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:莫队算法_1 [2021/02/07 19:17] (当前版本)
jxm2001
@@ 行 135: / 行 135: @@
 另外如果修改的位置属于区间 $[l,r]$，则需要对答案进行修改。
-假设 $n$ 和 $m$ 同阶，取取块的大小为 $O\left(n^{\frac 23}\right)$，则总时间复杂度为 $O\left(n^{\frac 53}\right)$。
+假设 $n$ 和 $m$ 同阶，首先对每个块，$t_i$ 单调，于是每个块移动时间指针的复杂度为 $O(n)$，移动时间指针的总复杂度为 $O\left(\frac {n^3}{S^2}\right)$。
-==== 算法例题 ====
+同时每个左/右指针每次只能在所在块中移动，于是每个询问左/右指针的复杂度为 $O(S)$，移动左指针的总复杂度为 $O(nS)$。
+于是总复杂度为 $O\left(\frac {n^3}{S^2}+nS\right)$，取取块的大小为 $O\left(n^{\frac 23}\right)$，则总时间复杂度为 $O\left(n^{\frac 53}\right)$。
+==== 例题 1 ====
 [[https://www.luogu.com.cn/problem/P1903|洛谷p1903]]
@@ 行 156: / 行 160: @@
 <code cpp>
 const int MAXN=1.5e5,MAXC=1e6+5;
-int blk_sz,a[MAXN],col[MAXC],cur_ans;
+int blk_sz,cc[MAXN],lc[MAXN],col[MAXC],cur_ans;
 struct query{
 	int l,r,t,idx;
 	bool operator < (const query &b)const{
 		if(l/blk_sz!=b.l/blk_sz)return l<b.l;
-		if(r/blk_sz!=b.r/blk_sz)return r<b.r;
+		if(r/blk_sz!=b.r/blk_sz)return ((l/blk_sz)&1)?(r<b.r):(r>b.r);
-		return t<b.t;
+		return ((r/blk_sz)&1)?(t<b.t):(t>b.t);
 	}
 }q[MAXN];
@@ 行 168: / 行 172: @@
 	int pos,pre,now;
 }p[MAXN];
-int ans[MAXN],q_cnt,p_cnt,lef=1,rig=0;
+int ans[MAXN],qn,pn,lef=1,rig=0;
 void add(int c){
 	if(!col[c])cur_ans++;
@@ 行 179: / 行 183: @@
 void update(opt &p){
 	if(lef<=p.pos&&p.pos<=rig){
-		del(p.now);
+		del(p.pre);
-		add(p.pre);
+		add(p.now);
 	}
-	a[p.pos]=p.pre;
+	cc[p.pos]=p.now;
 	swap(p.pre,p.now);
 }
@@ 行 190: / 行 194: @@
 	blk_sz=pow(n,2.0/3);
 	_rep(i,1,n)
-	a[i]=read_int();
+	cc[i]=lc[i]=read_int();
 	_for(i,0,m){
 		char c=get_char();
 		if(c=='Q'){
-			q[q_cnt].l=read_int(),q[q_cnt].r=read_int(),q[q_cnt].t=p_cnt,q[q_cnt].idx=q_cnt;
+			qn++;
-			q_cnt++;
+			q[qn].l=read_int(),q[qn].r=read_int(),q[qn].t=pn,q[qn].idx=qn;
 		}
 		else{
-			int pos=read_int(),v=read_int();++p_cnt;
+			pn++;
-			p[p_cnt].pos=pos,p[p_cnt].pre=a[pos],p[p_cnt].now=v,a[pos]=v;
+			int pos=read_int(),v=read_int();
+			p[pn].pos=pos,p[pn].pre=lc[pos],p[pn].now=(lc[pos]=v);
 		}
 	}
-	sort(q,q+q_cnt);
+	sort(q+1,q+qn+1);
-	int tim=p_cnt;
+	int tim=0;
-	_for(i,0,q_cnt){
+	_rep(i,1,qn){
+		while(lef>q[i].l)add(cc[--lef]);
+		while(rig<q[i].r)add(cc[++rig]);
+		while(lef<q[i].l)del(cc[lef++]);
+		while(rig>q[i].r)del(cc[rig--]);
+		while(tim<q[i].t)update(p[++tim]);
+		while(tim>q[i].t)update(p[tim--]);
+		ans[q[i].idx]=cur_ans;
+	}
+	_rep(i,1,qn)
+	enter(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+==== 例题 2 ====
+[[https://codeforces.com/problemset/problem/940/F|CF940F]]
+=== 题意 ===
+给定一个长度为 $n$ 的序列，接下来两种操作。
+操作 $1$ 给定询问区间 $[l,r]$，设 $c_i$ 表示 $i$ 在 $a_l\sim a_r$ 中出现的次数，$s_i$ 表示 $i$ 在 $c_0\sim c_{1e9}$ 中出现的次数，求 $\text{mex}(s)$。
+其中 $\text{mex}(s)$ 表示没有出现在序列 $s$ 中的最小非负整数。
+操作 $2$ 为单点修改。
+=== 题解 ===
+首先离散化一下原序列和修改操作的数值，这样数值范围变为 $O(n+q)$，同时也不会影响答案。
+另外假设 $\text{mex}(s)=k+1$，则对每个 $i\in [1,k]$ 至少有一个 $j$ 满足 $c_j=i$，于是这样询问区间长度至少为 $\sum_{i=1}^k i=\frac {k(k+1)}2$。
+于是 $\text{mem}(s)\sim O(\sqrt n)$。带修莫队维护 $c,s$ 序列，对每个询问暴力查询 $s$ 数组，时间复杂度 $O(n^{\frac 53}+m\sqrt n)$。
+==== 例题 3 ====
+[[https://codeforces.com/contest/1476/problem/G|CF1476G]]
+=== 题意 ===
+给定一个长度为 $n$ 的序列，接下来两种操作。
+操作 $1$ 给定询问区间 $[l,r]$ 和整数 $k$，设 $c_i$ 表示 $i$ 在 $a_l\sim a_r$ 中出现的次数，要求选择 $k$ 个 $c_i\gt 0$，记为 $d_{1\sim k}$，最小化 $\max (d)-\min (d)$。
+操作 $2$ 为单点修改。
+=== 题解 ===
+设 $s$ 表示将 $c$ 从小到大排列的序列，于是答案变为 $\min (s_{i+k}-s_i)$。
+有由于对于一个固定区间，$c_i$ 最多只有 $O(\sqrt n)$ 种取值(原因见例题 2)，于是 $s$ 最多仅有 $O(\sqrt n)$ 个值相同的段。
+考虑维护 $s$ 每个段的左端点和右端点，然后双指针遍历 $s$，即可 $O(\sqrt n)$ 得到答案。
+接下来考虑如何维护 $s$，当 $c_i$ 变为 $c_i+1$ 时，只需要将 $s$ 中的值等于 $c_i$ 的段的右端点的 $c_i$ 改为 $c_i+1$ 即可。
+当 $c_i$ 变为 $c_i-1$ 时，只需要将 $s$ 中的值等于 $c_i$ 的段的左端点的 $c_i$ 改为 $c_i-1$ 即可。
+因为最多有 $n$ 个非 $0$ 的 $c_i$，故初始时用 $n$ 个 $0$ 填充 $s$ 即可(用 $0$ 填充可以将插入操作转化为修改操作)。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXC=2e5+5,Inf=1e9;
+int blk_sz,a[MAXN],lst_a[MAXN],cnt[MAXC],cl[MAXN],cr[MAXN],s[MAXN];
+int ans[MAXN],qn,pn,lef=1,rig=0;
+struct query{
+	int l,r,k,t,idx;
+	bool operator < (const query &b)const{
+		if(l/blk_sz!=b.l/blk_sz)return l<b.l;
+		if(r/blk_sz!=b.r/blk_sz)return ((l/blk_sz)&1)?(r<b.r):(r>b.r);
+		return ((r/blk_sz)&1)?(t<b.t):(t>b.t);
+	}
+}q[MAXN];
+struct opt{
+	int pos,cur,next;
+}p[MAXN];
+void add(int v){
+	int c=cnt[v];
+	s[cr[c]]++;
+	cl[c+1]=cr[c];
+	if(!cr[c+1])cr[c+1]=cl[c+1];
+	cr[c]--;
+	if(cl[c]>cr[c])cl[c]=cr[c]=0;
+	cnt[v]++;
+}
+void del(int v){
+	int c=cnt[v];
+	s[cl[c]]--;
+	cr[c-1]=cl[c];
+	if(!cl[c-1])cl[c-1]=cr[c-1];
+	cl[c]++;
+	if(cl[c]>cr[c])cl[c]=cr[c]=0;
+	cnt[v]--;
+}
+void update(opt &p){
+	if(lef<=p.pos&&p.pos<=rig){
+		del(p.cur);
+		add(p.next);
+	}
+	a[p.pos]=p.next;
+	swap(p.cur,p.next);
+}
+int main()
+{
+	int n=read_int(),m=read_int();
+	blk_sz=pow(n,2.0/3)+1;
+	_rep(i,1,n)
+	a[i]=lst_a[i]=read_int();
+	_for(i,0,m){
+		int op=read_int();
+		if(op==1){
+			qn++;
+			int l=read_int(),r=read_int(),k=read_int();
+			q[qn].l=l,q[qn].r=r,q[qn].k=k,q[qn].t=pn,q[qn].idx=qn;
+		}
+		else{
+			pn++;
+			int pos=read_int(),v=read_int();
+			p[pn].pos=pos,p[pn].cur=lst_a[pos],p[pn].next=(lst_a[pos]=v);
+		}
+	}
+	sort(q+1,q+qn+1);
+	cl[0]=1,cr[0]=n;
+	_rep(i,1,n)cl[i]=cr[i]=0;
+	int tim=0;
+	_rep(i,1,qn){
 		while(lef>q[i].l)add(a[--lef]);
 		while(rig<q[i].r)add(a[++rig]);
@@ 行 211: / 行 345: @@
 		while(tim<q[i].t)update(p[++tim]);
 		while(tim>q[i].t)update(p[tim--]);
-		ans[q[i].idx]=cur_ans;
+		int cur=Inf,lpos=cr[0]+1,rpos=cr[0];
+		while(lpos<=n){
+			while(rpos<n&&rpos-lpos+1<q[i].k)rpos=cr[s[rpos+1]];
+			if(rpos-lpos+1>=q[i].k)cur=min(cur,s[rpos]-s[lpos]);
+			lpos=cr[s[lpos]]+1;
+		}
+		ans[q[i].idx]=cur==Inf?-1:cur;
 	}
-	_for(i,0,q_cnt)
+	_rep(i,1,qn)
 	enter(ans[i]);
 	return 0;
@@ 行 219: / 行 359: @@
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

页面工具