这道题,我这样用结构体写是对的
struct Node {
int sum, len, tag;
int val1, lv1, rv1;
int val0, lv0, rv0;
void merge(Node a, Node b) {
sum = a.sum + b.sum;
if(a.val1 == a.len) lv1 = a.len + b.lv1;
else lv1 = a.lv1;
if(a.val0 == a.len) lv0 = a.len + b.lv0;
else lv0 = a.lv0;
if(b.val1 == b.len) rv1 = b.len + a.rv1;
else rv1 = b.rv1;
if(b.val0 == b.len) rv0 = b.len + a.rv0;
else rv0 = b.rv0;
val1 = max(max(a.val1, b.val1), a.rv1 + b.lv1);
val0 = max(max(a.val0, b.val0), a.rv0 + b.lv0);
}
}t[MAXN << 2];
//...
t[o].merge(t[ls], t[rs]);//调用
但是如果这样写,就会出现神奇的答案:
struct Segment_tree {
struct Node {
int sum, len, tag;
int val1, lv1, rv1;
int val0, lv0, rv0;
}t[MAXN << 2];
Node merge(Node a, Node b) {
Node res;
res.sum = a.sum + b.sum;
if(a.val1 == a.len) res.lv1 = a.len + b.lv1;
else res.lv1 = a.lv1;
if(a.val0 == a.len) res.lv0 = a.len + b.lv0;
else res.lv0 = a.lv0;
if(b.val1 == b.len) res.rv1 = b.len + a.rv1;
else res.rv1 = b.rv1;
if(b.val0 == b.len) res.rv0 = b.len + a.rv0;
else res.rv0 = b.rv0;
res.val1 = max(max(a.val1, b.val1), a.rv1 + b.lv1);
res.val0 = max(max(a.val0, b.val0), a.rv0 + b.lv0);
return res;
}
//...
t[o] = merge(t[ls], t[rs]);//调用
追踪输出发现,有些节点的sum值是随机数。这个是什么问题呢? 求dalao赐教