题解p9580 round game

来一发 $O(\log n)$ 线性空间的解法。 考虑通过只维护线段树叶子节点的虚树的方法压缩空间，考虑记录下每个节点的编号，然后通过异或完求最低位的 $1$ 的方式求出 LCA 的深度，然后记录下 LCA 右端点的编号。在回收节点的时候可以释放储存右端点编号的空间，但是这里为了方便就不这样做了。 ......

考虑设计一个哈希函数 $hash(x) = f(x) \times base^x$。 其中 $f(x)$ 表示 $\sum_{j=1}^{i-1} [j #define int unsigned long long #define lowbit(x)(x&(-x)) using namespace ......

真的卡不动了，但是我感觉我的思路还是有一些价值的，就来写一篇题解吧。 考虑使用回滚莫队（不增）来维护，当区间删去一个点时相当于全局加入一条边，这个询问的本质是询问是否是二分图，所以考虑扩展值域并查集，这里使用路径压缩加按秩合并，记录下修改，在回滚时全部还原。 总复杂度是 $O(n \sqrt n \ ......

先考虑这个式子： $\sum_{j=1}^{M} |C_{k_{j}} - C_{k_{j+1}}|$ 一定是在 $C$ 有序时取到，具体证明很简单各位读者自己证明。 那么现在式子变成： $\sum{V} + 2 \times({C_{\max} - C_{\min}})$ 这个时候一个常见的技巧是 ......

[放一个比赛链接](https://uoj.ac/contest/85) 先考虑打完暴力后 $k = 1$ 的特殊性质。 当队列容量为 $1$ 时，队中的人 $i$ 会被第一个满足 $i \leq j$ 且 $b_i \leq a_j$ 的人淘汰，并且队列中的人会变成 $j$，考虑倍增加速这个过程， ......

[problem](https://www.luogu.com.cn/problem/CF1438F) & [blog](https://www.cnblogs.com/liangbowen/p/17563234.html)。 神秘随机题。 众所周知： > $(u,v)$ 的 LCA 是所有点 $i ......

# A. Vika and Her Friends 枚举所有的点，判断是否存在点与Vika的距离和其他 k 个人的距离的奇偶性不同。 ```cpp #include using namespace std; #define int long long const int mod = 99824435 ......

20230718 [传送门](https://www.luogu.com.cn/problem/P5228 "传送门") 发现$a_i$和$n$都很小 也就是说我的面值最大是$10^5$ 这样最大面值就可以用来做下标 其实最开始也不知道怎么做 我们现在考虑dp $dp[i]$表示最大面值为$i$时的 ......

看到同机房的好哥们发了贪心做法的题解，心血来潮就A了这道题写了真·dp的题解。 虽然方法比老师上课讲的麻烦的多，并不是最优解，但至少是我自己思考得出的结果。 ## 题目要求 输入一个原序列 $a_i$，从 $a_i$ 中求得某个区间 $[l,r]$。 此区间经过题面中所描述的修改操作（任何元素 $+ ......

# P6835 [Cnoi2020] 线形生物题解 ## 题目描述 求从 $1$ 到 $n+1$ 的链的期望，其中有 $m$ 条返祖边：$u->v$ 这条边 $u\ge v$，**等概率**，求期望 ## Solution 这种爬楼梯的题一般求解 $E(x\rightarrow x+1)$，则最后答 ......

历史版本线段树；扫描线：区间的所有子区间 trick ## Problem 给长为 $n$ 的排列 $a,b$。$Q$ 次询问 $L,R$，回答这个东西： $$\sum_{L\leq l\leq r\leq R}maxa(l,r)maxb(l,r)$$ 其中 $maxa(l,r)=\max_{l\l ......

[Building Bridges](https://www.luogu.com.cn/problem/P4655) ### 题目大意 连接两根柱子 $i,j$ 的代价是 $(h_i-h_j)^2+\sum\limits_{k=j+1}^{i-1}w_k$，连接具有传递性，求将 $1,n$ 连接的最 ......

[Peaceful Teams](https://www.luogu.com.cn/problem/AT_abc310_d) ### 题目大意 将 $n$ 个人分成 $T$ 组，要求每组不能包含敌对的人，问有多少种分法。 ### 思路分析 注意到 $n,T$ 均很小，考虑爆搜。 注意到直接枚举会枚举 ......

Codeforces Round 885 (Div. 2) A - Vika and Her Friends 思路：移动后再判断，所以距离为奇数时朋友永远抓不到她 #include<bits/stdc++.h> using namespace std; #define int long long t ......

# A. Telephone Number 找到第一个 8 ```cpp #include using namespace std; #define int long long const int mod = 998244353; #define mp make_pair void solve() ......

## D - Chocolate（博弈论） 12分钟过题。签到。 ## K - Subdivision（图论、搜索） 1小时21分过题，签到。如果给定的是一棵树的话，新增的点一定位于连接叶子节点的那条边上、否则就是已有的点。然而这是一张图，所以我们可以使用 $\tt bfs$ 将其近似的转化为一棵树 ......

### B - Performance（贪心、排序） 23分过题。打卡题，差分+排序。 ### A - Code Lock（图论、搜索） 37分由队友单人过题。打卡题，将序列转化为图上问题，随后维护每一个环上相同元素的距离。 ### D - Company Network（树论、倍增、数据结构） 2 ......

[ T312819 命题工作 ](https://www.luogu.com.cn/problem/T312819) 直接容斥。 总方案 - 一题出现四次 - 一题出现三次 - 一题出现两次。 一题出现两次的情况略有不同，注意考虑周全。 复杂度 $O(n)$。 [code](https://www. ......

换根 DP。 本蒟蒻最初没想到换根，把自己写自闭了... 定义 $f_u$ 为子树 $u$ 中的每个结点走到 $u$ 的贡献和，$l_u$ 为大于 $a_u$ 的最小的 $10$ 的幂次方数，$sum_u$ 为 $\sum\limits_{v\in son(u)}{f_v}$。 转移方程为：$f_u ......

不难推理出当初始绳长为 $len$，需要下降的距离为 $d$，并且满足 $d\le lenf_j\land v_j\ge v_i\end{cases}$$ 开两棵线段树，第一棵 $t_1$ 维护 $\min(f_j)(h_j+\frac{f_j}{2}\ge h_i)$，第二棵 $t_2$ 维护 $ ......

带有小 trick 的点分治。 建议先做完 [弱化版](https://www.luogu.com.cn/problem/P4186) 再看。 假如奶牛在 $u$，那么所需的最少农夫数为 $\sum\limits_{v\in son(u)}[dis(u,v)\ge g_v][dis(u,fa_v) ......

神奇的分块。 假如没有 $2$ 操作，我们可以直接用主席树解决。 我们考虑将询问分块，每遍历完一块就将这一块内出现的所有修改更新。如果在块内，就把当前块之前的所有修改暴力算，当然只有修改的节点在询问的节点的子树内才会发生。 具体的来说，我们可以用分块维护 dfs 序，并将块内的元素排序，询问 $O( ......

## 0. 题面 ### 题目描述 高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。 邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和 ......

[toc] # 1 前言 这次的光线追踪，主要是基于 **Radiometry** 的一种实现，也就是基于物理的一种实现。本文对辐射度量学做了解释，同时给出了程序中的关键代码以及参考资料，实现了微表面模形，模形的代码正确无误，但是运用到路径追踪上会出现很强的噪声，这个项目无法解决。 # 2 辐射度量 ......

点分治。 考虑当前的分治重心的城市被完全联通。 这可以用队列接解决。每次放入一种城市，就把那些城镇的父亲加入队列，如果存在城镇不在当前分治重心的联通块内，那么说明必定存在另一个分治重心能算到它，直接退出即可。 剩下的和模板没有任何区别。 复杂度 $O(n\log n)$。 code: ```cpp ......

点分树模板题。是个神奇的算法。 点分树就是将分治重心按照层级连边，每个节点父亲的联通块都包含了当前节点的联通块，且高度为 $\log n$。可以解决不考虑树的形态的多次询问带修改的问题。 对于这道题，我们可以在点分树的每个节点上记录两棵树状数组，分别与当前节点距离为 $k$ 的节点的权值和，以及与当 ......

点分树。 本题的核心问题在于不好直接确定补给站的位置。 但是仔细思考后我们发现，对于当前节点，如果存在一个儿子的答案比它优，那么补给站一定在那个儿子的子树中。 增量为 $w\times(sum_u-2\cdot sum_v)$。当 $v$ 优于 $u$ 时，$2\cdot sum_v>sum_u$。 ......

树上带修莫队。 **带修莫队复杂度分析：** 带修莫队比普通莫队多了一个时间戳，排序的时候先排左端点，再排右端点，如果左右端点所在块对应相等，则按时间戳排序。 设区间长度为 $n$，询问数为 $q$，修改数为 $c$，块长为 $B$。 我们分别考虑时间戳、左端点和右端点的移动次数。 时间戳：对于每一 ......

这题有紫？？ 对于询问节点 $u$，倍增地跳到它的 $k$ 级祖先，求其子树内有多少深度为 $dep_u$ 的节点。 我们考虑把询问离线，再通过 dfs 序把树拍平，然后扫一遍直接求就行了。 复杂度 $O(n\log n)$。 code: ```cpp #include using namespac ......

点分治模板题。 点分治适合处理大规模的树上路径信息问题 暴力做法：dfs 每个点 $u$，算出其子树内每个点到 $u$ 的距离，统计经过 $u$ 的所有路径，复杂度 $O(n^2)$。 容易发现，复杂度和子树大小有关。 对于当前子树，我们可以求出其重心，计算经过重心的所有路径，删掉重心，递归每个联通 ......