XYD 2025.7.19 记录

上午讲字符串，比上次 dx 来讲听得更懂一些，可能是后缀数组什么的之前学过，但是淀粉质和淀粉树啥的之前没学。

然后上午终于把 P7446 [Ynoi2007] rfplca 给过了，之前我看那一列都过了，就缺我一个空就去写了，改了三四天还没改好，今天发现是比较

dep_u

和

dep_v

的时候比成

dep_{Fu}

和

dep_{Fv}

了，然后还有个地方少写个 else，太愚蠢了，但是交上去只有 80pts，开始卡常，加了快读，用 register int ，调块长都没用，后来预处理了 blk[] 数组，就是求每个点在哪个块里面，之前是直接算的，然后直接过了，YnOI 真的太爱卡常了（确信

下午先是调了一会儿配置，就是一个工具可以直接把样例搞到本地测试，让调试更快一些。

然后开始补前天的 T1，我用线段树分治写

\mathcal{O}(n\log^2n)

的写法，考虑每个点存在的范围是个区间，将其放在线段树上，那么对于一个叶子节点其存在的点就是他和根节点之间那条链上存在的所有点，每个点最多在线段树上多开

\log n

个点，所以空间

\mathcal{O}(n\log n)

可以接受，然后我看到一中非常好的写法就是因为你分治

[l,r]

结束之后还要还原操作的，他是这么写的

int top;
struct Opt { int *x, y; } stk[(MAXN << 6) + 5];
void push(int &x, int y) {
  stk[++top] = { &x, x };
  x = y;
}
void dc(int p, int L, int R) {
  int tmp = top;
  分治操作
  while (top != tmp) *stk[top].x = stk[top].y, top--;
}

感觉非常聪明的写法啊，非常会用指针啊，但是这个数组要开得比较大，我就是没开大越界了然后挂了。

说到这里说一下今天浅浅学习了 Linux 的 g++ -fsanitize=address 参数，非常好用

就是他可以检测数组越界，然后一下就找到哪里出问题了~~虽然绿色字下面的就看不懂了~~，还有其他种类的溢出也可以检测，非常的好用啊。

然后开始写 P3796 AC 自动机（简单版 II），调完差不多过去半个小时，开始写 P9196 [JOI Open 2016] 销售基因链 / Selling RNA Strands 差不多快 19:00 写完，突然想起来总结还没写，虽然还没调出来但是过来写总结了。19:40 又回去调题。

磨磨蹭蹭 20:00 点出头改完了，挺简单的一道数数题。

然后在写 e-Government，准备写完把精品题单的题先看一看。

好吧 20:50 前没写完。

文章操作

相关推荐

评论

XYD 2025.7.19 记录