zhangxixi的博客

平面图欧拉公式 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134062975 V−E+P=B+1V-E+P=B+1V−E+P=B+1 VVV ：点数 EEE ：边数 PPP ：面数（含外面） BBB ：连通块数量 通过这个我们可以处理网格图中的连通块数量问题 上图中有7个点，8条边，3个面（包括外面），所以有 7-8+3=1+1 个连通块

拆贡献+统计非法可能不统计非法贡献：ARC150D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134047357 https://atcoder.jp/contests/arc150/tasks/arc150_d 先拆贡献成每个点，然后就只需要考虑这条链上的情况了 我们现在要求的是： 在所有点选完之前，最后一个点被选了多少次 我们发现这很难做，但有个性质： 在所有点选完前，最后一个点始终是坏点 因此我们可以钦定好点也可以选，只是不计算其贡献 ...

SA+ST表维护height+单调队列维护：CF1073G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134043286 https://www.luogu.com.cn/problem/CF1073G lcp相关的，先跑个sa，然后height建个ST表 现在考虑询问，我们按A和B按 rkrkrk 排序。现在考虑B->A，反过来同理。 我们可以用单调队列维护，满足height是单增的。因为越往前lcp必然越短。同时要维护有多少个。然后对于当前后缀...

后缀数组SA 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134042245 https://uoj.ac/problem/35 通过倍增实现排序 类似基数排序，先排后面，再排前面 排的过程可以拿桶排优化 设 h(i)=lcp(sa[rk[i]−1],i)h(i)=lcp(sa[rk[i]-1],i)h(i)=lcp(sa[rk[i]−1],i) 有 h(i)≥h(i−1)−1h(i)\ge h(i-1)-1h(i)≥h(i−1)−1 123...

树上形态改变统计贡献：1025T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134039125 http://cplusoj.com/d/senior/p/SS231025D 答案为 ∑w[x]−w[son[x]]\sum w[x]-w[son[x]]∑w[x]−w[son[x]] ， xxx 非儿子 要维护断边，LCT固然可以，但不一定需要 发现如果发生了变化，只会由重儿子变成次重儿子 所以我们首先要维护次重儿子 同时我们拿树状数组维护其所有祖先的...

排列置换环上构造：1025T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134035399 http://cplusoj.com/d/senior/p/SS231025C 排列构造的新知识：上置换环！ 我们发现朴素做法是 n2n^2n2 级别的，但数据范围希望我们是 n22\frac {n^2}2 2n2​ 级别的。我们发现我们暴力复制序列显得非常蠢，因为很多序列前后我们其实可以考虑合并。 至于怎么合并？我们直接维护指针。然后我们现在要“运”东西到相应...

分析性质+排列置换环+最小割：1024T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134022318 http://cplusoj.com/d/senior/p/SS231024D 相当于各选一些置换环进行一次位移 我们考虑只对A进行置换。对于一个大小>1的环，如果对其进行位移，一定可以使这些位完全不同。 因此，如果我们置换B，置换的意义是什么？是把A中自环的位置统计掉，使这些位置不同。 但如果我们再置换B，可能会和之前已经置换的A在某些地方相...

组合计数+容斥：1024T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134013962 http://cplusoj.com/d/senior/p/SS231024B?tid=653748c7611b23c4594b05ab 要么是环，要么是链，都可以有两个方向 链的话可以缩成点一起统计 长为2的链如果成二元环不应该乘2，那么考虑容斥 g(i)g(i)g(i) 表示至少有 iii 个二元环不被算错的方案数， ∑i=0kg(i)(−1)k−i\sum...

线段树维护势能类 / 均摊类问题：CF403E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134002988 https://www.luogu.com.cn/problem/CF403E 场上想对于一棵树的某个子树把所有向外边全部删掉 变成dfn序一个在子树区间，一个不在的问题 易发现这个问题可以用线段树维护 在一个点在其dfn序加入另一个点，维护区间另一个点dfn序的最大和最小值 如果不在询问区间里，直接递归 易证明均摊是 O(nlog⁡n)O(n...

枚举最大值+ds：1887D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133996658 https://codeforces.com/problemset/problem/1887/D 左边区间最大值小于右边区间最小值 肯定要离线 感觉分治？ 枚举左边区间最大值 求出其影响范围，推出左端点可取范围 然后可取右端点就是一段连续大于此值得区间 也就是左端点在一段区间时右端点可以在另一端区间取 差分一下，拿个数据结构维护即可 发现枚举最大值过程从大往小枚...