差别

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

--- 2020-2021:teams:legal_string:jxm2001:cdq分治 [2020/07/29 10:25]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:cdq分治 [2020/07/30 15:29] (当前版本)
jxm2001
@@ 行 3: / 行 3: @@
 ===== 算法简介 =====
-一种离线处理多维偏序问题的算法，算法效率明显优于树套树和 KD_Tree。
+一种利用分治解决问题的算法思想，时间复杂度一般为 $O(n\log^2 n)$。
-===== 算法模板 =====
+===== 算法例题 =====
+==== 点对统计 ====
 [[https://www.luogu.com.cn/problem/P3810|洛谷p3810]]
-==== 题意 ====
+=== 题意 ===
-三维空间中给定 $n$ 个点，编号为 $1 \sim n$。定义 $f[i]$ 表示恰好有 $i$ 个元素满足 $x_i\le x_j,y_i\le y_j,z_i\le z_j$ 且 $i\ne j$ 的 $j$ 的个数。
+三维空间中给定 $n$ 个点，编号为 $1 \sim n$。
+定义 $f[i]$ 表示恰好有 $i$ 个元素满足 $x_i\le x_j,y_i\le y_j,z_i\le z_j$ 且 $i\ne j$ 的 $j$ 的个数。
 要求输出 $f[0 \sim n-1]$。
-==== 题解 1 ====
+=== 题解 1 ===
 先考虑所有元素互异的情况。
@@ 行 29: / 行 33: @@
 需要注意每轮分治完成后需要重置树状数组，考虑再次减去左区间贡献，不能暴力重置。
-最后也可以发现，这样不会遗漏任何贡献。关于重复元素，最后特殊处理一下即可。
+最后也可以发现，这样不会遗漏任何贡献。关于重复元素，最后特殊处理一下即可。时间复杂度 $O(n\log n\log v)$。
-总时间复杂度 $O(n\log n\log v)$。
 <hidden 查看代码>
@@ 行 114: / 行 116: @@
 </hidden>
-==== 题解 2 ====
+=== 题解 2 ===
 考虑两次嵌套 $\text{CDQ}$ 分治来解决上述问题。
@@ 行 220: / 行 222: @@
 </code>
 </hidden>
+==== DP优化 ====
+[[https://www.luogu.com.cn/problem/P2487|洛谷p2487]]
+=== 题意 ===
+给定一个序列，每个元素有两个属性 $x,y$，求最长不增子序列长度。定义 $a\ge b\iff a_x\ge b_x \land a_y\ge b_y$。
+假定存在若干个最长二维不增子序列，系统将从中随机选择一个序列，问每个元素被选取的概率。
+=== 题解 ===
+先考虑 $O(n^2)$ 算法。
+容易想到 $\text{dp}$ 出以每个元素为结尾和每个元素为开头的最长不增子序列长度和方案数。
+由此可以得到题目所求最长不增子序列长度和相应的方案数。
+对某个元素，如果以其结尾的最长不增子序列长度 $+$ 以其开头的最长不增子序列长度 $-1\lt$ 答案，则该元素被选中概率为 $0$。
+否则，该元素被选中的方案数为以其结尾的最长不增子序列方案数 $\times$ 以其开头的最长不增子序列方案数。
+用该元素被选中的方案数除以总方案数即可得到该元素被选择概率。
+先考虑 $\text{dp}$ 求以每个元素结尾的最长不增子序列的过程，发现这也是个偏序问题，可以转化为考虑左区间对右区间的贡献。
+接下来考虑中序遍历方式使用 $\text{CDQ}$ 分治，这样可以保证按顺序递推出每个 $\text{dp}$ 值。
+对于以每个元素开头的最长不增子序列，考虑颠倒序列，再次使用 $\text{CDQ}$ 分治。
+时间复杂度优化为 $O(n\log^2 n)$。
+<hidden 查看代码>
+<code cpp>
+typedef pair<int,double> pr;
+const int MAXN=5e4+5;
+const pr zero=make_pair(0,0.0);
+struct Node{
+	int a,b,id;
+}node[MAXN],temp[MAXN];
+int n,m;
+pr dp[2][MAXN],c[MAXN];
+pr Merge(const pr &a,const pr &b){
+	if(a.first!=b.first)return a.first>b.first?a:b;
+	return make_pair(a.first,a.second+b.second);
+}
+#define lowbit(x) ((x)&(-x))
+void add(int pos,pr v){
+	while(pos<=m){
+		c[pos]=Merge(c[pos],v);
+		pos+=lowbit(pos);
+	}
+}
+void del(int pos){
+	while(pos<=m){
+		c[pos]=zero;
+		pos+=lowbit(pos);
+	}
+}
+pr query(int pos){
+	pr ans=zero;
+	while(pos){
+		ans=Merge(ans,c[pos]);
+		pos-=lowbit(pos);
+	}
+	return make_pair(ans.first+1,ans.second);
+}
+bool cmp1(const Node &x,const Node &y){
+	return x.a<y.a;
+}
+bool cmp2(const Node &x,const Node &y){
+	return x.a>y.a;
+}
+void cdq1(int lef,int rig){
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	cdq1(lef,mid);
+	_rep(i,lef,rig)temp[i]=node[i];
+	sort(temp+lef,temp+mid+1,cmp2);sort(temp+mid+1,temp+rig+1,cmp2);
+	int pos1=lef,pos2=mid+1;
+	while(pos1<=mid&&pos2<=rig){
+		if(temp[pos1].a>=temp[pos2].a)add(temp[pos1].b,dp[0][temp[pos1].id]),pos1++;
+		else dp[0][temp[pos2].id]=Merge(dp[0][temp[pos2].id],query(temp[pos2].b)),pos2++;
+	}
+	while(pos1<=mid)add(temp[pos1].b,dp[0][temp[pos1].id]),pos1++;
+	while(pos2<=rig)dp[0][temp[pos2].id]=Merge(dp[0][temp[pos2].id],query(temp[pos2].b)),pos2++;
+	_rep(i,lef,mid)del(temp[i].b);
+	cdq1(mid+1,rig);
+}
+void cdq2(int lef,int rig){
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	cdq2(lef,mid);
+	_rep(i,lef,rig)temp[i]=node[i];
+	sort(temp+lef,temp+mid+1,cmp1);sort(temp+mid+1,temp+rig+1,cmp1);
+	int pos1=lef,pos2=mid+1;
+	while(pos1<=mid&&pos2<=rig){
+		if(temp[pos1].a<=temp[pos2].a)add(temp[pos1].b,dp[1][temp[pos1].id]),pos1++;
+		else dp[1][temp[pos2].id]=Merge(dp[1][temp[pos2].id],query(temp[pos2].b)),pos2++;
+	}
+	while(pos1<=mid)add(temp[pos1].b,dp[1][temp[pos1].id]),pos1++;
+	while(pos2<=rig)dp[1][temp[pos2].id]=Merge(dp[1][temp[pos2].id],query(temp[pos2].b)),pos2++;
+	_rep(i,lef,mid)del(temp[i].b);
+	cdq2(mid+1,rig);
+}
+int a[MAXN],b[MAXN];
+int main()
+{
+	n=read_int();
+	_for(i,0,n){
+		node[i].a=read_int(),node[i].b=read_int(),node[i].id=i;
+		a[i]=node[i].a,b[i]=node[i].b;
+	}
+	sort(a,a+n);sort(b,b+n);
+	int t1=unique(a,a+n)-a,t2=unique(b,b+n)-b;
+	_for(i,0,n)
+	node[i].a=upper_bound(a,a+t1,node[i].a)-a,node[i].b=upper_bound(b,b+t2,node[i].b)-b;
+	m=max(t1,t2)+1;
+	_for(i,0,n)dp[0][i]=dp[1][i]=make_pair(1,1.0);
+	_for(i,0,n)node[i].b=m-node[i].b;
+	cdq1(0,n-1);
+	for(int l=0,r=n-1;l<r;l++,r--)swap(node[l],node[r]);
+	_for(i,0,n)node[i].b=m-node[i].b;
+	cdq2(0,n-1);
+	pr ans=zero;
+	_for(i,0,n)
+	ans=Merge(ans,dp[0][i]);
+	enter(ans.first);
+	_for(i,0,n){
+		if(dp[0][i].first+dp[1][i].first-1==ans.first)
+		printf("%.5lf ",dp[0][i].second*dp[1][i].second/ans.second);
+		else
+		printf("%.5lf ",0.0);
+	}
+	return 0;
+}
+</code>
+</hidden>
 ===== 算法练习 =====
 ==== 习题一 ====
+[[https://www.luogu.com.cn/problem/P3157|洛谷p3157]]
+=== 题意 ===
+给定一个 $1\sim n$ 的排列，依次删除 $m$ 个元素，要求输出每次删除前序列中的逆序对数。
+=== 题解 ===
+考虑第一维为位置，第二维为权值，第三维为时间，$\text{CDQ}$ 分治维护即可。
+需要注意左区间可以对右区间贡献，右区间也可以对左区间贡献，考虑在分治过程中同时维护。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXV=5e4+5;
+struct Node{
+	int a,b,id;
+}node[MAXN],temp[MAXN];
+int n,m,c[MAXN],ans[MAXN];
+#define lowbit(x) (x)&(-x)
+struct BIT{
+	int c[MAXV];
+	void add(int pos,int v){
+		while(pos<=m){
+			c[pos]+=v;
+			pos+=lowbit(pos);
+		}
+	}
+	int query(int pos){
+		int ans=0;
+		while(pos){
+			ans+=c[pos];
+			pos-=lowbit(pos);
+		}
+		return ans;
+	}
+}tree1,tree2;
+void cdq(int lef,int rig){
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	cdq(lef,mid);cdq(mid+1,rig);
+	int pos1=lef,pos2=mid+1,pos3=lef;
+	while(pos1<=mid&&pos2<=rig){
+		if(node[pos1].a<=node[pos2].a){
+			tree1.add(node[pos1].b,1);
+			temp[pos3++]=node[pos1++];
+		}
+		else{
+			ans[node[pos2].id]+=tree1.query(node[pos2].b);
+			temp[pos3++]=node[pos2++];
+		}
+	}
+	while(pos1<=mid){
+		tree1.add(node[pos1].b,1);
+		temp[pos3++]=node[pos1++];
+	}
+	while(pos2<=rig){
+		ans[node[pos2].id]+=tree1.query(node[pos2].b);
+		temp[pos3++]=node[pos2++];
+	}
+	_rep(i,lef,mid)tree1.add(node[i].b,-1);
+	pos1=mid,pos2=rig;
+	while(pos1>=lef&&pos2>mid){
+		if(node[pos2].a>=node[pos1].a)tree2.add(node[pos2].b,1),pos2--;
+		else ans[node[pos1].id]+=tree2.query(node[pos1].b),pos1--;
+	}
+	while(pos2>mid)tree2.add(node[pos2].b,1),pos2--;
+	while(pos1>=lef)ans[node[pos1].id]+=tree2.query(node[pos1].b),pos1--;
+	_rep(i,mid+1,rig)tree2.add(node[i].b,-1);
+	_rep(i,lef,rig)node[i]=temp[i];
+}
+int pos[MAXN],t;
+int main()
+{
+	n=read_int(),m=read_int();
+	for(int i=n;i;i--)
+	node[i].a=read_int(),pos[node[i].a]=i;
+	LL sum=0;
+	_rep(i,1,n){
+		int k=node[i].a;
+		while(k)sum+=c[k],k-=lowbit(k);
+		k=node[i].a;
+		while(k<=n)c[k]++,k+=lowbit(k);
+	}
+	for(int i=m;i;i--){
+		t=read_int();
+		node[pos[t]].b=i,node[pos[t]].id=m+1-i;
+	}
+	_rep(i,1,n)node[i].b++;
+	m++;
+	cdq(1,n);
+	_for(i,1,m){
+		enter(sum);
+		sum-=ans[i];
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 习题二 ====
 [[https://www.luogu.com.cn/problem/P4169|洛谷p4169]]
@@ 行 236: / 行 480: @@
 === 题解 ===
+将时间作为第一维，$x$ 坐标作为第二维，$y$ 坐标作为第三维，将插入的点和初始点记为第一类点，查询的点记为第二类点。
+对每个第二类点 $(u_t,u_x,u_y)$，先考虑所有满足 $v_t\lt u_t,v_x\le u_x,v_y\le u_y$ 的第一类点。
+显然这些点对答案的贡献为 $u_x+u_y-\max(v_x+v_y)$，问题转化为三维偏序问题，考虑使用树状数组维护。
+而对于其他的第一类点，可以将坐标系分别翻转 $3$ 次，转化为上述情况。
+另外发现一开始 $n$ 个第一类点一定满足 $v_t\lt u_t$，考虑单独处理优化算法效率。
+时间复杂度 $O(4(n\log n+m\log m\log v))$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=6e5+5,MAXV=1e6+5,Inf=1e9;
+struct Node{
+	int a,b;bool flag;
+	bool operator < (const Node &y)const{
+		if(a!=y.a)return a<y.a;
+		return b<y.b;
+	}
+}node[MAXN],node2[MAXN];
+int m,ans[MAXN],c[MAXV];
+int Id[MAXN],temp[MAXN];
+#define lowbit(x) (x)&(-x)
+void add(int pos,int v){
+	while(pos<=m){
+		c[pos]=max(c[pos],v);
+		pos+=lowbit(pos);
+	}
+}
+void del(int pos){
+	while(pos<=m){
+		c[pos]=0;
+		pos+=lowbit(pos);
+	}
+}
+int query(int pos){
+	int ans=0;
+	while(pos){
+		ans=max(ans,c[pos]);
+		pos-=lowbit(pos);
+	}
+	return ans;
+}
+void cdq(int lef,int rig){
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	cdq(lef,mid);cdq(mid+1,rig);
+	int pos1=lef,pos2=mid+1,pos3=lef;
+	while(pos1<=mid&&pos2<=rig){
+		if(node2[Id[pos1]].a<=node2[Id[pos2]].a){
+			if(node2[Id[pos1]].flag)add(node2[Id[pos1]].b,node2[Id[pos1]].a+node2[Id[pos1]].b);
+			temp[pos3++]=Id[pos1++];
+		}
+		else{
+			if(!node2[Id[pos2]].flag)ans[Id[pos2]]=max(ans[Id[pos2]],query(node2[Id[pos2]].b));
+			temp[pos3++]=Id[pos2++];
+		}
+	}
+	while(pos1<=mid){
+		if(node2[Id[pos1]].flag)add(node2[Id[pos1]].b,node2[Id[pos1]].a+node2[Id[pos1]].b);
+		temp[pos3++]=Id[pos1++];
+	}
+	while(pos2<=rig){
+		if(!node2[Id[pos2]].flag)ans[Id[pos2]]=max(ans[Id[pos2]],query(node2[Id[pos2]].b));
+		temp[pos3++]=Id[pos2++];
+	}
+	_rep(i,lef,mid)if(node2[Id[i]].flag)del(node2[Id[i]].b);
+	_rep(i,lef,rig)Id[i]=temp[i];
+}
+int f[MAXN];
+void cal(int mid,int rig){
+	int pos1=0,pos2=mid+1;
+	sort(node2,node2+mid+1);
+	while(pos1<=mid&&pos2<=rig){
+		if(node2[pos1].a<=node2[Id[pos2]].a)
+		add(node2[pos1].b,node2[pos1].a+node2[pos1].b),pos1++;
+		else{
+			if(!node2[Id[pos2]].flag)ans[Id[pos2]]=max(ans[Id[pos2]],query(node2[Id[pos2]].b));
+			pos2++;
+		}
+	}
+	while(pos1<=mid)add(node2[pos1].b,node2[pos1].a+node2[pos1].b),pos1++;
+	while(pos2<=rig){
+		if(!node2[Id[pos2]].flag)ans[Id[pos2]]=max(ans[Id[pos2]],query(node2[Id[pos2]].b));
+		pos2++;
+	}
+	_rep(i,0,mid)del(node2[i].b);
+	_rep(i,0,rig){
+		if(ans[i])f[i]=min(f[i],node2[i].a+node2[i].b-ans[i]);
+		node2[i]=node[i],Id[i]=i,ans[i]=0;
+	}
+}
+int main()
+{
+	int n=read_int(),nn=read_int()+n;
+	m=0;
+	_for(i,0,n){
+		node2[i].a=read_int()+1,node2[i].b=read_int()+1;
+		m=max(m,max(node2[i].a,node2[i].b));
+	}
+	_for(i,n,nn){
+		node2[i].flag=read_int()&1,node2[i].a=read_int()+1,node2[i].b=read_int()+1;
+		Id[i]=i,ans[i]=0,f[i]=Inf;
+		m=max(m,max(node2[i].a,node2[i].b));
+	}
+	m++;
+	_for(i,0,nn)node[i]=node2[i];
+	cdq(n,nn-1);cal(n-1,nn-1);
+	_for(i,0,nn)node2[i].a=m-node2[i].a;
+	cdq(n,nn-1);cal(n-1,nn-1);
+	_for(i,0,nn)node2[i].b=m-node2[i].b;
+	cdq(n,nn-1);cal(n-1,nn-1);
+	_for(i,0,nn)node2[i].a=m-node2[i].a,node2[i].b=m-node2[i].b;
+	cdq(n,nn-1);cal(n-1,nn-1);
+	_for(i,n,nn)if(f[i]!=Inf)enter(f[i]);
+	return 0;
+}
+</code>
+</hidden>
+==== 习题三 ====
+[[https://www.luogu.com.cn/problem/P4093|洛谷p4093]]
+=== 题意 ===
+给定一个长度为 $n$ 的序列以及 $m$ 个变换。
+每个变化可以将位置 $x$ 的数变成 $y$，求最长不降子序列，且该子序列满足最多一次变换下仍为不降子序列。
+=== 题解 ===
+考虑状态转移方程，记 $dp_i$ 表示以位置 $i$ 的数结尾的满足上述条件的最长子序列，$l_i$ 为位置 $i$ 的最小可能值，$r_i$ 为位置 $i$ 的最大可能值。
+于是有 $dp_i=\max(dp_j+1)(j\lt i,r_j\le a_i,a_j\le l_i)$，$\text{CDQ}$ 分治即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+struct Node{
+	int a,l,r,id;
+}node[MAXN],temp[MAXN];
+int mv,dp[MAXN],c[MAXN];
+#define lowbit(x) ((x)&(-x))
+void add(int pos,int v){
+	while(pos<=mv){
+		c[pos]=max(c[pos],v);
+		pos+=lowbit(pos);
+	}
+}
+void del(int pos){
+	while(pos<=mv){
+		c[pos]=0;
+		pos+=lowbit(pos);
+	}
+}
+int query(int pos){
+	int ans=0;
+	while(pos){
+		ans=max(ans,c[pos]);
+		pos-=lowbit(pos);
+	}
+	return ans;
+}
+bool cmp1(const Node &x,const Node &y){
+	return x.r<y.r;
+}
+bool cmp2(const Node &x,const Node &y){
+	return x.a<y.a;
+}
+void cdq(int lef,int rig){
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	cdq(lef,mid);
+	_rep(i,lef,rig)temp[i]=node[i];
+	sort(temp+lef,temp+mid+1,cmp1);sort(temp+mid+1,temp+rig+1,cmp2);
+	int pos1=lef,pos2=mid+1;
+	while(pos1<=mid&&pos2<=rig){
+		if(temp[pos1].r<=temp[pos2].a)add(temp[pos1].a,dp[temp[pos1].id]),pos1++;
+		else dp[temp[pos2].id]=max(dp[temp[pos2].id],query(temp[pos2].l)+1),pos2++;
+	}
+	while(pos1<=mid)add(temp[pos1].a,dp[temp[pos1].id]),pos1++;
+	while(pos2<=rig)dp[temp[pos2].id]=max(dp[temp[pos2].id],query(temp[pos2].l)+1),pos2++;
+	_rep(i,lef,mid)del(temp[i].a);
+	cdq(mid+1,rig);
+}
+int main()
+{
+	int n=read_int(),m=read_int(),x,y;
+	_rep(i,1,n)
+	node[i].a=node[i].l=node[i].r=read_int(),node[i].id=i,dp[i]=1;
+	while(m--){
+		x=read_int(),y=read_int();
+		node[x].l=min(node[x].l,y);
+		node[x].r=max(node[x].r,y);
+	}
+	_rep(i,1,n)
+	mv=max(mv,node[i].r);
+	cdq(1,n);
+	int ans=0;
+	_rep(i,1,n)
+	ans=max(dp[i],ans);
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具