专栏文章

RiOI R7 Overall

RRegister_int-std=c++14
算法·理论参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mlml5wqt
此快照首次捕获于
2026/02/15 01:24
4 天前
此快照最后确认于
2026/02/18 01:26
昨天
查看原文
ABG TBD。

C

我毫无头绪！
先尝试做一些基本的无解判断。发现答案一定形如 x(x+1)2+k1v(v+1)2+k2v\frac{x(x+1)}2+k_1\frac{v(v+1)}2+k_2v 的形式，先判断是否有 x≥s(s+1)2x\ge\frac{s(s+1)}2 且 x−x(x+1)2x-\frac{x(x+1)}2 或 x−x(x+1)2−v(v+1)2x-\frac{x(x+1)}2-\frac{v(v+1)}2 是否能被 vv 整除。
加速有点抽象啊！
将 v−tv-t 图像画出来，可以将距离视为面积。那么每一个加速对答案的贡献都形如一个等腰梯形。可以拆成一个宽为 vv 的平行四边形和一个边长为 vv 的直角三角形。
如何快速求解？
对加速次数奇偶分类。设加速了 kk 次第 ii 次加速对距离造成的贡献为 aia_i，容易发现有：
  • ∀i,ai≥0\forall i,a_i\ge 0。
  • ∀i,ai≤x+(i−1)(v−1)\forall i, a_i\le x+(i-1)(v-1)
那么 ∑a\sum a 可以取到 0∼kx+k(k−1)(v−1)20\sim kx+\frac{k(k-1)(v-1)}2 的所有数。只要 ss 所需的 ∑a\sum a 在这个在这个范围内即可。直接二分，总时间复杂度 O(Tlog⁡V)\mathcal{O}(T\log V)。当然也可以解不等式，时间复杂度 O(T)\mathcal{O}(T)。
注意一下边界。当 x≤vx\le v 的时候可能出现踩一脚不够踩两脚太多的情况，不过也只会在答案为 22 时出现，特判掉就好。
可以看看具体实现吗？
可以捏。
CPP
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int T; ll x, v, s;

int main() {
	for (scanf("%d", &T); T--; ) {
		scanf("%lld%lld%lld", &x, &v, &s), s -= x * (x + 1) / 2;
		if (s < 0) { puts("-1"); continue; }
		if (!v) { puts(s ? "-1" : "0"); continue; }
		ll ans = 1e18;
		if (s % v == 0) {
			ll l = 0, r = 1e12, ts = s / v;
			for (; l < r; ) {
				ll mid = l + r >> 1, k = mid << 1;
				if (mid * (v + 1) + k * x + (__int128)k * (k - 1) * (v - 1) / 2 >= ts) r = mid;
				else l = mid + 1;
			}
			if (s >= (__int128)l * v * (v + 1)) ans = min(ans, l << 1);
		}
		s -= v * (v + 1) / 2;
		if (s >= 0 && s % v == 0) {
			ll l = 0, r = 1e12, ts = s / v;
			for (; l < r; ) {
				ll mid = l + r >> 1, k = mid << 1 | 1;
				if (mid * (v + 1) + k * x + (__int128)k * (k - 1) * (v - 1) / 2 >= ts) r = mid;
				else l = mid + 1;
			}
			if (s >= (__int128)l * v * (v + 1)) ans = min(ans, l << 1 | 1);
		}
		printf("%lld\n", ans >= 1e18 ? -1ll : ans);
	}
}

D

我毫无头绪！
先想想怎么做构造。我们需要去判断两个点是否相邻。 可以发现一个事情：若固定一个点 uu，则查询得到的返回值最大时，vv 必然与 uu 相邻。
这样即可做到查询 n2/2n^2/2 次左右。
我大概会构造了，但是如何进一步缩减步数？
在下一个 Subtask 中你大概要做到 n2/4n^2/4。容易看出来这是一个“叶子节点数量”×\times“非叶子节点数量”。
首先找到一个叶子，以他为根，即可获得所有节点的子树大小。之后，将所有点按子树大小排序，维护一个“待匹配节点”列表。每次用最小的点去这个列表里进行匹配，之后将这个点塞进列表之中。容易看出，任意时刻列表内的点数都不超过叶子数，总匹配次数自然是 n2/4n^2/4 级别。
问题是如何用一次询问做到匹配呢？假设 uu 要去匹配 vv，vv 的子树大小为 svs_v。由于 vv 不能是 uu 的祖先，经过 u,vu,v 链的条数的最大值必然为 sv(n−sv)s_v(n-s_v)。这也恰好是 vv 是 uu 的儿子的情况！只需判断查询所得的值是否是 sv(n−sv)s_v(n-s_v) 即可。
直接这么干应该过不去，会多 O(n)\mathcal{O}(n) 次询问。不过加点剪枝随便过。
Bonus：查询次数必须得 O(n2)\mathcal{O}(n^2) 吗？
很遗憾，是的。
考虑一个菊花，再将菊花的每一瓣换成长度为 22 的链。与菊花中心距离为 11 的称为内层点，距离为 22 的称为外层点。你会发现，若要确定每个内层点与外层点的匹配关系，除了 O(n2)\mathcal{O}(n^2) 枚举别无他法。
不过这并不代表 4×1064\times 10^6 就是这题的极限了。事实上用这个图只能说明下界是期望 n2/16n^2/16（也即随机打乱后的期望逆序对数量）。
关于维护待匹配集合的做法，事实上存在 n2/6n^2/6 的一个下界：考虑一棵树，子树大小为 2k2^k 的节点有 n/2k+1n/2^{k+1} 个，每个节点的儿子子树大小为 20∼k−12^{0\sim k-1}。通过简单计算可以得出，至少需要查询 (n2/2)/3=n2/6(n^2/2)/3=n^2/6 次。当然在期望下是 n2/12n^2/12 次了。不过这个构造只能说明存在这个下界，但是最大能卡到多少也不得而知了。
如果有人得出了更好的做法，欢迎在讨论区指出！
可以看看具体实现吗？
可以捏。
CPP
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned uint;
typedef vector<pair<int, int>> vii;

const int MAXN = 4e3 + 10;

int n, sz[MAXN], a[MAXN]; set<int> s;

int query(int u, int v);
inline bool check(int u, int v) { return sz[v] * (n - sz[v]) == query(u, v); }

vii guess(int N) {
	vii res; n = N;
	int rt = 1; sz[1] = n * (n - 1) >> 1;
	for (int i = 2; i <= n; i++) {
		int x = query(1, i);
		if (x < sz[1]) sz[1] = x, rt = i;
	}
    for (int i = 2; i <= n; i++) sz[i] = (i == rt) ? n : query(rt, i);
	for (int i = 1; i <= n; i++) a[i] = i;
	sort(a + 1, a + n + 1, [](int u, int v) { return sz[u] < sz[v]; });
	for (int i = 1; i <= n; i++) {
		if (sz[a[i]] == 1) { s.emplace(a[i]); continue; }
		int k = sz[a[i]];
		for (auto it = s.begin(); it != s.end(); ) {
			if (k <= sz[*it] || !check(a[i], *it)) ++it;
			else k -= sz[*it], res.emplace_back(a[i], *it), it = s.erase(it);
		}
		s.emplace(a[i]);
	}
	return res;
}

E

我毫无头绪！
先做判定。找出 Alice 和 Bob 的必胜条件。
感觉两个人做的操作有点奇怪？
的确如此。我们考虑将操作改写。可以执行以下两个操作之一：
  1. 将一个数删除。
  2. 将 1111 变为 00。
很明显 Alice 不会傻到去动第二种操作，而 Bob 希望能一直干第二种操作。接下来就比较清晰了。
Alice 也太难办了！
那就别办咯！来看看如果 Bob 先手是什么情况。
首先如果 Bob 走最后一步 Alice 必死无疑。因此 nn 为偶数 Bob 必胜。接下来考虑 nn 为奇数的情况。
我们发现 Bob 干的事情很无脑。他会吃掉所有 11 的连续段，知道连续段内的 11 没掉或剩一个。此时 Alice 啥都干不了，因为 Bob 在吃俩 11 的时候会顺便生出来一个 00，Alice 只能跟在后面把 00 擦掉。
接下来两个人都只能一个一个删，这时就是比速度了。看谁的数多谁就赢。
我尝试得出 Alice 必胜的充要条件，但是看上去复杂得完全没法做。
那是因为 Bob 的必胜条件还没推完呢（恼）
若序列开头为 00，那么 00 的个数必然不少于 11 的段数，Bob 必胜。否则开头为 11。考虑从单个 11 开始，两个两个地往末尾接上数字，尝试生成所有 Bob 必败的序列。我们发现：
  • 不能接 0000，最前面的 11 和 00 抵消后回到开头为 00 的情况。
  • 不能接 1010，否则最前面的两个 11 会被 Bob 干掉，回到开头为 00 的情况。
所以只能接 0101 或者 1111。而这相当于奇数位上不能是 00！
得到等价充要条件：
  • nn 为偶数，或者奇数位上存在至少一个 00。
那么 Alice 的策略就很明显了：对着这个卡！
考虑挖出所有 00 的位置。如果形如一段偶数（可以为空）加一段奇数（可以为空）的形式，Alice 可以删去分界点处的 00，从而转到 Bob 先手的必败情况。否则 Alice 无论如何操作都会转到 Bob 先手的必胜情况。进一步得到 Alice 获胜的充要条件：
  • nn 为偶数，且 00 的位置形如一段偶数（可以为空）加一段奇数（可以为空）的形式。
我不会维护！
这个不用我教你了吧（恼）
区间查询用线段树维护，维护以下五个信息：
  • 没有 00 出现的方案数。
  • 有 00 且全在奇数上的方案数。
  • 有 00 且全在偶数上的方案数。
  • 有 00 且一段奇一段偶的方案数。
  • 有 00 且一段偶一段奇的方案数。
合并是简单的。时间复杂度 O(n+mlog⁡n)O(n+m\log n)。
当然你也可以考虑 dpi,0/1dp_{i,0/1} 表示考虑了前 ii 个，是否有 00 在奇数位出现的方案数。转移是 2×22\times 2 矩阵形式，动态 dp 即可。时间复杂度不变。
注意特判区间长度为 11 的情况。这个时候谁都动不了。
可以看看具体实现吗？
可以捏。
CPP
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;
const int mod = 998244353;

int n, m; char s[MAXN];

struct node {
	int l, r;
	int x, y, z, xy, yx;
	node(int l = 0, int r = 0) : l(l), r(r), x(0), y(0), z(0), xy(0), yx(0) {}
	node operator + (const node &rhs) const {
		node res(l, rhs.r); res.z = (ll)z * rhs.z % mod;
		if (r - l & 1) {
			res.x = ((ll)x * (rhs.x + rhs.z) + (ll)z * rhs.x) % mod;
			res.y = ((ll)y * (rhs.y + rhs.z) + (ll)z * rhs.y) % mod;
			res.xy = ((ll)x * (rhs.y + rhs.xy) + (ll)xy * (rhs.y + rhs.z) + (ll)z * rhs.xy) % mod;
			res.yx = ((ll)y * (rhs.x + rhs.yx) + (ll)yx * (rhs.x + rhs.z) + (ll)z * rhs.yx) % mod;
		} else {
			res.x = ((ll)x * (rhs.y + rhs.z) + (ll)z * rhs.y) % mod;
			res.y = ((ll)y * (rhs.x + rhs.z) + (ll)z * rhs.x) % mod;
			res.xy = ((ll)x * (rhs.x + rhs.yx) + (ll)xy * (rhs.x + rhs.z) + (ll)z * rhs.yx) % mod;
			res.yx = ((ll)y * (rhs.y + rhs.xy) + (ll)yx * (rhs.y + rhs.z) + (ll)z * rhs.xy) % mod;
		}
		return res; 
	}
} t[MAXN << 2];

void build(int l = 1, int r = n, int p = 1) {
	if (l == r) {
		t[p] = node(l, r);
		if (s[l] != '0') t[p].z = 1;
		if (s[l] != '1') t[p].x = 1;
		return ;
	}
	int mid = l + r >> 1;
	build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
	t[p] = t[p << 1] + t[p << 1 | 1];
}

node ask(int ql, int qr, int l = 1, int r = n, int p = 1) {
	if (ql <= l && r <= qr) return t[p];
	int mid = l + r >> 1;
	if (qr <= mid) return ask(ql, qr, l, mid, p << 1);
	if (ql > mid) return ask(ql, qr, mid + 1, r, p << 1 | 1);
	return ask(ql, qr, l, mid, p << 1) + ask(ql, qr, mid + 1, r, p << 1 | 1);
}

int main() {
	scanf("%d%d%s", &n, &m, s + 1), build();
	for (int l, r; m--; ) {
		scanf("%d%d", &l, &r);
		if (r - l + 1 & 1) {
			if (l == r) puts(s[l] == '0' ? "0" : "1");
			else puts("0"); continue;
		}
		node tmp = ask(l, r);
		printf("%lld\n", ((ll)tmp.x + tmp.y + tmp.z + tmp.yx) % mod);
	}
}

F

我毫无头绪！
区间区间 mex⁡\operatorname{mex} 之和看上去就没法做。因此需要对 mex⁡\operatorname{mex} 进行一个贡献的拆，拆成 ∑i∏ji[j∈S]\sum_i\prod^i_j[j\in S]。
静态怎么做？
对于每个 kk 预处理出来包含 0∼k0\sim k 的所有数的最小区间 [lk,rk][l_k,r_k]，每个区间被包含一次就会造成 11 的贡献。那么一个区间 kk 如果被询问 l,rl,r 包含，就会造成 (lk−l+1)(r−rk+1)(l_k-l+1)(r-r_k+1) 的贡献。
这些区间是一个包一个的，而最大区间就是区间 mex⁡\operatorname{mex} 对应的区间。根据经典结论区间 mex⁡\operatorname{mex} 等于补集 min⁡\min，可以直接通过维护原排列前后缀最小值算出来。那么只要求一个前缀和，时间复杂度 O(n+q)\mathcal{O}(n+q)。
没想到吧能线性！
我已经尝试了一些火箭，但是都不太有前途。
不知道你有没有做过【UR #19】前进四。
换维，转而扫描序列维，维护时间维。那么我们相当于要维护以下操作：
  1. 对于 [L,R][L,R] 内的所有 ii，li→min⁡(li,x)l_i\to\min(l_i,x)，ri→max⁡(ri,x)r_i\to\max(r_i,x)。
  2. 复制一个新版本。
  3. 查询 ii 上 lil_i，rir_i，liril_ir_i 的历史和。
这个问题看着就可做多了。
我已经得到了单 log⁡\log 做法，但是常数也太逆天了！
直接用矩阵标记的套路维护历史和很倒闭，因为至少要维护四个 5×55\times 5 的矩阵标记用来分类下传，带一个大约 535^3 的常数，完全不可接受，需要另寻它路。
突破口应该在单点历史和上。矩阵标记维护了我们并不需要的区间历史和，这个很菜。
在要维护什么东西这方面能给一些提示吗？
先来看简单的情况：区间加，单点历史和。对于一个在 t0t_0 时刻加 kk 的修改，其对 TT 时刻历史和的影响是 k(T−t0)=kT−kt0k(T-t_0)=kT-kt_0，是一个关于 TT 的一次函数。这启发我们以一次函数的形式描述一个标记。
我不会下传标记，完蛋了！
别急啊别急啊（笑）
查询中前两项 ∑li,∑ri\sum l_i,\sum r_i 是简单的，但第三项 ∑iliri\sum_i l_ir_i 有些棘手。
我们尝试来解决它。维护三类贡献：所有修改对于 ll 为最大值且 rr 不为最小值的位置的贡献（下文称为一类标记），对于 ll 不为最大值且 rr 为最小值的位置的贡献（称为二类标记，以及对于 ll 为最大值且 rr 为最小值的位置的贡献（称为三类标记）。
在一次修改时，第三类贡献是已经确定的，可以直接下传。但另两类贡献都有一个乘积项不确定。如何解决？
首先，在 Segment Tree Beats 修改的过程中，所有非最值的位置都不会被更改，且下传时一二类标记对应的情况不会发生更改，因此不用考虑一二类标记相互合并的情况。另外，以一类标记为例，其在下传至子区间时有两种情况：
  1. rr 的最小值不变。
  2. rr 的最小值改变。
对于第一种情况，直接与子区间的一类标记合并即可。对于第二种情况，虽然直接下传会少算 rr 的最小值这部分贡献，只需将这部分直接“结算”至第三类贡献，就能补上漏的部分。
由于我们只关心单点的信息，不需要考虑上传。查询时直接查叶子处的标记即可。
总时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。
时限很宽松，只要写的不是过分的菜都能通过。
可以看看具体实现吗？
可以捏。有点小长。
CPP
#include <bits/stdc++.h>

using namespace std;

// using ikaleio fastIO

typedef unsigned long long ll;

const int MAXN = 1e6 + 10;

int n, m, a[MAXN];

namespace SGT {
	
	int len, t[MAXN << 2];
	
	inline void pushup(int p) { t[p] = min(t[p << 1], t[p << 1 | 1]); }
	
	inline 
	void build() {
		for (len = 1; len <= n; len <<= 1);
		for (int i = 1; i <= n; i++) t[i + len] = a[i];
		for (int i = len; i; i--) pushup(i);
	}
	
	inline 
	void modify(int k, int x) {
		t[k + len] = x;
		for (int i = k + len >> 1; i; i >>= 1) pushup(i);
	}
	
	inline 
	int ask(int l, int r) {
		int res = n + 1; if (l > r) return res;
		for (l += len - 1, r += len + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
			if (~l & 1) res = min(res, t[l ^ 1]);
			if (r & 1) res = min(res, t[r ^ 1]);
		}
		return res;
	}
	
};

int tmp[MAXN];

namespace SGTB {
	
	struct func {
		ll k, b;
		func(ll k = 0, ll b = 0) : k(k), b(b) {}
		func operator + (const func &rhs) const { return func(k + rhs.k, b + rhs.b); }
		func& operator += (const func &rhs) { return *this = *this + rhs; }
		func operator * (ll w) const { return func(k * w, b * w); }
		ll operator () (ll x) { return k * x + b; }
	};
	
	struct node {
		
		int x, sx, dx, y, sy, dy;
		func tx, ty, t1, t2, t3;
		
		node(int val = 0) : 
			x(val), sx(0), dx(1e9), y(val), sy(1e9), dy(0), 
			tx(val), ty(val), t1(), t2(), t3((ll)val * val) {}
		
		node operator + (const node &rhs) const {
			node res;
			if (x == rhs.x) res.x = x, res.sx = max(sx, rhs.sx);
			else {
				res.x = max(x, rhs.x);
				if (x < rhs.x) res.sx = max(x, rhs.sx);
				else res.sx = max(sx, rhs.x);
			}
			if (y == rhs.y) res.y = y, res.sy = min(sy, rhs.sy);
			else {
				res.y = min(y, rhs.y);
				if (y > rhs.y) res.sy = min(y, rhs.sy);
				else res.sy = min(sy, rhs.y);
			}
			return res;
		}
		
	} t[MAXN << 2];
	
	inline 
	void pushup(int p) {
		t[p] = t[p << 1] + t[p << 1 | 1];
	}
	
	inline 
	void upd(int p, const node &tag) {
		if (t[p].x > tag.dx) t[p].x = t[p].dx = tag.dx;
		if (t[p].y < tag.dy) t[p].y = t[p].dy = tag.dy;
		if (t[p].x == tag.x) t[p].tx += tag.tx, t[p].t1 += tag.t1;
		if (t[p].y == tag.y) t[p].ty += tag.ty, t[p].t2 += tag.t2;
		if (t[p].x == tag.x && t[p].y == tag.y) t[p].t3 += tag.t3;
		else if (t[p].x == tag.x) t[p].t3 += tag.t1 * t[p].y;
		else if (t[p].y == tag.y) t[p].t3 += tag.t2 * t[p].x;
	}
	
	inline 
	void pushdown(int p) {
		upd(p << 1, t[p]), upd(p << 1 | 1, t[p]);
		t[p].dx = 1e9, t[p].dy = 0;
		t[p].tx = t[p].ty = t[p].t1 = t[p].t2 = t[p].t3 = 0;
	}
	
	void build(int l = 1, int r = m, int p = 1) {
		if (l == r) return t[p] = node(tmp[l]), void(); int mid = l + r >> 1;
		build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1), pushup(p);
	}
	
	void modify(int ql, int qr, int val, int t0, int l = 1, int r = m, int p = 1) {
		if (r < ql || l > qr) return ;
		if (val >= t[p].x && val <= t[p].y) return ;
		if (ql <= l && r <= qr && val > t[p].sx && val < t[p].sy) {
			int px = t[p].x, py = t[p].y; ll k = 0;
			if (t[p].x > val) t[p].x = t[p].dx = val;
			if (t[p].y < val) t[p].y = t[p].dy = val;
			k = t[p].x - px;
			t[p].tx += func(k, -k * t0), t[p].t1 += func(k, -k * t0);
			k = t[p].y - py;
			t[p].ty += func(k, -k * t0), t[p].t2 += func(k, -k * t0);
			k = (ll)t[p].x * t[p].y - (ll)px * py;
			t[p].t3 += func(k, -k * t0);
			return ;
		}
		int mid = l + r >> 1; pushdown(p);
		if (ql <= mid) modify(ql, qr, val, t0, l, mid, p << 1);
		if (qr > mid) modify(ql, qr, val, t0, mid + 1, r, p << 1 | 1);
		pushup(p);
	}
	
	node ask(int k, int l = 1, int r = m, int p = 1) {
		if (l == r) return t[p];
		int mid = l + r >> 1; pushdown(p);
		if (k <= mid) return ask(k, l, mid, p << 1);
		return ask(k, mid + 1, r, p << 1 | 1);
	}
	
}

vector<tuple<int, int, int>> g[MAXN], q[MAXN];

int ti[MAXN]; ll ans[MAXN]; bool vq[MAXN];

int main() {
	io.read(n, m);
	for (int i = 1; i <= n; i++) io.read(a[i]), a[i]++;
	SGT::build();
	for (int i = 1, op, l, r; i <= m; i++) {
		io.read(op, l, r);
		if (op == 1) {
			g[a[l]].emplace_back(ti[a[l]] + 1, i, l), ti[a[l]] = i;
			g[a[r]].emplace_back(ti[a[r]] + 1, i, r), ti[a[r]] = i;
			swap(a[l], a[r]), SGT::modify(l, a[l]), SGT::modify(r, a[r]);
		} else {
			int x = SGT::ask(1, l - 1), y = SGT::ask(r + 1, n);
			q[min(x, y) - 1].emplace_back(l, r, i), vq[i] = 1;
		}
	}
	for (int i = 1; i <= n; i++) if (ti[a[i]] < m) g[a[i]].emplace_back(ti[a[i]] + 1, m, i);
	for (auto [l, r, k] : g[1]) for (int i = l; i <= r; i++) tmp[i] = k;
	SGTB::build();
	for (int i = 1; i <= n; i++) {
		for (auto [l, r, k] : g[i]) SGTB::modify(l, r, k, i - 1);
		for (auto [l, r, k] : q[i]) {
			auto res = SGTB::ask(k);
			ll sl = res.tx(i), sr = res.ty(i), slr = res.t3(i);
			ans[k] = sl * (r + 1) + sr * (l - 1) - slr - (ll)(l - 1) * (r + 1) * i;
		}
	}
	for (int i = 1; i <= m; i++) if (vq[i]) io.writeln(ans[i]);
}

G

我不会，哈哈！

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...