有 \(N\) 个数 \(X_i\) 和 \(M\) 个数 \(D_i\),对每个 \(X_i\) 询问依次对 \(j = 1 \to n\) 执行:如果 \(X_i > 0\) 就 \(-D_j\),如果 \(X_i < 0\) 就 \(+D_j\),\(X_i = 0\) 啥都不做。问每个 \(X_i\) 最后能否变成 \(0\),如果能问当 \(j\) 为何值时,否则问最后的值。\(N, M \le 300000\),\(X_i, D_i \le 1000000\)。
模拟加裸并查集。\(X\) 值小,可以维护 \([-1000000, -1]\) 和 \([1, 1000000]\) 两个区间。对于每个 \(D_i\) 就是把两个区间移移,重叠的用并查集合起来,如果有等于 \(0\) 的记录一下,并从 \(0\) 处断开。
最后对于 \(N\) 个询问看看 \(X_i\) 在并查集上的祖先最后怎么样了即可,时间复杂度 \(\Theta(n \cdot \alpha(n))\)。
标签:le,查集,1000000,Sugoroku,Simultaneous,ARC149D From: https://www.cnblogs.com/Pizza1123/p/16750427.html