第五场¶
没想到赛程已经过半了
平均成绩距离平均水平依然很远
今天带了 kuangbin 的板子，vagrt 看了看计算几何说：有向四面体都有？
然后今天的二维计算几何考了个《工程测量》什么控制点碎部点当场 PTSD
赛后也是讨论和思考了一下学算法到底是学思想还是学模板
| Rank | Author | Solved | Penalty | 1001 42/286 | 1002 70/558 | 1003 548/4161 | 1004 93/441 | 1005 4/75 | 1006 119/1212 | 1007 270/1594 | 1008 26/272 | 1009 9/86 | 1010 789/2292 | 1011 25/127 | 1012 669/3172 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 408 | team1157 四川大学 | 2 | 05:00:48 | (-4) | 02:49:41 | 02:11:07 |
1001 Pandaemonium Asphodelos: The First¶
题意：给定 \(n\) 个砖块，每个砖块一个权值，初始都为 \(0\)。\(q\) 次操作：
- \(\mathtt{1}\ x\ c\)：对区间 \([x-c，x+c]\) 的砖块赋予一个新的属性，与原属性共存
- \(\mathtt{2}\ x\ y\)：将 \(x\) 的属性复制到 \(y\) 以及 \(y\) 相邻、连续、同属性的最长砖块段上
- \(\mathtt{3}\ x\ v\)：对属性与第 \(x\) 块相同的砖块的权值增加 \(v\)
- \(\mathtt{4}\ x\)：输出第 \(x\) 块砖块的权值
操作 \(1\) 中新属性直接记作询问的 \(id\) 即可。
- 开一个数组 \(tag\) ，用于维护属性的权重
- 开一个珂朵莉树，用于维护砖块属性
- 开一个线段树，用于维护砖块权重
那么，操作 \(3\) 只需要将 \(tag\) 中对应属性的权值加上 \(v\) 即可
操作 \(1， 2\) 修改区间属性时，先在珂朵莉树上裂开区间，当一个区间被赋予新属性时，将原属性贡献减去新属性贡献存入线段树中，即在时间上进行差分
特别的，对于操作 \(2\) 修改属性后，有可能珂朵莉树上裂开的区间左右段还有属性相同的区间，需要进行合并
对于操作 \(2\) 只需要对线段树进行单点查询，并加上属性 \(tag\) 存储的权值即可，注意到这里的 \(n\) 很大，应当进行动态开点。
1005 3D Puzzles¶
三维精确覆盖。
我盯着精确覆盖 DLX 的模板看了半点硬是没看出是个板子来，
看了看题解，标程基本和 kuangbin 的模板一样。