标签：月度做题记录
2024 年 8 月做题记录
为了防止版权纠纷，部分内容已修改或匿名化。 0818A 大意是给你一个数组，然后每次查询给区间加上/减去一个固定数值（保证修改后数组严格单调递增），查询是否包含一个下标等于值的数（即 ai=ia_i = iai=i）。 然后发现 ai−ia_i - iai−i 也是单调的，然后可以打懒标记（我用的线段树）然后二分。 struct Sg { struct { int lz, val; } tr[MAXN * 4]; void build(int l, int r, int p = 1); [...]
2024/09 做题笔记
不行了，语言开始变机械化了 TAT 还有几道题没写完 [POI2015] PUS / Pustynia 给定一个长度为 nnn 的正整数序列 aaa，每个数都在 111 到 10910^9109 范围内，告诉你其中 sss 个数，并给出 mmm 条信息，每条信息包含三个数 l,r,kl,r,kl,r,k 以及接下来 kkk 个正整数 tit_iti，表示 al,al+1,…,ar−1,ara_l, a_{l+1}, \ldots, a_{r-1}, a_ral,al+1,…,ar−1,a [...]
2024/10 做题笔记
呜呜呜好多题都没来得及写。你说得对但是我 CSP-S 炸了 [Internal] 1 给你一堆边，区间和区间对应点相连（x→y,(x+1)→(y+1),…,(x+k)→(y+k)x \to y, (x+1)\to (y+1), \dots, (x+k)\to (y+k)x→y,(x+1)→(y+1),…,(x+k)→(y+k)），求这张图的最小生成树。 区间数量 5e5，节点数 1e5。 暴力来做的话，就是直接建一个并查集然后 merge。写一个启发式合并可以把暴力时间优化很多，但是还是过不了。 [...]