旧题新做:从idy的视角看数据结构

时间:2021-09-22 20:07:21

  “今天你不写总结……!!!”

  额……

  还是讲我的吧。这些考试都是idy出的题。

20170121:DFS序、 ST表、线段树练习

  这是第一次考数据结构。

  Problem 1. setsum 1 second
    给你一个长度为N 的整数序列,支持两种操作:
    • modity l r val 将区间[l,r] 中的所有数修改为val
    • query l r 询问区间[l,r] 所有数的和

  分析:最简单的线段树,区间更改区间求和。但注意是更改,不是添改,sum与flag需同时覆盖。

  Problem 2. subtree 1 second
    给出一棵N 个点的有根树(以1 为根),每个点有点权,要求支持:
    • modify u x 把节点u 的点权加x
    • query u 询问u 代表的子树的点权和

  分析:DFS序,单点修改区间求和

  Problem 3. matgcd 1 second
    给出一个N M 的正整数矩阵,再给出Q 个询问:
    • query x1 y1 x2 y2:询问(x1,y1)-(x2,y2) 这个子矩形的最大公约数。

  分析:idy所说的“正解”,我现在依旧很敬畏。树套树,外面按行,行有ls,rs但也有一棵按列的树。合并时,ls的被套树与rs的被套树相合并。查询时,若行已卡入,则进入其按列树进行统计。此题无修改,若有修改,则标记需要好好讲究。但此题就是无修改,故可用ST表水过去。代码实现很暴力。

20170122:LCA 值域线段树 加 复习

  基本在树上。

  Problem 1. distance 1 second
    小庆住在一个很特别的国度里,它有N 个城市,并且只建了N -1 条双向路,但神奇的是任意两个城市都可以通过这些路连接起来。小庆最近在研究寒假的旅游计划,有时她想快速地知道两个城市之间的距离,于是找你来帮帮解决。

  分析:ST表倍增经典做法,存anc与cost。

  Problem 2. redpacket 1 second
    承上题)小漫是小庆那个国家的国王,她住在1 号城市,u 号城市如果到1 必定经过v 号城市,我们则称v 号城市管辖u 号城市(v 号城市也管辖自己)。过年了,小漫想给国家的一些城市发红包,每次她会给u 号城市管辖的每个城市发放w 的红包,有时,她也想知道某个城市或被某个城市管辖的城市一共得了多少红包。如下:
    • give u w :表示将u 号城市管辖的每个城市发w 的红包。
    • single u :表示询问u 号城市得了多少红包。
    • all u :表示询问u 号城市管辖的城市一共得了多少红包。

  分析:DFS序,简单处理。

  Problem 3. kth 1 second
    小敏有个可重集S,一开始就包含一些整数,现在有三种操作需要你执行:
    • add x 将整数数x 加到集合中
    • del x 如果集合中有整数x,则删除一个x,否则忽略本操作。
    • query k 询问这个集合中第k 小的整数数是多少

  分析:值域线段树,若不提前给出上下界,须读入离散化。

20170123:最SXBK的一次练习

  额额额额额。

  Problem 1. dcplca 1 second
    这是一道练习题,要求你们用链剖来写lca,熟悉链剖的过程。(以节点1 为根)

  分析:神奇的idy为了防止你用倍增,一定会卡O(nlog n)的内存。但是,链剖确实不难写。DFS1:siz,son,fat,dep。DFS2:top,in,out,seq。DFS2中的后三者是为了方便用线段树DFS序,一条重链上in值是连续的。

  Problem 2. treekth 1 second
    给你棵带点权树,一些询问:
    • query u v 询问节点u 和v 之间的简单路径上的点权的中位数1。

  分析:这道题才是真正SXBK的那道题。先用树链剖分(后面求LCA),再DFS建出主席树(存链值),然后用差分求出中位数。但是,就是调不出来!!!(笔者现在已经调了出来……)

  Problem 3. full 1 second
    我们来个完全版如何?
    给你棵带点权的树(以1 为根),要你完成一些操作。
    • msub u x:将u 代表的子树的点权整体加x
    • mpth u v x:将u 到v 的简单路径的点权整体加x
    • qsub u:询问子树u 的点权和
    • qpth u v:询问路径u 到v 的点权和

  分析:链剖与DFS序共存。

20170318:数据结构第1套模拟题

  是否变难了?

  Problem 1. rotinv 2 seconds 256 MB
    如果你有一个长度为n 的序列:
      a1,a2,a3,……,an
    那么它的一个逆序对是一个二元组:< i, j > 满足i < j 且ai > aj,其中i, j ∈ [1, n]。
    我们称一个序列所包含的逆序对的个数为这个序列的逆序对数。
    那么问题来了:
    我给出一个长度为n 的序列,需要你计算:

        a1,a2,a3,……,an-1,an

      a2,a3,a4,……,an,a1

              ……

        an,a1,a2,……,an-2,an-1
    这n 个序列的逆序对之和。

  分析:方法很多,但大致相似。转化为数学公式,然后用树状数组快速解决。对于这种问题的极困难版,可见BZOJ 图腾。

  Problem 2. rise 2 seconds 256 MB
    你有一堆柱子,它们竖直地并排摆放在桌子上,它们的高度分别是:

h1,h2,h3,……,hn

    你从前往后看,能够看见的柱子个数为这个柱子序列的“可见度”(能够看见柱子i 当且仅当hj < hi & j < i)。
    现在给你一个长度为n 的序列,还有m 个询问,每次询问某个区间[l,r] 的柱子单独拿出来后,其可见度是多大。

  分析:当时并没有看懂题解。后来做了一道BZOJ 楼房重建,再一看便恍然大悟。与那道题相似,但需要多存储一些东西。因为没有修改,可以充分使用此题的性质。但丁神在统计的时候,把所有线段先放入了栈,再集中处理。看似更加麻烦,但其实更加朴素,更加灵活。还有,当时很迷,于是写了个暴力(链表)水了过去。

  Problem 3. seqmod 2 seconds 256 MB
    给你一棵无根树,边有边权,且是[0,9] 之间的整数,给你m 个询问,每次询问两个点u, v 之间的路径的边的边权顺次连接起来后构成的那个数字取模于31。

  分析:题面十分易懂。链剖也很好想,但是,就像其他很多的DS题一样,你以为自己已经明白了,但还是有太多细节没有想到。为了方便合并,idy想到用struct来做到方便的合并。找路径的方式也有不同,谁深了就跳谁,最后到同一条链上进行最后的合并。每一个节点也存了2个方向,但怎样区分?很简单,按深度。

20170404:practice before 省选

  啊啊啊啊啊!

  Problem 1. setmod 2 seconds 256 MB
    给你一个序列:a1,a2,a3,……, an,有m 个操作,操作如下:
    • modify l r x  将区间[l,r] 中的每个数修改为x
    • change l r x 将区间[l,r] 中的每个数加上x
    • query l r 询问区间[l,r] 中的和

  分析:我在处理时,用了一种叫做kill的标记。因为“修改为”==“*”+“加上”。但是,这似乎有点不负责任。若+=与=标记同时作用,当然很好想。若只用一个,需用type。

  int type; // type==1 change += 改改改delta 原delta或无则++ 原value则value++ 
  dnt delta, value; // type==2 modify = 改value

  Problem 2. area  2 seconds 256 MB
    给出n 个矩形,求它们的面积并.
    更准确一点,每个矩形将给出它的左上角和右下角的位置:x1,y1, x2, y2
    这四个数都是整数且满足x1<=x2,y1<=y2.
    我们需要你求:
      area =|{ f(x, y) ∈ Z × Z | ∃ a rect. s. t. x1<=x2 and y1<=y2 }|

  分析:扫描线,标记永久化。时候不早了,明天再来。

  Problem 3. intkth 3 seconds 512 MB
    我看好你哟。
    给你一个长度为n 的序列,有m 个操作:
    • modify u x 将第u 个数修改为x
    • query l r k 询问区间[l,r] 中第k 小的数

  分析:此题很有趣。树状数组套线段树,很好实现。