Magical Girl Lya Problem Setting Report

“Magical Girl Lya” Problem Setting Report

I originally intended to follow the format of that article “Problem Setting Report for ” from the IOI 2024 National Training Team papers, but I realized this crappy problem has absolutely no depth and cannot be imitated at all, so I’ll just write it like this.
Part of the inspiration for this problem came from $P2572 [SCOI2010] "Sequence Operation"$; by the way, I also temporarily strengthened it on the afternoon of the day before the contest.

Problem

Given a 01 sequence, with operations for interval reversal and interval assignment, query the longest alternating 01 substring within an interval. $(1 \le n, m \le 5 \times 10^5)$.

O(mlogn) Solution

Obviously, interval reversal and interval assignment are standard segment tree operations; the key to this problem lies in the merging of nodes in the segment tree.

My approach is to maintain the length of the longest interval starting with 0/1 from the left/right of the interval represented by the node, and the length of the longest interval starting with 0/1. When performing pull (or pushup), taking the length of the interval starting with 0 from the leftmost side as an example: if its length equals the total length of the left child node, then directly append the corresponding length of the interval starting with 0/1 from the leftmost side of the right child node based on the parity of the left child node’s length—whether it is 0 or 1 follows the principle of “odd changes, even remains unchanged”; otherwise, inherit directly. The other three cases are the same. As for the length of the longest interval starting with 0/1, one only needs to take the max of the left and right child nodes, and then take a max for the middle part. The middle part is determined by the value on the right side of the left child node to select the corresponding value on the left side of the right child node so that they can be connected, and then it is done.

It is indeed a bit heavy implementation; I also spent quite a while writing and debugging it.

Code

#include <bits/stdc++.h>
#define lc p << 1
#define rc p << 1 | 1
#define mid (s + t) / 2

constexpr int N = 5e5;

struct Seg {
  int llen0 = 0, llen1 = 0, rlen0 = 0, rlen1 = 0;
  int maxlen0 = 0, maxlen1 = 0;
  int len = 0;
};

std::vector<std::array<int, 2>> tag(N << 2);
std::vector<Seg> seg(N << 2);
std::vector<int> a(N + 1);

Seg merge(const Seg &x, const Seg &y) {
  if (!y.len) return x;
  if (!x.len) return y;
  auto s = Seg{
    x.llen0 == x.len ? x.llen0 + (x.len % 2 == 0 ? y.llen0 : y.llen1) : x.llen0,
    x.llen1 == x.len ? x.llen1 + (x.len % 2 == 0 ? y.llen1 : y.llen0) : x.llen1,
    y.rlen0 == y.len ? y.rlen0 + (y.len % 2 == 0 ? x.rlen0 : x.rlen1) : y.rlen0,
    y.rlen1 == y.len ? y.rlen1 + (y.len % 2 == 0 ? x.rlen1 : x.rlen0) : y.rlen1,
    std::max(x.maxlen0, y.maxlen0),
    std::max(x.maxlen1, y.maxlen1),
    x.len + y.len,
  };
  if (x.rlen0) {
    if (x.rlen0 % 2) {
      s.maxlen1 = std::max(s.maxlen1, x.rlen0 + y.llen1);
    } else {
      s.maxlen0 = std::max(s.maxlen0, x.rlen0 + y.llen1);
    }
  }
  if (x.rlen1) {
    if (x.rlen1 % 2) {
      s.maxlen0 = std::max(s.maxlen0, x.rlen1 + y.llen0);
    } else {
      s.maxlen1 = std::max(s.maxlen1, x.rlen1 + y.llen0);
    }
  }
  return s;
}

void exec(int s, int t, int p, int typ) {
  if (typ == 0) {
    tag[p] = {1, 0};
    seg[p] = {1, 0, 1, 0, 1, 0, seg[p].len};
  }
  if (typ == 1) {
    tag[p][1] ^= 1;
    seg[p] = {seg[p].llen1, seg[p].llen0, seg[p].rlen1, seg[p].rlen0, seg[p].maxlen1, seg[p].maxlen0, seg[p].len};
  }
}

void push(int s, int t, int p) {
  if (tag[p][0]) {
    exec(s, mid, lc, 0);
    exec(mid + 1, t, rc, 0);
  }
  if (tag[p][1]) {
    exec(s, mid, lc, 1);
    exec(mid + 1, t, rc, 1);
  }
  tag[p] = {0, 0};
}

void pull(int p) {
  seg[p] = merge(seg[lc], seg[rc]);
}

void build(int s, int t, int p) {
  seg[p].len = t - s + 1;
  if (s == t) {
    seg[p] = {!a[s], a[s], !a[s], a[s], !a[s], a[s], 1};
    return;
  }
  build(s, mid, lc);
  build(mid + 1, t, rc);
  pull(p);
}

// 只可能区间赋值为0
void reset(int l, int r, int s, int t, int p) {
  if (r < s || l > t)
    return;
  if (l <= s && t <= r) {
    exec(s, t, p, 0);
    return;
  }
  push(s, t, p);
  reset(l, r, s, mid, lc);
  reset(l, r, mid + 1, t, rc);
  pull(p);
}

void rev(int l, int r, int s, int t, int p) {
  if (r < s || l > t)
    return;
  if (l <= s && t <= r) {
    exec(s, t, p, 1);
    return;
  }
  push(s, t, p);
  rev(l, r, s, mid, lc);
  rev(l, r, mid + 1, t, rc);
  pull(p);
}

Seg query(int l, int r, int s, int t, int p) {
  if (l > t || r < s) return {};
  if (l <= s && t <= r) {
    return seg[p];
  }
  push(s, t, p);
  auto sl = query(l, r, s, mid, lc);
  auto rl = query(l, r, mid + 1, t, rc);
  return merge(sl, rl);
}

signed main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int n, m;
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    a[i] &= 1;
  }
  build(1, n, 1);
  for (int i = 1; i <= m; i++) {
    int op, l, r, x;
    std::cin >> op;
    if (op == 1 || op == 3) {
      std::cin >> l >> r >> x;
      if (x & 1) {
        rev(l, r, 1, n, 1);
      }
    } else if (op == 2) {
      std::cin >> l >> r >> x;
      if (x & 1 ^ 1) {
        reset(l, r, 1, n, 1);
      }
    } else {
      std::cin >> l >> r;
      int len = r - l + 1;
      auto s = query(l, r, 1, n, 1);
      std::cout << std::max(s.maxlen0, s.maxlen1) << '\n';
    }
  }

  return 0;
}

Old Version Problem

Given a 01 sequence, with operations for interval reversal and interval assignment, query whether the numbers within an interval are all alternating 01. $(1 \le n, m \le 5 \times 10^5)$.

Old Version Problem O(mlogn) Solution

The interval operations remain unchanged, but one only needs to maintain the interval length of the node and the length of the 0/1 string starting from the left side; finally, just check if the string length equals the interval length.

Old Version Problem Code

#include <bits/stdc++.h>
#define lc p << 1
#define rc p << 1 | 1
#define mid (s + t) / 2

constexpr int N = 5e5;

struct Seg {
  int llen0 = 0, llen1 = 0;
  int len = 0;
};

std::vector<std::array<int, 2>> tag(N << 2);
std::vector<Seg> seg(N << 2);
std::vector<int> a(N + 1);

Seg merge(const Seg &x, const Seg &y) {
  return Seg{
    x.llen0 == x.len ? x.llen0 + (x.len % 2 == 0 ? y.llen0 : y.llen1) : x.llen0,
    x.llen1 == x.len ? x.llen1 + (x.len % 2 == 0 ? y.llen1 : y.llen0) : x.llen1,
    x.len + y.len,
  };
}

void exec(int s, int t, int p, int typ) {
  if (typ == 0) {
    tag[p] = {1, 0};
    seg[p] = {1, 0, 1};
  }
  if (typ == 1) {
    tag[p][1] ^= 1;
    seg[p] = {seg[p].llen1, seg[p].llen0, seg[p].len};
  }
}

void push(int s, int t, int p) {
  if (tag[p][0]) {
    exec(s, mid, lc, 0);
    exec(mid + 1, t, rc, 0);
  }
  if (tag[p][1]) {
    exec(s, mid, lc, 1);
    exec(mid + 1, t, rc, 1);
  }
  tag[p] = {0, 0};
}

void pull(int p) {
  seg[p] = merge(seg[lc], seg[rc]);
}

void build(int s, int t, int p) {
  seg[p].len = t - s + 1;
  if (s == t) {
    seg[p] = {!a[s], a[s], 1};
    return;
  }
  build(s, mid, lc);
  build(mid + 1, t, rc);
  pull(p);
}

// 只可能区间赋值为0
void reset(int l, int r, int s, int t, int p) {
  if (r < s || l > t)
    return;
  if (l <= s && t <= r) {
    exec(s, t, p, 0);
    return;
  }
  push(s, t, p);
  reset(l, r, s, mid, lc);
  reset(l, r, mid + 1, t, rc);
  pull(p);
}

void rev(int l, int r, int s, int t, int p) {
  if (r < s || l > t)
    return;
  if (l <= s && t <= r) {
    exec(s, t, p, 1);
    return;
  }
  push(s, t, p);
  rev(l, r, s, mid, lc);
  rev(l, r, mid + 1, t, rc);
  pull(p);
}

Seg query(int l, int r, int s, int t, int p) {
  if (l > t || r < s) return {};
  if (l <= s && t <= r) {
    return seg[p];
  }
  push(s, t, p);
  return merge(query(l, r, s, mid, lc), query(l, r, mid + 1, t, rc));
}

signed main() {
//   if (argc > 1) freopen(argv[1], "r", stdin);
//   if (argc > 2) freopen(argv[2], "w", stdout);
  std::cin.tie(nullptr)->sync_with_stdio(false);

  auto start = std::chrono::high_resolution_clock::now();

  int n, m;
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    a[i] &= 1;
  }
  build(1, n, 1);
  for (int i = 1; i <= m; i++) {
    int op, l, r, x;
    std::cin >> op;
    if (op == 1 || op == 3) {
      std::cin >> l >> r >> x;
      if (x & 1) {
        rev(l, r, 1, n, 1);
      }
    } else if (op == 2) {
      std::cin >> l >> r >> x;
      if (x & 1 ^ 1) {
        reset(l, r, 1, n, 1);
      }
    } else {
      std::cin >> l >> r;
      int len = r - l + 1;
      auto s = query(l, r, 1, n, 1);
      std::cout << (s.llen0 == len || s.llen1 == len ? "YES" : "NO") << '\n';
    }
  }

  return 0;
}

Postscript

I originally thought there might be some hacky solutions? For example, using bitset, which might achieve O(mn/w), so I specifically uploaded the first three test points with n and m maxed out, and even increased it to 5e5, but until now I haven’t implemented it, and no one else has written it that way either. However, it probably wouldn’t pass anyway, right? Even at the 2e5 level?

Honestly, I was super happy when zhw got AC during the contest; at least it proved that the first problem I set myself for the first contest I organized didn’t have bugs. When he first got WA, I couldn’t help but start checking his code and my brute force code during class, but fortunately, he got AC in the end. By the way, the code he wrote was twice as fast as mine; I don’t know if it was due to fast I/O or something else, I didn’t look closely.

Having said that, perhaps it would have been better to write the problem title into the problem description?

And perhaps adding a prefix to the test data points to make them test in order would also be good?

As for this contest, I don’t know if it was due to the shuffled order of problems, but the number of solved problems and the objective difficulty of the problems were actually completely inverted.

Moreover, it is truly regrettable that tiome and rainydyas solved the problem exactly 22 seconds and 1 minute 35 seconds after the contest ended.

As for changing the problem title to “The bright moon illumines the drifted snow”, it was even a whim on the day of the contest (lol); this works out perfectly, next time it will be “The northern wind blows fierce and mournful”. Maybe next time I should write an announcement to remind everyone that the difficulty is shuffled…

2024/9/29 23:25