20240928 模拟赛

20240928 模拟赛

A genius

将模运算转化，\(\sum_{i=1}^{n}a_i\bmod k=\sum_{i=1}^{n}(a_i- \lfloor\frac{a_i}{k}\rfloor\times k)=sum-k\sum_{i=1}^n\lfloor\frac{a_i}{k}\rfloor=s\)。移项得到 \(sum-s=k\sum_{i=1}^n\lfloor\frac{a_i}{k}\rfloor\)。于是 \(sum-s\) 是 \(k\) 的倍数。枚举因数并一一判断即可。注意特判当 \(k\) 大于所有数，也就是 \(sum=s\) 的情况（赛时挂 \(90\)）。

B magic

注意到题目要求的是一个形如最大值最小的东西，想到二分答案。考虑如何 check。首先存在 \(a_i+b_i>mid\) 时一定不合法。感觉能贪心。先按 \(a_i\) 排序，依次考虑每一组配对中 \(a\) 的值较大的一个。那么只要满足 \(a_i+b_j\leq mid\) 的 \(i,j\) 都可以配对。那么应该取哪一个呢？尝试几种贪心，发现取的 \(a_j\) 越大越好。怎么证明呢？引用一个巨佬的注释：

严谨的证明是：
如果 \(i\) 可以匹配两个 \(j_1,j_2\)，其中 \(a_i\ge a_{j_1}\ge a_{j_2}\)，且 \(a_i+b_{j_1},a_i+b_{j_2}\leq mid\)。
如果我们去匹配 \(i\) 和 \(j_2\)，如果后面 \(j_1\) 去匹配了一个 \(i_2\)，则一定有 \(a_{j_1}+b_{i_2}\leq mid\)：

1. 如果 \(a_i\ge a_{j_1}\ge a_{j_2}\ge a_{i_2}\)
   因为 \(a_{j_2}+b_{i_2}\leq a_{j_1}+b_{i_2}\leq mid\)，所以可以改成 \(i\) 和 \(j_1\) 匹配，\(j_2\) 和 \(i_2\) 匹配。
2. 如果 \(a_i\ge a_{j_1}\ge a_{i_2}\ge a_{j_2}\)
   那么 \(a_{i_2}+b_{j_2}\leq a_i+b_{j_2}\leq mid\)，也可以改成 \(i\) 和 \(j_1\) 匹配，\(j_2\) 和 \(i_2\) 匹配。
3. 如果 \(a_i\ge a_{i_2}\ge a_{j_1}\ge a_{j_2}\)，此时是 \(i_2\) 去匹配了 \(j_1\)
   那么同理 \(a_{i_2}+b_{j_2}\leq a_i+b_{j_2}\leq mid\)。

那么接下来直接按照这个贪心策略配对，找最大的 \(a_j\) 可以使用 set 维护。具体的，因为枚举的 \(a_i\) 具有单调性，所以可以双指针求出满足条件的 \(b_j\) 的集合，插入 set，查找时直接取末尾即可。

D hollow

考虑取一个分界点 \(x\)，前面的 \(0\) 全取，后面的 \(1\) 全取，此时答案为一个 \(0\) 的前缀和加上一个 \(1\) 的后缀和。这样不方便维护，那么将 \(0\) 的前缀和看作所有数的前缀和，再将其中的 \(1\) 减掉。把 \(0\) 的权值设为正，\(1\) 的权值设为负，对这个新数组做一个前缀和 \(s\)，答案即为 \(cnt_1+\max_{1\le x \le n}{s_x}\)。

接下来考虑区间反转后的一个前缀来自于哪里，手玩一下发现来自于原序列中可以为空的一个前缀和若干个不交的区间，每次反转操作可以多加入一个区间的贡献。那么每次操作就应该取出原序列中的一个和最大的子段。但是这样显然无法保证几个区间不交。

这里就有一个很妙的操作（反悔贪心）。在选取一个区间之后，将这个区间中的所有数乘上 \(-1\)。这样如果在之后选取的区间与它相交，重叠部分的贡献就会被扣除（一正一负）。用线段树维护这些操作，每次查询最大子段，就能既保证最优，又保证区间不交。时间复杂度 \(O(n\log n)\)。

线段树部分需要维护最大、最小前缀、后缀、子段以及对应的位置。为了实现简便，可以将值与对应位置用一个 pair 存储。

using PP = pair<int, int>;
using PPP = pair<int, PP>;

struct Node{
	int l, r, sum, lzy;
	PP mxpre, mxsuf, mnpre, mnsuf;
	PPP max, min;
}c[N << 2];

PP operator + (int a, PP b){return {b.fi + a, b.se};}
PPP operator + (PP a, PP b){return {a.fi + b.fi, {a.se, b.se}};}
PP operator - (PP a){return {-a.fi, a.se};}
PPP operator - (PPP a){return {-a.fi, a.se};}

void push_up(int x){
	c[x].sum = c[x << 1].sum + c[x << 1 | 1].sum;
	c[x].mxpre = max(c[x << 1].mxpre, c[x << 1].sum + c[x << 1 | 1].mxpre);
	c[x].mnpre = min(c[x << 1].mnpre, c[x << 1].sum + c[x << 1 | 1].mnpre);
	c[x].mxsuf = max(c[x << 1 | 1].mxsuf, c[x << 1 | 1].sum + c[x << 1].mxsuf);
	c[x].mnsuf = min(c[x << 1 | 1].mnsuf, c[x << 1 | 1].sum + c[x << 1].mnsuf);
	c[x].max = max({c[x << 1].max, c[x << 1 | 1].max, c[x << 1].mxsuf + c[x << 1 | 1].mxpre});
	c[x].min = min({c[x << 1].min, c[x << 1 | 1].min, c[x << 1].mnsuf + c[x << 1 | 1].mnpre});
}

void change(int x){
	swap(c[x].mxpre, c[x].mnpre);
	swap(c[x].mxsuf, c[x].mnsuf);
	swap(c[x].max, c[x].min);
	c[x].lzy = -c[x].lzy;
	c[x].sum = -c[x].sum;
	c[x].mxpre = -c[x].mxpre;
	c[x].mnpre = -c[x].mnpre;
	c[x].mxsuf = -c[x].mxsuf;
	c[x].mnsuf = -c[x].mnsuf;
	c[x].max = -c[x].max;
	c[x].min = -c[x].min;
}

void push_down(int x){
	if (c[x].lzy == 1) return;
	c[x].lzy = 1, change(x << 1), change(x << 1 | 1);
}

void build(int x, int l, int r){
	c[x].l = l, c[x].r = r, c[x].lzy = 1;
	if (l == r){
		if (a[l] > 0){
			c[x].mxpre = c[x].mxsuf = {a[l], l};
			c[x].mnpre = {0, l - 1}, c[x].mnsuf = {0, r + 1};
			c[x].max = {a[l], {l, r}};
			c[x].min = {0, {l, l - 1}};
		}
		else{
			c[x].mnpre = c[x].mnsuf = {a[l], l};
			c[x].mxpre = {0, l - 1}, c[x].mxsuf = {0, r + 1};
			c[x].min = {a[l], {l, r}};
			c[x].max = {0, {l, l - 1}};
		}
		c[x].sum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
	push_up(x);
}

void change(int x, int l, int r){
	if (l <= c[x].l && c[x].r <= r){
		change(x);
		return;
	}
	push_down(x);
	int mid = (c[x].l + c[x].r) >> 1;
	if (l <= mid) change(x << 1, l, r);
	if (mid + 1 <= r) change(x << 1 | 1, l, r);
	push_up(x);
}