2020-2021:teams:legal_string:jxm2001:cdq分治
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:cdq分治 [2020/07/29 22:27] jxm2001 |
2020-2021:teams:legal_string:jxm2001:cdq分治 [2020/07/30 15:29] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| ===== 算法例题 ===== | ===== 算法例题 ===== | ||
| - | ==== 点对问题 ==== | + | ==== 点对统计 ==== |
| [[https://www.luogu.com.cn/problem/P3810|洛谷p3810]] | [[https://www.luogu.com.cn/problem/P3810|洛谷p3810]] | ||
| 行 223: | 行 223: | ||
| </hidden> | </hidden> | ||
| - | ==== dp 优化 ==== | + | ==== DP优化 ==== |
| [[https://www.luogu.com.cn/problem/P2487|洛谷p2487]] | [[https://www.luogu.com.cn/problem/P2487|洛谷p2487]] | ||
| 行 480: | 行 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$ 的第一类点。 | 对每个第二类点 $(u_t,u_x,u_y)$，先考虑所有满足 $v_t\lt u_t,v_x\le u_x,v_y\le u_y$ 的第一类点。 | ||
| 行 604: | 行 604: | ||
| ==== 习题三 ==== | ==== 习题三 ==== | ||
| - | [[https://www.luogu.com.cn/problem/P3206|洛谷p3206]] | + | [[https://www.luogu.com.cn/problem/P4093|洛谷p4093]] |
| === 题意 === | === 题意 === | ||
| - | 给定一个图，图中每条边有一个初始边权。$q$ 次操作，每次操作修改一条边的边权。 | + | 给定一个长度为 $n$ 的序列以及 $m$ 个变换。 |
| - | 要求输出 $q$ 个数，第 $i$ 个数表示经过前 $i$ 次修改后的最小生成树的边权和。 | + | 每个变化可以将位置 $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> | ||
2020-2021/teams/legal_string/jxm2001/cdq分治.1596032844.txt.gz · 最后更改: 2020/07/29 22:27 由 jxm2001
