。。。
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
在讨论《求值域倍增分块好题》回复：
ZYPRESSEN
[例题 $1$](https://www.luogu.com.cn/problem/P4097) >在平面直角坐标系下维护 $n$ 次操作： > >1. 在平面上加入一条线段。 >2. 给定数 $k$，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大线段的编号。 > >强制在线。 > >$1 \le n \le…
线段树合并听起来十分高端，但其实非常好理解。 对于两个维护区间和的线段树 $T_1,T_2$ 的合并，大致如下图：  其实就是将两棵线段树的相同位置的信息合并。假设我们仍要使用 $T_1$ 存储…
 https://www.luogu.me/article/xpu213se 具体哪里不行呢》》
对于一颗 $n$ 个结点的树，以下无特殊说明时没有边权，有边权时一般非负。所以有边权的情况在无边权的情况下同样适用。仿照重链剖分，考虑以下定义： 长儿子：一个结点的所有儿子中，子树深度最大的儿子。 长链：连续的长儿子组成的链。 使用两次 dfs，第一次处理结点深度、长儿子等信息，第二次处理长链信息、dfn 序等。注意第…
[例题 $1$](https://www.luogu.com.cn/problem/P4097) >在平面直角坐标系下维护 $n$ 次操作： > >1. 在平面上加入一条线段。 >2. 给定数 $k$，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大线段的编号。 > >强制在线。 > >$1 \le n \le…
在讨论《求助 DS》回复：
是不是就是 P5073
在讨论《萌新求问简单数据结构题》回复：
为什么要说这么好心眼的话？ 直接上 trie 好像确实甲烷了。 $O(n \sqrt{V})$ 是不是按高低位划分，然后低位处理所有加一的情况，高位加一同样。不过这样可以在线
在讨论《萌新求问简单数据结构题》回复：
但是 $a_i \oplus b_i$ 好像不可维护？
在讨论《萌新求问简单数据结构题》回复：
@[hsaht2426](luogu://user/342567) 条件变为 $a_i \oplus (b_i+y)=x$。 将询问挂在 $y$ 上扫描线，每次对 $b$ 全局加一。 用 trie 维护即可 $O((n+q)\log V)$。
在讨论《哇，我只比nq多了一个log，能拿多少啊？》回复：
直接分治不是可以过 ABDE 吗
该变量不应为空。 ## 11.26 20min 一发通过了树上查询，非常舒适。 然后遗失的赋值和种花看了好久才会？ ## 11.28 随便写的代码拿下了 [risrqnis](https://www.luogu.com.cn/article/x3mwztql) 的最优解。爽爽。 NOIP 一等线怎么这么高。唉唉。 ##…
对于 $m=1$ 的情况，任意发现每个 $a_i$ 只会被加入集合一次。上个 ODT 考虑新增数，随便做做即可，但是一定要 $\mathcal{O}(q \log n)$ 不然过不了。 对于一般情况，考虑对集合操作次数阈值分治，设阈值为 $B$。 - 对于操作次数 $>B$ 的集合： 这种集合至多存在 $\mathca…
环，直接将 $l>r$ 的询问拆成两个询问做即可。 考虑到一次询问后，若有过交换，$x$ 一定是区间最大值。 说明区间中的最大值被取出，$x$ 被丢进去了。 如果询问都是全局的，可以发现其实我们连 $x$ 被放在哪里都不关心，只需维护一个大根堆就可以做。 考虑分块。类比全局，整块是简单的。但是散块我们需要知道元素的顺序…
环，直接将 $l>r$ 的询问拆成两个询问做即可。 考虑到一次询问后，若有过交换，$x$ 一定是区间最大值。 说明区间中的最大值被取出，$x$ 被丢进去了。 如果询问都是全局的，可以发现其实我们连 $x$ 被放在哪里都不关心，只需维护一个大根堆就可以做。 考虑分块。类比全局，整块是简单的。但是散块我们需要知道元素的顺序…
在讨论《求数据结构好题》回复：
P5314 P5609 P6109 P9058 P11831 P12082 P12084
设 $a_i=\mathrm{dep}_{\mathrm{LCA}^{*}(i,i+1)}$。对于 $l<r$，可以发现 $$\mathrm{dep}_{\mathrm{LCA}^{*}(l,r)}=\min_{i=l}^{r-1}a_i$$ 我们令 $r \gets r-1,k \gets k-1$。 于是问题变为求…
在讨论《FHQ Treap 怎么求解区间某个数的出现次数》回复：
离线的话，可以直接做到线性
区间查询某值域内的顺序对数。 对于所有点 $(i,a_i)$ 建立平面直角坐标系如下：  现在我们要计算部分 $(1,2,3,4)$ 的答案 $s_{1,2,3,4}$。 可以变为 $s_{1,…
在讨论《求助二进制警报器实现问题》回复：
@[Felix72](luogu://user/553659)
在讨论《求助二进制警报器实现问题》回复：
每个警报器重构 $O(\log V)$ 次 每次重构 ```cpp for(int i = 0; ; ++i) { long long sum = 0; for(int x : fact[c[ID].p]) sum += get_next(a[x] + 1, (1ll << i)); if(sum <= c[ID].l…
因为 $n \ge 2$，所以翻倍带来的贡献显然比加一要大。 所以要尽可能选翻倍，共有 $k=\min _{i=1}^{n}\lfloor \log_2\dfrac{b_i}{a_i} \rfloor$ 次。 在翻倍 $k$ 次的情况下考虑，每个 $a_i$ 距离达到 $b_i$ 还有 $(b_i-2^{k}a_i)$…
在讨论《求紫色数据结构好题》回复：
https://www.luogu.com.cn/problem/P7603
直接做是困难的。 记 $L_x,R_x$ 为上一个与下一个与 $s_x$ 相同的位置。不存在则分别记为 $1$ 和 $n$。 钦定一个终点 $x$，考虑其他点跳到 $x$ 的步数。 对于可以一步到达 $x$ 的点。显然，其位于 $[L_x,R_x]$ 中。 对于可以两步到达 $x$ 的点。其可以一步走进 $[L_x,R…
首先 $\cfrac{\operatorname{lcm}(a,b)}{\gcd(a,b)}=\cfrac{ab}{\gcd^2(a,b)}$。 故当 $\gcd(a,b)$ 一定时，$ab$ 最小会使原式最小。 考虑使用线段树维护。那么对一个结点赋值时，我们就要考虑区间中的 $b$ 与 $x$ 构成最小值。 而 $\…
简单题。 首先 $| S\cup T| = |S|+|T|-|S\cap T|$。考虑求 $|S\cap T|$ 即可。 对于每种颜色的出现次数阈值分治，设阈值为 $B$。 对于出现次数 $\ge B$ 的颜色，只有 $\mathcal{O}(n/B)$ 个，开个 bitset 跑暴力即可做到 $\mathcal{O}…
在讨论《S组T2》回复：
不过这个复杂度本地大样例只跑了 90ms
实现了 https://www.luogu.com.cn/problem/P8569 的 $O(n)$ 做法。 但是跑得非常慢，大概在暴力 20 到 30 倍时间。 所以很可能是复杂度假了。 ```cpp #include #define vr vector #define in signed #define int…