• 2020.07.12 2020牛客暑期多校训练营（第一场） pro: 5/5/10 rk: 30/1216
• 2020.07.13 2020牛客暑期多校训练营（第二场） pro: 5/6/11 rk: 83/1162

无

• Atcoder AIsing Programming Contest 2020 pro: 4/5/6 rk: 765/7353
• Codeforces Round #655 (Div. 2) pro: 4/6 rk: NaN

无

无

• Codeforces Round #655 (Div. 2) pro: 4/6 rk: NAN

无

无

• Atcoder AIsing Programming Contest 2020 pro: 4/6 rk: 935/7353

• TopCoder ABBA

给出两个数 A 和 B（$1\le A, B \le 10^{16}$），可以对 A 进行若干次操作，每次操作类型如下：

• 加 1，代价为 X；
• 减 1，代价为 Y；
• 乘 $C_i$，代价为 $Z_i$ ；（$2\le C_i \le 10$）
• 平方，代价为 Q ；

最后目标是要把 A 变为 B，问最小代价是多少。

比如 这一题 和 这一题 就是这种类型的题目，想知道这类型题目的一般思路。

复习后缀数组

给定一个括号串，问有多少种不同的合法括号子串，n⇐5e5

题解：将左括号看作1，右括号看作-1，处理出一个前缀和。下面求每个位置开头的合法子串个数，即对于每一个i，求出多少$i<j<n,s.t. s_j=s_{i-1},i < = k< =j,s_k>=s_{i-1}$

​ 先处理出每种前缀和的所有位置，并通过RMQ维护区间最小值，然后在之前处理出的位置数组中二分判断最大可选的j在哪个位置。

​ 求出height，然后j的范围就是$sa_i + height_i + 1 < = j< =n$ ​ 复杂度$O(nlogn)$

无