2017-Personal2-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 * A
  * 题意等价于找到一个最大的子矩阵满足子矩阵的中位数>=h（若有偶数个数字，取第n／2大的数字为中位数）。对于矩阵中每个数字，若>=h，则置为1，否则-1。问题转化为找最大的矩阵和>=0的子矩阵。枚举上下边界，得到前缀和s，问题转化为找到满足 i<j，s[i]≤s[j]的max(j−i)，对于s[i]，显然当i递增时s[i]递减，否则显然不优。s[j]同理。处理出两个单调的数组，各一个指针统计答案即可。
 * B
  * 可持久化线段树，区间取 min ，只有单点询问所以标记不用下传。
 * C
  * 通过map和并查集把两棵树共有的边缩成一个点，然后对于第一棵树，从叶子结点开始找到向父亲连的边删掉，在第二棵树中找到相应的点向父亲连的边连起来。
 * D
  * 区间第k大裸题。
 * E
  * 对于操作2，建立新点，把原来的点的贡献去掉。其他的操作并查集即可。
 * F
  * 用可持久化线段树维护并查集数组，按秩合并。
 * G
  * @sub
 * H
  * 每个点对祖先的贡献是自己的值乘上走到祖先一路上的孩子数的积。线段树维护每个点对根节点的贡献，节点u的答案就是子树u对跟节点的贡献除掉u对根节点的倍数。离线建树。
 * I
  * 将一条路径视为，从u出发，以u到v的某个节点为重点。问题转化为最少的互相不交叉的路径覆盖整棵树。DP。f[u]表示u这棵子树加上u到父亲的边都覆盖的最小代价。用某棵子树出来的路径加上别的子树的答案更新这个点的答案，注意维护这个点开始的路径的加入和这个点结束的点的删除。
 * J
  * 罚时最多不超过4000，开10棵树状数组和10*4000个set，按题意维护即可。
 * K
  * 整体二分。
 * L
 * M
  * 同K。
 * N
  * 先对树进行树链剖分，用两棵主席树分别维护果子数和每根树枝的剩余载重能力的区间最小值。维护果子总数的主席树较为简单，下面主要说明如何维护最小值树。由于内存原因，不能进行标记下放，于是如下进行处理：
   * 区间修改：将标记打在区间上，update时取左右儿子的最小值-本节点的tag
   * 区间还原到初始状态：一开始建立初始状态的线段树，还原时直接复制初始线段树的对应节点，同时在从根下来的过程中记录tag的和，在还原的节点上反作用tag。
   * 查找是否存在会断的树枝：在由根向下的过程中将tag加进将要增加的重量中，到目标区间后如果最小值<当前将要增加的重量则会断。
  • A
    • 题意等价于找到一个最大的子矩阵满足子矩阵的中位数>=h（若有偶数个数字，取第n／2大的数字为中位数）。对于矩阵中每个数字，若>=h，则置为1，否则-1。问题转化为找最大的矩阵和>=0的子矩阵。枚举上下边界，得到前缀和s，问题转化为找到满足 i
  • B
    • 可持久化线段树，区间取 min ，只有单点询问所以标记不用下传。
  • C
    • 通过map和并查集把两棵树共有的边缩成一个点，然后对于第一棵树，从叶子结点开始找到向父亲连的边删掉，在第二棵树中找到相应的点向父亲连的边连起来。
  • D
    • 区间第k大裸题。
  • E
    • 对于操作2，建立新点，把原来的点的贡献去掉。其他的操作并查集即可。
  • F
    • 用可持久化线段树维护并查集数组，按秩合并。
  • G
    • @sub
  • H
    • 每个点对祖先的贡献是自己的值乘上走到祖先一路上的孩子数的积。线段树维护每个点对根节点的贡献，节点u的答案就是子树u对跟节点的贡献除掉u对根节点的倍数。离线建树。
  • I
    • 将一条路径视为，从u出发，以u到v的某个节点为重点。问题转化为最少的互相不交叉的路径覆盖整棵树。DP。f[u]表示u这棵子树加上u到父亲的边都覆盖的最小代价。用某棵子树出来的路径加上别的子树的答案更新这个点的答案，注意维护这个点开始的路径的加入和这个点结束的点的删除。
  • J
    • 罚时最多不超过4000，开10棵树状数组和10*4000个set，按题意维护即可。
  • K
    • 整体二分。
  • L
  • M
    • 同K。
  • N
    • 先对树进行树链剖分，用两棵主席树分别维护果子数和每根树枝的剩余载重能力的区间最小值。维护果子总数的主席树较为简单，下面主要说明如何维护最小值树。由于内存原因，不能进行标记下放，于是如下进行处理：
      • 区间修改：将标记打在区间上，update时取左右儿子的最小值-本节点的tag
      • 区间还原到初始状态：一开始建立初始状态的线段树，还原时直接复制初始线段树的对应节点，同时在从根下来的过程中记录tag的和，在还原的节点上反作用tag。
      • 查找是否存在会断的树枝：在由根向下的过程中将tag加进将要增加的重量中，到目标区间后如果最小值<当前将要增加的重量则会断。