``` 1 10 5 -14 -21 -7 20 6 -13 13 15 -24 -8 -15 -21 -1 24 -6 -20 24 2 21 8 2 14 4 24 15 8 10 -13 5 -25 20 -24 -7 -16 -19 14 8 24 9 0 0 1 0 10.9804 31.0150538747…

在文章《replace》发表评论：

Bssssm

在文章《题解：CF1399F Yet Another Segments Subset》发表评论：

Bssssm！！！

如果你TLE on #7,8,9，请注意链式前向星的空间大小（唐）

如果你20pts，且AC#1#2，那么请注意你的离线数组空间是否开够4*N。

可持久化seg长度不能仅为1e5,需要更大一点

如果最后RE #19 #20，注意输入 $A,B,C,P$。 （应该没人这么唐）

## 题意 维护一个序列，支持区间求和，区间赋值，区间加，区间复制和交换，区间翻转，**强制在线且数据不一定随机**。 ## 思路 ~~感觉用什么都可以做的样子~~ 我们将目光指向了最后一个操作：区间翻转。 这题是平衡树是跑不了了。 然后因为还需要区间复制和交换，所以就需要可持久化。 赋值，区间加，区间翻转分别记一个…

# 前置知识 **二维树状数组** 什么？你说你不会？没事，文末有讲解。 # 思路 因为只有 $30$ 个物品，且只维护奇偶性，考虑压缩状态。 用二维树状数组维护即可。 具体来说，对于第 $i$ 位，表示第 $i$ 个物品个数是否是奇数（$1$ 表示是奇数，$0$ 表示是偶数）。 如果将每次修改看做 $k$ 次修改，方…

# 题意 给定序列 $a$，$q$ 组询问给定 $L,R$，求 ${\rm popcount}(\sum_{i=L}^{R}2^{a_i})$。 其中 $n \le 1 \times 10^5,q \le 1 \times 10^6$。 # 思路 ## First ~~由 Ynoi 和没有强制在线，猜出是莫队不过分吧……

在文章《[ABC373G] No Cross Matching 题解》发表评论：

%%%

在文章《P4598 [HEOI2012] Akai 的数学作业 题解》发表评论：

%%%

在文章《P4902 乘积 题解》发表评论：

%%%

在文章《P1791 [国家集训队] 人员雇佣 题解》发表评论：

网络流大佬

在文章《P1791 [国家集训队] 人员雇佣 题解》发表评论：

%%%

在文章《P6357 [COCI 2007/2008 #3] REDOKS 题解》发表评论：

%%%

在文章《P3454 [POI 2007] OSI-Axes of Symmetry 题解》发表评论：

%%%

在文章《P8576 「DTOI-2」星之界 题解》发表评论：

%%%

# 思路 ## First 很容易得到一个 $O(n \log n)$ 的做法。从 $1$ 到 $n$ 枚举每个点 $i$，如果硬币朝下，则将 $i$ 的倍数全部翻转。 ## Second 设 $f_i$（只有 $0$ 和 $1$ 两种取值，或者说为一个 `bool`）表示第 $i$ 个硬币是否需要翻转。 容易得到 $…

## 思路 ### First 注意到 $1 \le x_i,y_i \le 500$ 且为整数，考虑从此处入手。 用一个 `vector[505][505]` 存储每个点圆的半径，并将同一个 `vector` 里半径从小到大排序。 ### Second 考虑如何查询每个点上的圆到某条线段的**距离**是否小于等于半径…

## 思路 第一眼看过去以为是[最优贸易](https://www.luogu.com.cn/problem/P1073)。 注意到 $X_i q; for(i=1;i<=n;i++) { if(deg[i]==0) q.push(i); } while(q.size()) { int x=q.front(); q.p…

~~第一篇黑体题解，好兴奋~~ ## 题意 $T$ 组数据，给定 $N,M,A,B_1,B_2$，求 $$ \sum_{i=0}^{N-1} \left[(Ai+B_1) \bmod M \right] \left[ (Ai+B_2) \bmod M \right] $$ 其中 $0 \le A,B_1,B_2 #de…

如果你80分，WA on #1,2,3,8，可能是因为某些地方没有输出换行。 ~~最唐氏的错误~~

## 题意 卒从 $(1,1)$ 出发，可以向令 $x+1$，或 $y+1$，或 $x+1$ 并且 $y+1$。棋盘上有一些地方不可到达，求到达 $(n+1,m+1)$ 的方案数（原文不是这样的，但是转化之后是的）。 ## 思路 首先考虑没有障碍时怎么做。 设 $dp_{i,j}$ 表示在没有障碍的情况下，到达 $(i…

在文章《AT_abc400_g [ABC400G] Patisserie ABC 3 题解》发表评论：

%%%

## 题意 给定一颗树，几对好点 $\{\langle u_1, v_1 \rangle, \langle u_2, v_2 \rangle, \dots, \langle u_a, v_a \rangle\}$ 和一个坏点对 $\langle b_u, b_v \rangle$。$\langle u_i, v_i \…

## 思路 **期望 DP。** 分成撞不撞墙两种可能。 设 $Arrive_{i,j}$ 表示从 $(1,1)$ 出发，走 $i+j-2$ 步，到达 $(i,j)$ 的概率。 则撞墙的期望就是 $x \times (1-Arrive_{i,j})$。 接下来考虑不撞墙的情况。 如果直接 DP，比较困难。因为是异或操作…

## **前置知识：** [李超线段树](https://www.luogu.com.cn/problem/P4097)。 ## 本题思路 显然发出的噪音就是两段线段。 首先考虑**没有降噪设备**的时候怎么做。 发现其实就是李超线段树板子题（甚至只有没有精度差）。 加上降噪设备之后，每段线段就会再次“分裂”（~~就像…

## 题目注意 尝试后跳板**不再视为**跳板。 ## 思路 首先，要求任意一个出发的期望，其实也就是求从每个点出发，最短时间期望的平均值。 不妨设 $dp_i$ 表示起点为 $i$ 的最短时间期望，$Fail_i$ 表示 $i$ 为起点，跳失败的概率。 分成三种情况： - 如果 $i=1$，则 $Fail_i = 1…

## 思路 ### First ~~一眼 DP。~~ ### Second 设 $dp_i$ 表示对于前 $i$ 个位置，选择第 $i$ 个位置的答案最小值。 考虑如何转移。 可以想象转移方程的样子大概是 $dp_i = \min_{j=Left_i}^{Right_i} dp_j + a_i$，且显然 $Right_…