数据结构
「Luogu 2801」教主的魔法-分块
· ✏️ 459 words · ☕ 1 mins read

给定一个长度为 N 的数列,每次一个操作或询问:

  • 把闭区间 [L,R] 内的数全部加上一个整数 W
  • 问闭区间 [L,R] 内有多少英雄身高大于等于 C

「NOI2012」魔幻棋盘-差分+树套树
· ✏️ 1480 words · ☕ 3 mins read

将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘,它是一个 NM 列的网格棋盘,每个格子中均有一个正整数。棋盘守护者在棋盘的第 X 行第 Y 列(行与列均从 1 开始编号)并且始终不会移动。棋盘守护者会进行两种操作:

  1. 询问:他会以自己所在位置为基础,向四周随机扩展出一块大小不定的矩形区域,向你询问这一区域内所有数的最大公约数是多少。

  2. 修改:他会随意挑选棋盘上的一块矩形区域,将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友,当你连续答对 19930324 次询问后会得到一个惊喜噢!”。小 Q 十分想得到这个惊喜,于是每天都在玩这个玩具。但由于他粗心大意,经常算错数,难以达到这个目标。于是他来向你寻求帮助,希望你帮他写一个程序来回答棋盘守护者的询问,并保证 100 的正确率。

为了简化问题,你的程序只需要完成棋盘守护者的 T 次操作,并且问题保证任何时刻棋盘上的数字均为不超过 2621 的正整数。


「APIO2008」免费道路-生成树+并查集
· ✏️ 496 words · ☕ 1 mins read

给定一个 n 个点,m 条边的无向图,每条边有两种权值: 0 或者 1

先询问能不能找出一个生成树,使得其中恰有 k0 边,若存在,输出任意一个方案,否则输出 no solution


「SHOI2016」随机序列-线段树
· ✏️ 919 words · ☕ 2 mins read

你的面前有 n 个数排成一行,分别为 a1,a2,,an 。你打算在每相邻的两个 aic和 ai+1 间都插入一个加号、减号或者乘号。那么一共有 3n1 种可能的表达式。

你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了,所以你还打算支持一个修改操作,可以修改某个 ai 的值。

你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗?注意,修改是永久的,也就是说每次修改都是在上一次修改的基础上进行,而不是在最初的表达式上进行。


「ZJOI2012」小蓝的好友-Treap
· ✏️ 1673 words · ☕ 4 mins read

简单版题意:

给定一个 R×C 的矩形,在其中 N 个位置有随机生成的资源点。现在请你求出在所有的子矩形中,至少包含一个资源点的矩形数量。


「ZJOI2012」网络-LCT
· ✏️ 949 words · ☕ 2 mins read

有一个无向图 G ,每个点有个权值,每条边有一个颜色。这个无向图满足以下两个条件:

  • 对于任意节点连出去的边中,相同颜色的边不超过两条。
  • 图中不存在同色的环,同色的环指相同颜色的边构成的环。

在这个图上,你要支持以下三种操作:

  • 修改一个节点的权值。
  • 修改一条边的颜色。
  • 查询由颜色 c 的边构成的图中, u 到节点 v 之间的简单路径上的节点的权值的最大值。

对于 100% 的数据,保证颜色不多于 10 种。


「POI2011」Tree Rotations-线段树合并
· ✏️ 1677 words · ☕ 4 mins read

现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有 n 个叶子节点,满足这些权值为 1n 的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换,使得最终所有叶子节点的权值按照前序遍历序写出来,逆序对个数最少。


「JLOI2015」城池攻占-左偏树
· ✏️ 1104 words · ☕ 3 mins read

m 个骑士攻占 n 个城池。除 1 号城池外,城池 i 会受到另一座城池 fi 的管辖,其中 fi<i。也就是说,所有城池构成了一棵有根树。第 i 个骑士的初始战斗力为 si,第一个攻击的城池为 ci

每个城池有一个防御值 hi,如果一个骑士的战斗力大于等于城池的生命值,那么骑士就可以占领这座城池;否则占领失败,骑士将在这座城池牺牲。占领一个城池以后,骑士的战斗力将发生变化,然后继续攻击管辖这座城池的城池,直到占领 1 号城池,或牺牲为止。

1 号城池外,每个城池 i 会给出一个战斗力变化参数 ai;vi。若 ai=0,攻占城池 i 以后骑士战斗力会增加 vi;若 ai=1,攻占城池 i 以后,战斗力会乘以 vi。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池,不管结果如何,均不会影响其他骑士攻击这座城池的结果。

对于每个城池,输出有多少个骑士在这里牺牲;对于每个骑士,输出他攻占的城池数量。


「APIO2012」派遣-左偏树
· ✏️ 627 words · ☕ 2 mins read

给定一棵有根树,每个点有一个代价 Ci ,权值 Li ,要求从这个树某个节点 k 的子树(包含该节点)选取若干个节点,使得选取节点的个数乘上节点 k 的权值最大,且这若干个节点的代价和不超过给定的限制 M


左偏树学习笔记
· ✏️ 1101 words · ☕ 3 mins read

左偏树是一种以二叉树为基础的数据结构,可以用来实现可以在O(logn)时间内合并的堆。


「IOI2014」Wall-线段树
· ✏️ 409 words · ☕ 1 mins read

给定一个长度为 n 且初始值全为 0 的序列。你需要支持以下两种操作:

  • Add,L,R,h :将序列 [L,R] 内所有值小于 h 的元素都赋为 h,此时不改变高度大于 h 的元素值
  • Remove,L,R,h:将序列 [L,R] 内所有值大于 h 的元素都赋为 h ,此时不改变高度小于 h 的元素值

你需要输出进行 k 次上述操作之后的序列。


「NOI2014」魔法森林-LCT
· ✏️ 1210 words · ☕ 3 mins read

给定一个 n 个点 m 条边的无向图,每条边有两个权值 ai,bi 。请你找到一条从 1n 的道路,令道路上所有边的集合为 S ,使 ans=max(ai)+max(bj),i,jS 最小,求出这个最小值 ans


「CQOI2011」动态逆序对-CDQ分治
· ✏️ 973 words · ☕ 2 mins read

对于序列 A ,它的逆序对数定义为满足 i<j ,且 Ai>Aj 的数对 (i,j) 的个数。
给出一个 1n 的排列,按照某种顺序依次删除 m 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。


「ZJOI2013」K大数查询-整体二分
· ✏️ 941 words · ☕ 2 mins read

N 个位置, M 个操作。

操作有两种:

  • 如果是 1 a b c 的形式表示在第 a 个位置到第 b 个位置,每个位置加入一个数 c
  • 如果是 2 a b c 形式,表示询问从第 a 个位置到第 b 个位置,第 c 大的数是多少。

「LNOI2014」LCA-树链剖分-差分
· ✏️ 933 words · ☕ 2 mins read

给出一个 n 个节点的有根树。有 q 次询问,每次询问给出 l,r,z ,求 lirdep[LCA(i,z)]