差别

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

--- 2020-2021:teams:legal_string:jxm2001:cdq分治 [2020/07/29 17:50]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:cdq分治 [2020/07/30 15:29] (当前版本)
jxm2001
@@ 行 7: / 行 7: @@
 ===== 算法例题 =====
-==== 点对问题 ====
+==== 点对统计 ====
 [[https://www.luogu.com.cn/problem/P3810|洛谷p3810]]
@@ 行 223: / 行 223: @@
 </hidden>
-==== $\text{dp}$ 优化 ====
+==== 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>
 ===== 算法练习 =====
@@ 行 343: / 行 480: @@
 === 题解 ===
-将时间作为第一维，$x$ 坐标作为第二维，$y$ 坐标作为第三维，将插入的点记为第一类点，查询的点记为第二类点。
+将时间作为第一维，$x$ 坐标作为第二维，$y$ 坐标作为第三维，将插入的点和初始点记为第一类点，查询的点记为第二类点。
 对每个第二类点 $(u_t,u_x,u_y)$，先考虑所有满足 $v_t\lt u_t,v_x\le u_x,v_y\le u_y$ 的第一类点。
@@ 行 460: / 行 597: @@
 	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

用户工具

站点工具

差别

页面工具