AtCoder ARC149D – Simultaneous Sugoroku 简略题解

Atcoder ARC149D – Simultaneous Sugoroku

官方题解做法是线性的，在此不再赘述。

考虑对于纸片 $X=1,2,\cdots,\max\{X_i\}$ 分别计算答案。每次暴力枚举显然不可取，但假若我们知晓对于 $X$，在 $i=0,1,\cdots,M$ 次操作以后纸片在数轴上的坐标 $x_0=X,x_1,\cdots,x_m$，其中 $\text{pos}$ 是最小的取到 $x_\text{pos}=-1$ 的位置，则对于 ${x_0}’=X’=X+1$：

• 如果 $\text{pos}$ 不存在，则所有坐标整体向数轴正半轴平移 $1$ 单位；
• 否则，$\text{pos}$ 就将是起始点为 $X’$ 的纸片首次到达 $0$ 点的位置，也即题目所求。所有小于 $\text{pos}$ 的坐标仍向正半轴平移 $1$ 单位；而 $\geq \text{pos}$ 的坐标，由于偏移量 $D_i$ 符号翻转，则有 ${x_i}’-{x_{i-1}}’=-(x_i-x_{i-1})$。依次考虑每一坐标，就会得到 ${x_i}’=1-x_i,\forall \text{pos}\leq i\leq m$。
  （这里认为当 $x_\text{pos}=0$ 时仍然继续执行操作。维护 $\geq\text{pos}$ 的坐标位置是为了计算 $X”>X’$ 的答案。）

这是可以用区间树维护的：我们想要快速求出全局非正数最大值以及首次取到该最大值的位置，同时支持全局加 $1$、后缀所有数符号翻转 （$\times -1$）。那么同时维护区间非负数最大值、正数最小值以及首次取到他们的位置，采用延迟标记更新（两种操作对于前述信息是具有结合律的，形成幺半群）即可。

时间复杂度 $\operatorname{O}(\max\{X_i\}\log M)$，常数一般。

Submission #36155560

#include <bits/stdc++.h>
using namespace std;

#define inl inline
/* 快读已省略。 */
#define reint register int
#define newl putchar('\n')
typedef long long ll;
// typedef unsigned long long ull;
// typedef __int128 lll;
// typedef long double llf;
typedef pair <int, int> pint;
#define fst first
#define scd second
#define all(p) begin (p), end (p)
#define empb emplace_back

constexpr int N = 3e5 + 10, G = 1e6 + 10, INF = 0x3f3f3f3f;
int n, m, cor[N], seq[N], d;

struct seg_tree { int tar;
	struct node { pint pmn, nmx; int tag, dt; } t[N<<2];
	inl void post (int x) {
		t[x].pmn = min (t[x<<1].pmn, t[x<<1|1].pmn),
		t[x].nmx = min (t[x<<1].nmx, t[x<<1|1].nmx);
	}
	inl void sousa (int x, int tag, int dt) {
		if (tag) swap (t[x].pmn, t[x].nmx),
			t[x].tag ^= 1, t[x].dt *= -1;
		t[x].pmn.fst += dt,
		t[x].nmx.fst -= dt, t[x].dt += dt;
	}
	inl void down (int x) {
		sousa (x<<1, t[x].tag, t[x].dt),
		sousa (x<<1|1, t[x].tag, t[x].dt),
		t[x].tag = t[x].dt = 0;
	}
	void build (int x, int l, int r) {
		if (l == r) {
			t[x].pmn = { seq[l] <= 0 ? INF : seq[l], l },
			t[x].nmx = { seq[l] > 0 ? INF : -seq[l], l };
			return; }
		int mid = l + r >> 1;
		build (x<<1, l, mid),
		build (x<<1|1, mid + 1, r);
		post (x);
	}
	void rever (int x, int l, int r) {
		if (l >= tar) return sousa (x, 1, 0);
		int mid = l + r >> 1; down (x);
		if (tar <= mid) rever (x<<1, l, mid);
		rever (x<<1|1, mid + 1, r); post (x);
	}
	int saigo (int x, int l, int r) {
		if (l == r) return t[x].pmn.fst < G
			? t[x].pmn.fst : -t[x].nmx.fst;
		return down (x), saigo (x<<1|1, (l+r>>1)+1, r);
	}
	inl void rever (int lbd) { tar = lbd, rever (1, 0, m); }
} seg;

int main () {
	/* ARC149D - Simultaneous Suguroku 吴秋实 */
	read (n, m);
	for (int i = 1; i <= n; ++i)
		read (cor[i]);
	seq[0] = 1;
	for (int i = 1; i <= m; ++i) {
		read (d);
		if (seq[i-1] <= 0) seq[i] = seq[i-1] + d;
		else seq[i] = seq[i-1] - d;
	}
	seg.build (1, 0, m);
	for (int pt = 1, x = 1; pt <= n; ++x) {
		const auto [nmx, fr] = seg.t[1].nmx;
		if (!nmx) seg.rever (fr);
		if (x == cor[pt]) {
			if (!nmx) print ("Yes", fr), newl;
			else print ("No", seg.saigo (1, 0, m)), newl;
			++pt;
		}
		seg.sousa (1, 0, 1);
	}

	return 0;
}