- 11.4号这个只有一个上午的时间来着，晚上和中午我被弄去搞WHK了/jk
vp 第十七场 - T1 评分：绿
- 直接秒了，倒着弄+并查集即可(用时20min)
- T2 评分：蓝
- 这个我经过了一系列的思考才得出解法来着
- 首先我先观察到了 \(k_i \cdot t + b_i\) 这个式子在 \(t\) 变大的时候有些 \(k_i > \frac{A}{t}\) 是不能用了的，我很快的发现这是一个调和级数 \(N \log{N}\) 的形式
- 此时我的脑海中蹦出了一个枚举 \(k\) 的值再枚举 \(t\) 的值的想法 然后我发现当 \(k_i \cdot t\) 是固定的时候我们需要统计的是 \(b_i \equiv -k_i \cdot t (\mod a_t)\) 的数量
- 很显然我们无法对每个 \(t\) 都把这些数去统计一遍，这样的复杂度是不优的
- 这里我是过了比较久才想到根号分治的 （大概20min左右？
- 对于每个 \(k\) 中的数
- 我们先枚举它的模数 \(1 - B\)，拿一个全局变量记录模 \(i\) 等于 \(j\) 的 \(b_i\) 个数
- 拿一个全局变量 \(dis_i\) 表示 \(b_j = i\) 的 \(b_j\) 的个数
- 对于小于等于 \(B\) 的 \(a_t\) 则直接查表
- 对于大于 \(B\) 的 \(a_t\) 则我们把式子变成 \(b_i = -k_i \cdot t + c \cdot a_t\) 故可以枚举 \(c\) 从 \(1\) 到 \(\frac{A}{a_t}\) 然后计数即可
- 对于复杂度则是 \(O(A \log{A} \cdot \frac{A}{B} + N \cdot B)\)
- 则是让 \(A \log{A} \cdot \frac{A}{B} = N \cdot B\)
- 则最后的复杂度即为 \(O(N \sqrt{n \log{A}})\)
- 总用时1h30min
- T3 评分：蓝+紫-
- 完全是一道发现性质的题目啊/jk
- 法一(纯发现性质)
- 首先我们考虑枚举右端点 \(r\) 考虑在右端点为 \(r\) 的情况下有哪些点会被标记到
- 考虑有三种点
- 两次出现都在 \(r\) 左边的点，那么只有靠右边的那个点有可能 \(r\) 会对它产生贡献
- 两次出现都在 \(r\) 右边的点，那么 \(r\) 不可能会对它产生贡献
- 一次出现在 \(r\) 左边一次出现在 \(r\) 右边的点，\(r\) 可能对左边的那个点产生贡献
- 考虑有三种点
- 如果只考虑 \(r\) 对第三种情况产生的贡献的话，把序列反转后再做一次则能保证左或右端点会把每个点的贡献算上，不重不漏
- 但是对于第三种情况而言只可能对左边的点中离 \(r\) 最近的第三类点产生贡献，这个可以从左往右枚举 \(r\) 节点，然后维护一个栈不符合条件的弹出即可，然后我们可以对每一个数赋随机权，定义 \(sum_i\) 为前 \(i\) 个数权值的异或和，设离当前节点最近的数为 \(x\) 则查询 \(sum_j = sum_r \oplus a_x\) 的 \(j\) 个数。
- 首先我们考虑枚举右端点 \(r\) 考虑在右端点为 \(r\) 的情况下有哪些点会被标记到
- 法二（暴力线段树大法，很有锻炼套路思维能力的作用）
- 维护一个区间中出现次数为1的元素数量
- 将区间 \((l,r)\) 视为平面直角坐标系上的点，每种元素的贡献形如两个矩形+1
- 一个位置的答案即为一个矩形中元素值为1的数量
- 考虑有效的区间的长度一定是奇数，且值 >= 1，故可以分别维护奇偶区间最小值及其历史和就能维护
- T4
