算贡献

https://codeforces.com/contest/2065/problem/H 题目大意 给出一个 $01$ 字符串 $s$ 和 $q$ 次询问，每次询问将 $v_i$ 位置的字符翻转（询问不独立），之后询问这个串由下述函数算出的值是多少。 $f(S)$ 表示 $S$ 由多少个连续的相同字符的段，比如 $00110001$ 有 $00, 11, 000, 1$ 这样的 $4$ 段。 $g(S)$ 表示对于 $S$ 的 …

https://codeforces.com/contest/903/problem/D 题目大意 给出 $n \ (\le 2 \times 10^5)$ 长的数组 $a$ 其中 $1 \le a_i \le 10^9$。定义函数 $d$ 如下 $$ d(x, y) = \left\{ \begin{align} y - x, \quad & |x - y| > 1, \\ 0, \quad & |x - y| \le 1 \end{align} \right. $$ 求 $$ \sum_i \sum_{j = i}^{n} d(a[i], a[j]) $$ 简要题解 注意到其实特殊的只有 $a[i] = a[j] \pm 1$ （等于虽然是 case …

https://codeforces.com/contest/1996/problem/E 题目大意 给出 $01$ 串 $S$，长度 $\le 2 \cdot 10^5$。求其所有子串的 $01$ 个数相同的子串的个数。 简要题解 题目求 $\sum_l \sum_r \sum_x \sum_y [cnt0(x, y) == cnt1(x, y)] ,\ (1 \le l \le x \le y \le r \le n)$。 如果只有所有子串 $S(x, y)$ 的个数，那将非常好求。遇到 $0$ 就 $ …