模拟赛 19 题解

主席树+差分+二维BIT

A.斐波那契

发现 $fib\leqslant 10^9$ 时，序列的个数在 $40$ 左右。

所以可以每次枚举划分的左端点，查看是否有斐波那契数和新加的数的差为原来的数，用 $Map$ 统计。

B.序列

这题就比较神了。

首先，要求的中位数在 $[l_1,r_1]$ 范围内，可以转化为求在 $[1,l_1-1]$ 和 $[1,r_1]$ 的答案。

考虑不限制区间长度怎么做：枚举区间的右端点，看在它左边有没有符合要求的就行。

按照中位数的常见套路，**把 $\leqslant val$ 的赋值为 $1$，$\geqslant val$ 的赋 $-1$。**反过来也是一样的。

我们记 $a$ 为当前前缀大于 $val$ 的个数，$b$ 为小于的个数。差分后可以得到区间信息。

那么 比 $val$ 小的数是中位数的充要条件：$a-a'\leqslant b-b'$。因为 $val$ 变小，$a$ 只会更大

移项，$a-b\leqslant a'-b'$，设 $a-b=cnt$。

扫描到每个下标时把它们的 $cnt$ 扔进权值线段树里，每次查询比 $cnt$ 小的个数即可。

有了长度的限制，可以考虑的范围只有 $[i-r,i-l+1]$。

区间小于一个数的数，我选择主席树。

C.栅栏

挺标新立异的。

可以对子矩形进行一些操作，单点查询时判断两个点所属的矩形是否相同。

由于边界不重合，这样判断就能保证联通。

可以对子矩形整体加或异或一个值，但要保证不同矩形覆盖查询到的值时不同的，即不冲突。

这个值可以 $rand$ 出来，用 $map$ 记录每个子矩形修改的值是多少。