估计大家也像我一样被卡得心力交瘁了吧。。。

终于 AC 此题，在这里留下几点 tips 供大家参考

卡空间：

1. 数组尽可能少开，那些 b, p, l, r 的全部即时读入或用滚动数组（比如 last_p, b1, b2 之类的，不过千万注意只有在 i > 2 时才需要滚动 b 数组！）

2. 能开 int 就不要开 longlong，能开 longlong 就不要用高精度或__int128；只有最后计算 ans 时才真正需要高精度！

3. 不要用额外的 a 数组，直接用前缀和 s 数组存，并 s[i] += s[i-1] 求前缀和

卡时间：

1. 用一个 f 数组记录 val(i) = 2 * s[j] - s[g[j]]，这样就不用每次重新算（其实是空间换时间）

2. 高精度会被卡，所以要么用 __int128，要么写压位高精（其实这个我不会（逃

最后亿点提醒。。。

type = 1 时，若按照题目给出的方法计算 b 数组，有两点需要注意：

1. 虽然最终 b[i] 是 int 范围内的数，但是计算过程中可能溢出，因此一定要开好 longlong

2. 基于同样的原因，（虽说费时）中途该取模的地方一定不能省，否则可能会 WA