qbxt 10 月 Day6 讲课

BZOJ1112

肯定都变成中位数。

维护两个 multiset 分别维护前一半大和后一半大。记录一下和。

POJ 2777

注意到颜色数量才 $30$，所以可以直接维护区间或。

HDU 2795

对于每一行都记录一下还剩多少，线段树二分。

POJ 3667

维护前缀 $0$ 后缀 $0$ ，区间最长 $0$ 的长度，修改的时候线段树二分到区间即可。

CF 365D

出现偶数次数的数的异或和 = 所有数只算一次的异或和 异或上 出现奇数次数的异或和。

后面的很好算，等价于区间异或和：偶数都被消去了。

前面的可以离线+线段树或者是直接主席树。离线维护每个左端点的答案就行了。

CF 460C

二分答案，那么从小往大枚举每个区间，一直到必须要浇水的时候浇水（指区间左端点 $< ans$），这其实可以用差分维护。

CF Gym100739A

首先区间异或和，做前缀和后转化为求某个区间内任意两个点的异或和的和。

也就是求形如 $\sum_{i=l}^r \sum_{j=i+1}^r (sm_i \text{ xor }sm_j)$。

肯定按位考虑，相当于要求区间有多少对 $(i,j)$ 满足 $i<j$ 并且 $a_i \neq a_j$（这里因为拆位了，所以 $a_i,a_j \in \{0,1\}$ 。

这个线段树维护一个 $0$ 和 $1$ 的个数，合并的时候用左边的 $0$ 乘右边的 $1$ 加上左边的 $0$ 乘右边的 $1$ 就好了。

维护下区间取反即可。

CF 396D

字典序问题，先枚举上界卡到哪一位，然后只要保证下一位小于上界，后面就可以乱填了。

设和上界相等的是前缀 $i$ ，现在逆序对分三种：$i$ 前缀内部的贡献，剩下的后缀的贡献，前缀和后缀之间的贡献。

$i$ 前缀内部的贡献求逆序对即可。

前缀和后缀的贡献：和前后内部的顺序无关，所以用树状数组维护前后缀有哪些值，类似维护即可。

后缀内部的贡献：相当于是限制了第一位要小于某个数，我们可以先对于每个数维护处没有用过的数中有多少个比它小的，然后通过查前缀和就可以知道这个有限制的位置对后面的贡献。之后就是后面没有限制之间的贡献，相当于是考虑长度为 $n$ 的所有排列的逆序对个数，每一对都有一半的可能成为逆序对，所以是 $\binom n 2 \frac{n!}{2}$。

其实你发现有限制的那一位形如只能填前 $k$ 小，相当于是个等差数列求和。（第一小 $0*m!$，第二小 $1*m!$，第三小 $2*m!$...）

POJ 3017

设 $f_i$ 表示考虑划分前 $i$ 个的答案，转移就是 $f_i = \min_j (f_j+\max_{k=j+1}^ia_k)$。

观察到 $f_i$ 是单调不降的，我们只会从每个后缀最大值变动的地方转移而来。

所以用单调栈维护，然后再用个 multiset 维护一下所有可能的值，操作次数均摊是 $O(n)$ 的，总复杂度 $O(n \log n)$。