在讨论《“求区间中id仅出现一次的元素的最大权值和”问题》回复：

@[oOoOoOOOooOO](/user/42324) 是这个做法

在讨论《“求区间中id仅出现一次的元素的最大权值和”问题》回复：

@[oOoOoOOOooOO](/user/42324) 破案了，zkw线段树才能过，有点过分

给出一个长度为$n$的序列$a$，其中$a_i$代表某物品的种类 物品一共有$m$种，第$i$种物品的价值为$x_i$ 求价值最大的区间，区间的价值为，区间中仅出现$1$次的物品价值之和 其中$1 \leq m \leq n \leq 1e6$ 求助各位大佬是否存在$O(n)$算法，$O(mlogm)$的算法已经被卡掉…

在讨论《求助站外：求区间中id仅出现一次的元素的最大权值和》回复：

mlogm被卡掉了，看来存在on算法，无了

在讨论《求助站外：求区间中id仅出现一次的元素的最大权值和》回复：

@[RSGW_1e9](/user/847607) 大力线段树，这里是指有个m棵线段树吗？没太理解

给出一个长度为$n$的序列$a$，其中$a_i$代表某物品的种类，物品一共有$m$种，第$i$种物品的价值为$x_i$，求价值最大的区间，区间的价值为，出现$1$次的物品价值之和 $1 \leq m \leq n \leq 1e6$ 第一题就不会实在是太菜惹 [原题链接](https://iai.sh.cn/probl…

在讨论《求助：将含有正负数的序列按照某规则变为0问题》回复：

@[fsdgakjl](/user/115110) 非常感谢！

给出$n \leq 100000$长度的序列$a$, 其中$-10^9 \leq a \leq 10^9$，再给出两个值$1 \leq x, y \leq 10^9$，每次操作可以对序列a的一个连续子序列$+x, -x, +y, -y$，问最少操作多少次可以将该序列的每个数都变为0 原题链接：https://iai.s…

在讨论《一个理论性的问题》回复：

如果直径的长度(直径上点的个数)为奇数是可以的，你分别以2个点dfs到半径的长度为止，把这些点求到2个集合中去，这2个集合的交集就是直径的中点； 但是如果直径长度为偶数就不行，因为这个时候直径的中间点有2个；

在讨论《求助：随机生成的01串包含指定模式时长度的期望问题》回复：

@[yllcm](/user/682934) 我超级好奇为什么你没做过这题却能找到这题！

在讨论《求助：随机生成的01串包含指定模式时长度的期望问题》回复：

@[yllcm](/user/682934) 超级感谢！Thanks♪(･ω･)ﾉ

在讨论《求助：随机生成的01串包含指定模式时长度的期望问题》回复：

@[FunnyCreatress](/user/77174) (｡◕◡◕｡)ﾉ非常感谢！

在讨论《求助：随机生成的01串包含指定模式时长度的期望问题》回复：

@[Graygoo](/user/535714) 额，我看到你主页写了不要私信 大佬看到的话方便告诉我下poj的题号吗，自己思考并确认做不出前我是不会去直接搜题解的！

在讨论《求助：随机生成的01串包含指定模式时长度的期望问题》回复：

@[Graygoo](/user/535714) 谢谢大佬了！我先结合你的提示自己想一下 我关注了你，如果我还是搞不出来给你发私信！

在讨论《求助：环上最大独立集的一个问题》回复：

@[Graygoo](/user/535714) 天哪，我感觉我这几天可以不用干别的了0w0..把大佬们给的方法学一学！ 第一个人回我的说线段树维护凸包，不过他没讲太多，我也看不出是啥做法，感觉斜率优化做不了呀。。 万分感谢！！我去学习一下！(另，我刚又问了一道期望题，感觉比这题还难搞。。大佬有空可以去康康。。

以$1/2$的概率随机生成0和1，直到序列出现一个指定的模式$p$时停止 给出p，求这个01串的长度的期望 $p$的长度为$n$，$1 \leq n \leq 5e5$ 原题链接：https://iai.sh.cn/problem/599 (我又来给学术版的大佬们添麻烦了OwO..概率和期望遇到就懵了

在讨论《求助：环上最大独立集的一个问题》回复：

@[Echidna](/user/82284) 真的是双倍经验！你们都好强！

在讨论《求助：环上最大独立集的一个问题》回复：

@[WeLikeStudying](/user/260884) 谢谢！还有补充的资料，真的超级感谢！

在讨论《求助：环上最大独立集的一个问题》回复：

@[Echidna](/user/82284) or2，佩服！非常详细，太感谢了！

在讨论《求助：环上最大独立集的一个问题》回复：

@[RinkaSnow](/user/237660) 能稍微详细一点点么？我本来想用dp做，$dp[k]$代表从前$i$个数中选取$k$个能取得的最大值，但是每个$a[i]$会更新$k$个$dp[k]$，就感觉转移怎么也要$O(n^2)$级别了

给出一个长度为$n$的环状数列$a_1, a_2, ..., a_n$，选取$k$个不相邻数，使得这$k$个数之和最大 规模比较大，$2 \leq n \leq 5e5, 1 \leq k \leq n/2, 1 \leq a_i \leq 1e6$ 原题链接：https://iai.sh.cn/problem/539…

在讨论《尝试使用Dijkstra去解决带负边的图会发生什么？》回复：

@[虞皓翔](/user/10420) 有负边，无负环的场景下，你这两种情况应该均不会出现才对。

在讨论《如何证明2-SET算法的正确性》回复：

结个帖，首先感谢@Elegia和@SharpnessV的回答，correct且smart。 结合你们讲的，好像只需要证明如下结论： 在按照逆拓扑序选择元素的时，与所选元素冲突的元素不会影响后续获取集合中剩下的元素。 证明：假设某元素记作X与已经加入集合的元素冲突，则说明~X一定在所选集合中。假设不选择X会导致以后无法选…

在讨论《尝试使用Dijkstra去解决带负边的图会发生什么？》回复：

@[Light_Tracing](/user/133345) 非常感谢，很有用的回答。 结合你说的，应该还是存在负环的场景会导致先前确定了最段路的节点在随后会出现更小的值。当不存在负环，但存在负边的时候，可以使用dijkstra吗？ cc：@[AzusaCat](/user/96912)

如题。

在讨论《如何证明2-SET算法的正确性》回复：

@[ix35](/user/113546) 构造方案在处理冲突后，一定可以凑够位于不同夫妇中的n个人吗？ 比如有这样3个SCC：“A, B, C”, "~B, ~C, D", "~D, ~A"

在讨论《如何证明2-SET算法的正确性》回复：

@[SharpnessV](/user/119261) 不好意思打错了，确实是2-SAT闹笑话了。 可以证明吗？考虑仅有“A, B, C”, "~B, ~C, D", "~D, ~A"这3个SCC的情况，显然满足不存在同一个SCC中有一对夫妇，但是仍无法存在一组合法解。 当然我了解可能2-SAT模型中不会产生这样的有向…

n对夫妇出席典礼，每队夫妇仅能出席1人，并且有m对人之间有矛盾(夫妇之间不会有矛盾)，问是否可以找到一种方法能保证每对夫妇中都派出一个人参加典礼。 利用2-SET算法的解决过程为，将n对夫妇看作2n个节点，如果A与B有矛盾，则加一条A到~B的有向边，代表如果A出席，则~B必须出席；同理，也会加一条B到~A的有向边。 通…