以下是本人做法，不保证正确

1.奇数-1，偶数按二进制分解即可

2.开桶记录，暴力$O(nw)$，偏要写平衡树也没有人拦你

3.根据后缀表达式建树，考虑改变节点的值会不会改变答案

4.dp，向上走向下走分类讨论，注意开long long和特判第一行