AtCoder ARC 149 D – Simultaneous Sugoroku 简略题解

Atcoder ARC149D – Simultaneous Sugoroku

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

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

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

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

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

Submission #36155560

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
  80. 80
  81. 81
  82. 82
  83. 83
  84. 84
  85. 85
  86. 86
#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; }
  • 2022年11月2日