本提示可能只适用于平衡树。
如果你 10 分:
注意 pushup 的写法:
t[x].tot = t[l].tot + 1 + t[r].tot - (t[x].col == t[l].rc) - (t[x].col == t[r].lc);
这样的写法未必是错的,但无疑是十分危险的。
一旦你的 0 号节点的信息被修改过,这样的 pushup 有可能导致出现问题。
因此建议这样写 pushup:
t[x].tot = 1;
if(l)
t[x].tot += t[l].tot - (t[x].col == t[l].rc);
if(r)
t[x].tot += t[r].tot - (t[x].col == t[r].lc);
如果你 70 分:
注意 C 询问时,可能出现整个环都是一个颜色的情况。
如果你回答 C 询问的方式形如:
int count() { return t[rt].tot - (t[rt].lc == t[rt].rc); }
你可能得到的答案为 0,因此你需要把你得到的答案和 1 取个 max。