Segment Tree Beats template bug in .range_max()

[dxtvzw]

Segment Tree Beats template code does not work when the method .range_max() is called as a query.

Here are two submissions that differ only in the segtree beats implementation:

• from this repo -- RE
• from Nyaan -- AC

The queries used in this problem are:

range_add()
range_chmax()
range_chmin()
range_max()

Stress testing finds the following input on which the code REs: pastebin

I don't know exactly where the bug is, but the implementation doesn't work as expected.

P.S. This costed me one hour of contest and a failed problem(

[maspypy]

small RE case

1
2 3 5
1 2 1
1 -1 -1

[maspypy]

RE with

const int K = 10;
segment_tree_beats beats(K);

int main() {
  beats.range_add(3, 6, 0);
  return 0;
}

[maspypy]

RE

int main() {
  segment_tree_beats beats(10);
  beats.range_add(3, 6, 0);
  return 0;
}

NOT RE

int main() {
  vector<long long> a = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  segment_tree_beats beats(ALL(a));
  beats.range_add(3, 6, 0);
  return 0;
}

[maspypy]

Therefore, it seems there is an issue with the initialization of this Segtree Beats.
(So, the behavior of correct.cpp for the Library Checker problem might be correct.)

[maspypy]

#257

[maspypy]

segment_tree_beats(int n_) {}
を削除するというだけの修正を行うつもりです，一応お知らせしておきます（ @kmyk ）

[maspypy]

@dxtvzw

Thank you for the bug report.

I have confirmed that a bug occurs when using beats(n) instead of beats(first, last) in the constructor of segtree_beats.
While I have not investigated further details, I have addressed the issue by removing the implementation of beats(n).

Regarding your submission, the version with the constructor replaced resulted in TLE.
https://codeforces.com/contest/2053/submission/299826920

However, I have confirmed that it outputs correct results for small_random test cases.

[xdoju]

It looks tagging the node by UPDATE doesn't make the node to propagate its value to its children, because it sets the node's lazy_update as INT64_MAX.

I think that lazy_update variable is useless in the program. It cannot be other value rather than INT64_MAX.