题解：AT_arc149_d [ARC149D] Simultaneous Sugoroku

_Linver_ · 2025-02-21 11:25:21 · 题解

1. 直接上数据结构

   • 用范浩强平衡树维护。

2. 步骤

   • 初始按权值 0 分裂为两棵树 x 和 y。
   • 对 x 子树内所有节点权值增加 D，对 y 子树内所有节点权值减少 D。
   • 合并 x 和 y，需保证合并后平衡性：
     1. 选根：取值较小的树作为根（设为 x）。
     2. 分裂 y 树：以 x 的权值为基准，将 y 分裂为左子树 l 和右子树 r。
     3. 合并：将 x 的左子树与 l 合并，右子树与 r 合并。

3. 标记

   • 最终按权值 0 和 -1 将整棵树分裂为 x, y, z，将中间子树 y 的所有节点标记为 "Yes"。

4. 复杂度

   • 总时间复杂度为 O(n \log^2 n)，平衡树合并来的。

#include <bits/stdc++.h>
std::mt19937_64 myrand (
    std::chrono::high_resolution_clock::now ().time_since_epoch ().count ());
inline int
R (int n)
{
  return myrand () % n + 1;
}
inline int
read ()
{
  char ch = getchar ();
  int x = 0, f = 1;
  for (; ch < '0' || ch > '9'; ch = getchar ())
    if (ch == '-')
      f = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar ())
    x = (x << 3) + (x << 1) + (ch ^ 48);
  return x * f;
}
inline void
Min (int &x, int y)
{
  if (x > y)
    x = y;
}
inline void
Max (int &x, int y)
{
  if (x < y)
    x = y;
}
namespace std
{
const int N = 3e5 + 10;
inline ll
read ()
{
  ll x = 0, f = 1;
  char c = getchar ();
  while (c < '0' || c > '9')
    {
      if (c == '-')
        f = -1;
      c = getchar ();
    }
  while (c >= '0' && c <= '9')
    {
      x = (x << 1) + (x << 3) + (c ^ 48);
      c = getchar ();
    }
  return x * f;
}
inline void
write (ll x)
{
  if (x < 0)
    {
      putchar ('-');
      x = -x;
    }
  if (x > 9)
    write (x / 10);
  putchar (x % 10 + '0');
}
mt19937 R (time (0));
int n, m, v, cnt, rt;
int ans[N], fa[N];
bool f[N];
struct Node
{
  int lson, rson;
  int data, tag, id;
  ll key;
} X[N];
inline int
Find (int x)
{
  if (x != fa[x])
    return fa[x] = Find (fa[x]);
  return fa[x];
}
inline void
dsu_merge (int x, int y)
{
  x = Find (x), y = Find (y);
  if (x == y)
    return;
  fa[x] = y;
}
inline int
newnode (int v, int id)
{
  ++cnt;
  X[cnt].lson = X[cnt].rson = X[cnt].tag = 0;
  X[cnt].key = R ();
  X[cnt].data = v;
  X[cnt].id = id;
  return cnt;
}
inline void
add (int k, int v)
{
  if (!k)
    return;
  X[k].data += v;
  X[k].tag += v;
}
inline void
push_down (int k)
{
  if (X[k].tag)
    {
      add (X[k].lson, X[k].tag);
      add (X[k].rson, X[k].tag);
      X[k].tag = 0;
    }
}
inline void
split (int k, int v, int &x, int &y)
{
  if (!k)
    {
      x = y = 0;
      return;
    }
  push_down (k);
  if (X[k].data <= v)
    {
      x = k;
      split (X[k].rson, v, X[k].rson, y);
    }
  else
    {
      y = k;
      split (X[k].lson, v, x, X[k].lson);
    }
}
inline int
merge (int x, int y)
{
  if (!x || !y)
    return x + y;
  if (X[x].key < X[y].key)
    {
      push_down (x);
      X[x].rson = merge (X[x].rson, y);
      return x;
    }
  else
    {
      push_down (y);
      X[y].lson = merge (x, X[y].lson);
      return y;
    }
}
inline void
addfa (int k, int v)
{
  if (!k)
    return;
  dsu_merge (X[k].id, v);
  addfa (X[k].lson, v), addfa (X[k].rson, v);
}
inline int
Merge (int x, int y)
{
  if (!x || !y)
    return x + y;
  if (X[x].key > X[y].key)
    swap (x, y);
  push_down (x);
  int l, r, p;
  split (y, X[x].data, l, r);
  split (l, X[x].data - 1, l, p);
  addfa (p, X[x].id);
  X[x].lson = Merge (X[x].lson, l);
  X[x].rson = Merge (X[x].rson, r);
  return x;
}
inline void
insert (int v, int id)
{
  int x, y;
  split (rt, v, x, y);
  rt = merge (merge (x, newnode (v, id)), y);
}
inline void
sol (int k, int v)
{
  if (!k)
    return;
  push_down (k);
  if (v)
    {
      ans[X[k].id] = v;
      f[X[k].id] = 1;
    }
  else
    ans[X[k].id] = X[k].data;
  sol (X[k].lson, v), sol (X[k].rson, v);
}
int
main ()
{
  n = read (), m = read ();
  for (int i = 1; i <= n; ++i)
    {
      fa[i] = i;
      v = read ();
      if (!v)
        {
          f[i] = 1;
          ans[i] = 0;
          continue;
        }
      insert (v, i);
    }
  for (int i = 1; i <= m; ++i)
    {
      v = read ();
      int x, y;
      split (rt, 0, x, y);
      add (x, v), add (y, -v);
      rt = Merge (x, y);
      int z;
      split (rt, 0, x, z);
      split (x, -1, x, y);
      sol (y, i);
      rt = merge (x, z);
    }
  sol (rt, 0);
  for (int i = 1; i <= n; ++i)
    {
      fa[i] = Find (i);
      if (f[fa[i]])
        printf ("Yes %d\n", ans[fa[i]]);
      else
        printf ("No %d\n", ans[fa[i]]);
    }
  return 0;
}
}
const int N = 1e6 + 10, V = 1e6 + 10;
int n, m, fa[V], a[N], ans[V];
bool v[V];
inline int
find (int x)
{
  if (fa[x] == x)
    return x;
  int d = fa[x];
  fa[x] = find (fa[x]);
  return v[x] ^= v[d], fa[x];
}
signed
main ()
{
  std::ios::sync_with_stdio (false);
  std::cin.tie (0);
  std::cout.tie (0);
  n = read (), m = read ();
  for (int i = 1; i <= n; ++i)
    a[i] = read ();
  for (int i = a[1]; i <= a[n]; ++i)
    fa[i] = i;
  int o = 0;
  for (int i = 1, l = a[1], r = a[n]; i <= m; ++i)
    {
      int x = read ();
      if (o < l)
        o += x;
      else
        o -= x;
      if (l <= o && r >= o)
        {
          ans[o] = i;
          if (o - l < r - o)
            {
              for (int i = l; i < o; ++i)
                fa[i] = 2 * o - i, v[i] ^= 1;
              l = o + 1;
            }
          else
            {
              for (int i = r; i > o; --i)
                fa[i] = 2 * o - i, v[i] ^= 1;
              r = o - 1;
            }
        }
    }
  for (int i = 1; i <= n; ++i)
    {
      int x = find (a[i]);
      if (ans[x])
        std::cout << "Yes " << ans[x] << '\n';
      else
        std::cout << "No " << (v[a[i]] ? o - x : x - o) << '\n';
    }
}