「Summary」2022-07-06 做题记录

两天的跟线段树有关的题合到一起写。
啊啊啊啊啊啊，题都写不完，写啥题解啊。

2022-07-05

大概是听了一下怎么写 zkw 线段树，个人感觉没有递归版好写 。

$\mathbb{CF1469F}$

link
运用人类贪心本质，可以发现，先加入长链会更优，加入链条时，把重心接上去会更优。
维护一颗值域线段树就行，当白点的个数超过 $k$ 后就可以开始更新答案，只需要查询第 $k$ 小。

$\Theta(n \log_2n)$ 很可以过。 ### $\mathbb{CF452F}$

link
题目样例把做法写的很明显，找到一个中间的数 $x$，若 $\exists k$ 使得 $x - k$ 在 $x$ 前， $x + k$ 在 $x$ 后，那么就可以找到等差数列。
反着想，如果这样的 $k$ 不存在，则任意的 $k$ 都使得 $x + k$ , $x - k$ 在 $x$ 的同侧。若用 $1$ 表示在 $x$ 前出现，用 $0$ 表示在 $x$ 后出现，那么在没有等差数列时， $x + k$ ，$x - k$ 的状态时一致的。可以考虑线段树 hash 。取一个漂亮的质数就能过。

2022-07-06

$\mathbb{CF240F}$

link
这是个甚么小丑题，为啥 OnlineJudge 还要 文件io ？
做法是显然的，每个线段树上的节点维护一个桶，统计区间内 a~z 每个字母出现次数。
首先判能否构成回文串，用一个区间和就行。
考虑重构，其实就是一个区间覆盖操作。
然后我输出的时候搞忘了 push_down 。。。

$\mathbb{CF1439C}$

link
线段树二分，两个操作都是。
嗯，就这样。

$\mathbb{CF213E}$

link
写得越作，调得越恶心。
我只能说正解的代码写的很妙。
考虑序列 $a$ 是个排列，原始的值域是 $[1, n]$，全部加上一个 $\Delta$ 后，值域仍然连续，为 $[1 + \Delta, n + \Delta]$ , 想到把问题转化，如果能在 $b$ 中找到一个子序列为 $a'$ ，则 $a'$ 中的元素的相对位置在 $b$ 中是一致的。
可以把 $b$ 反向映射，考虑另一个序列 $ind$ ， $ind_i$ 表示 $i$ 在 $b$ 中的位置。也同样对 $a$ 进行这样的操作，对映射后的 $a$ hash, 同时在 $b$ 中 $[1 + \Delta, n + \Delta]$ 进行 hash，这里有一个很《妙》的写法，兼顾了离散化和 hash 。

struct SegmentTree {
	struct Node { int l, r, cnt; ULL dat; } s[MAXN << 2];
	void push_up(int p) {
		s[p].cnt = s[p << 1].cnt + s[p << 1 | 1].cnt;
		s[p].dat = s[p << 1].dat * w[s[p << 1 | 1].cnt] + s[p << 1 | 1].dat;
	}
	void build(int p, int l, int r) {
		s[p].l = l, s[p].r = r;
		if (s[p].l == s[p].r) return;
		int mid = (l + r) >> 1;
		build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
	}
	void update(int p, int pos, int val) {
		if (s[p].l == s[p].r) {
			s[p].cnt += (val > 0) ? 1 : -1;
			s[p].dat += val;
			return;
		}
		int mid = (s[p].l + s[p].r) >> 1;
		if (pos <= mid) update(p << 1, pos, val);
		else update(p << 1 | 1, pos , val);
		push_up(p);
	}
} seg;

实际写在主函数里时，就相当于一个维护了一个滑窗，因为下标的不连续，在线段树里又维护了一个 cnt ，起到了标号的作用。

$\mathbb{CF213E}$

link
这题好啊，写得我直接吐了。
这就是所谓的 rererererepos[rerererepos[rererepos[rerepos[repos[pos[]]]]]]] 吧。
如果只找一组解就是是简单题，考虑如何在一组特解的基础上找到另外一组解。
思考两点之间可以互换的条件。如果有两个点在特解中的位置是 $pos_i, pos_j$ ， 并且 $l_i \le pos_j \le r_i,l_j \le pos_i \le r_j$ ，则两个点可以互换，如果钦定 $pos_i > pos_j$ ，则可以得到 $l_i \le pos_j \le pos_i \le r_j$ ，那么对于 $i$ ，若能够找到一个 $j$ 使得 $r_j$ 在 $pos_i$ 右边且 $pos_j$ 在 $pos_i$ 左边即可，这个用线段树维护就好了。

$\mathbb{CF1539F}$

link
又一道跟中位数有关的题。
老套路依次考虑每一位，对当前位考虑，若比当前位大则定为 $1$，若比当前位小则定为 $-1$ 。
目标是使这个数离区间内的中位数比较远。
可以分情况讨论

• 如果 $a_i \ge M_e$，则要让 大于 $a_i$ 的数的个数 减 小于 $a_i$ 的数的个数 最大。
• 如果 $a_i \le M_e$，则要让 小于 $a_i$ 的数的个数 减 大于 $a_i$ 的数的个数 最大。
  因为已经把权值转化成了 $1/-1$ 。所以上面的做差可以变成求和。
  这就可以做了。