这题数据有锅吧

题目中明确说了

1\leq x_i\leq 10^{18}

，然而在树链剖分中，如果线段树pushup时将所有大于

10^{18}

的乘积全部变成

10^{18}+1

会错。

这竟然是Wrong answer on test 23的最终原因。

CPP

inline void pushup(int rt) {
    if ((long double)T[rt<<1].sum*T[rt<<1|1].sum>1e18) T[rt].sum=1e18+1;//没错就是这里，改成1e18+5000
    else T[rt].sum=T[rt<<1].sum*T[rt<<1|1].sum;
}

但是如果针对本题的数据范围，这两种操作是等价的

经本人验证，改成1e18+100仍然会wrong answer on test 44

讨论操作

回复

相关推荐

这题数据有锅吧