xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共4篇）

2019南昌网络赛 J Distance on the tree 主席树+lca

题意给一颗树，每条边有边权，每次询问\(u\)到\(v\)的路径中有多少边的边权小于等于\(k\) 分析在树的每个点上建\(1\)到\(i\)的权值线段树，查询的时候同时跑\(u,v,lca(u,v)\)三个版本的线段树，查询\(1\)到\(k\)的树上差分和\(val[u]+...

主席树 LCA

2019-05-23

0 412

2019icpc南京网络赛 F 主席树

题意给一个\(n\)的全排列数组\(a\)，求一个递推数组每一项的值：\(ans[i]=ans[j]+1\)，\(j\)为\(a[pos[i]-k]到a[pos[i]+k],(pos[i]为i在数组a中的下标)\)中小于\(i\)的最大的值。分析这题set的做法更优秀，但是想练习一下在主...

主席树

2019-09-01

0 371

2019icpc南京网络赛 A 主席树

题意给一个\(n\times n\)的螺旋矩阵，给出其中的\(m\)个点的值分别为各个点上数字的数位之和，给出\(q\)个询问，每次询问从\((x1,y1)\)到\((x2,y2)\)的子矩阵的和。分析用官方题解的方法\(O(1)\)推出点\((x,y)\)上的值，将这\(m\)个点按\...

主席树

2019-09-01

0 336

2019南昌网络赛 J Distance on the tree 主席树+lca

题意给一颗树，每条边有边权，每次询问\(u\)到\(v\)的路径中有多少边的边权小于等于\(k\) 分析在树的每个点上建\(1\)到\(i\)的权值线段树，查询的时候同时跑\(u,v,lca(u,v)\)三个版本的线段树，查询\(1\)到\(k\)的树上差分和\(val[u]+...

主席树 LCA

2019-05-23

0 386