Magical Girl Lya Proposition Report

Problem-Setting Report for “Magical Girl Lya”

Originally, I wanted to imitate the format of the “Problem-Setting Report for <World’s Sleeping Fairytale>” from the ioi2024 National Training Team papers, but I realized this crappy problem has no depth at all and can’t imitate it in the slightest, so I’ll just write it like this.
This problem was partly inspired by $P2572 [SCOI2010] 《序列操作》$, and by the way, I temporarily made it harder on the afternoon before the contest.

Problem

Given a 01 sequence, with range flip and range assignment operations, query the longest 01 alternating substring within a given range. $（1 \le n, m \le 5 \times 10^5）$.

O(mlogn) Approach

Obviously, range flip and range assignment are standard segment tree template operations. The key to this problem lies in merging the nodes in the segment tree.

My way of writing it is to maintain, for the interval represented by a node, the lengths of the longest intervals starting from the left/right that begin with 0/1, and the lengths of the longest intervals overall that begin with 0/1. During pull (or pushup), taking the length of the interval starting from the far left that begins with 0 as an example: if its length equals the total length of the left child, we directly append the corresponding length of the interval starting from the far left of the right child that begins with 0/1 based on the parity of the left child’s length—whether it’s 0 or 1 follows the “odd changes, even stays the same” rule; otherwise, we just inherit it directly. The other three are the same. As for the length of the longest interval beginning with 0/1, we just need to take a max of the left and right children, and then take a max with the middle part. The middle part is formed by choosing the corresponding left value of the right child based on the right value of the left child so that they can be connected, and then we’re done.

It is indeed a bit of a heavy implementation, and I spent quite a long time writing and debugging it too.

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 range flip and range assignment operations, query whether the numbers within a given range are all 01 alternating. $（1 \le n, m \le 5 \times 10^5）$.

Old Version Problem O(mlogn) Approach

The range operations remain unchanged, but what we maintain only needs to be the node’s interval length and the lengths of the 0/1 strings starting from the left. Finally, we just need to check whether 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

Originally, I was also thinking maybe there are some cheese approaches? For example, using bitset, which might achieve O(mn/w), so I specifically uploaded the first three new test cases with nm maxed out, and even raised the limit to 5e5, but up until now I haven’t implemented it, and no one else wrote it like that either. Though nine times out of ten 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 very first problem I set myself for the very first contest I organized didn’t have any flaws. When he first got wa, I couldn’t help but start checking his code and my brute-force code during class, but thankfully 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 because of fast I/O or something else, didn’t look closely.

Having said that, maybe it would be better to write the problem into the problem description?

And maybe adding a prefix to the test data points so they are tested in order would be good too?

As for this contest, I don’t know if it was because the problems were in random order, but the number of solves and the objective problem difficulty actually ended up being completely inverted.

Moreover, it was truly a pity that tiome and rainydyas passed the problem right at 22 seconds and 1 minute 35 seconds after the contest ended, respectively.

As for changing the problem title to “Bright Moon Shines O’er the Drifted Snow”, that was even a last-minute whim on the day of the contest (x. That works out nicely though, next time it will be “Fierce and Mournful Blows the Boreal Wind”, maybe next time I’ll have to write an announcement to remind everyone that the difficulties are in random order…

2024/9/29 23:25