很妙的一个题。
没法用数据结构直接维护点的移动。可以挖掘一些性质。
发现对于两个点 \(x\) 和 \(-x\)，它们的移动关于原点对称。可以根据对称性维护森林。
维护当前的区间，初始为 \([1,10^6]\) 并且这个区间总是位于 \(x\) 轴的同一个半轴中。假设当前遇到了操作 \(d_i\)，将区间根据正负向左或向右移 \(d_i\) 格。若区间覆盖了原点，就把区间以原点为分界点分割，将较短的那一边对称到较长的那一边。
参考官方题解给的一张图：
初始区间为 \([1,12]\)，左移 \(8\) 位，则 \(8\) 到达了原点，接下来不用考虑了。剩下的两个区间 \([1,7]\) 和 \([9,12]\)，将 \([9,12]\) 对称到 \([1,7]\) 中，在树中连向相应的边 \(7 \to 9\)，\(6 \to 10\)，\(5 \to 11\)，\(4 \to 12\)，表示将来的 \(12\) 就继承 \(4\) 的状态，最后位置再取个反。后面的右移 \(2\) 位同理。
最后一遍 dfs 求出最后每个点的状态。
实现时维护了一个 \(add\) 表示整个区间的偏移量。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 1000100;
const int N = 1000000;
int n, m, a[maxn], b[maxn], head[maxn], len;
bool vis[maxn];
pii ans[maxn];
struct edge {
int to, next;
} edges[maxn];
void add_edge(int u, int v) {
edges[++len].to = v;
edges[len].next = head[u];
head[u] = len;
}
void dfs(int u) {
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
ans[v] = (ans[u].fst ? ans[u] : make_pair(0, -ans[u].scd));
dfs(v);
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%d", &b[i]);
}
int l = 1, r = N, add = 0;
for (int i = 1; i <= m && l <= r; ++i) {
add += (l + add > 0 ? -b[i] : b[i]);
int mid = -add;
if (!(l <= mid && mid <= r)) {
continue;
}
ans[mid] = make_pair(1, i);
if (mid - l < r - mid) {
for (int j = l; j < mid; ++j) {
add_edge(mid * 2 - j, j);
vis[j] = 1;
}
l = mid + 1;
} else {
for (int j = mid + 1; j <= r; ++j) {
add_edge(mid * 2 - j, j);
vis[j] = 1;
}
r = mid - 1;
}
}
for (int i = l; i <= r; ++i) {
ans[i] = make_pair(0, i + add);
}
for (int i = 1; i <= N; ++i) {
if (!vis[i]) {
dfs(i);
}
}
for (int i = 1; i <= n; ++i) {
if (ans[a[i]].fst) {
printf("Yes %d\n", ans[a[i]].scd);
} else {
printf("No %d\n", ans[a[i]].scd);
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}