SPOJ GSS 系列杀青

算是题单吧

太壮观了兄弟们，可是之前 \(8\) 题难度评分都高一档的啊。

GSS1

区间最大子段和板子题，用线段树随便过。

GSS2

相同的数只算一次，我们离线询问，顺序插入数组中的值，设这个值上一次出现在 \(pos\)（经典套路），每次插入的时候都 \([pos+1,i]\) 区间加当前值，表示这些位置的后缀和加这么多。到了一个询问 \([l,i]\) 时等价于查询 \([l,i]\) 位置后缀和的历史最大值，用维护历史最值的线段树即可。

GSS3

就是 GSS1 的带单点修版，同样简单。

GSS4

区间开方区间求和板子。

势能分析一个数 \(x\) 开方次数 \(O(\log \log x)\)，在数组上建并查集，快速跳过值为 \(1\) 的位置。

GSS5

询问左 / 右端点分别在给定范围内的最大区间和。

同 GSS1，维护区间前后缀 \(\max\) 和区间内 \(\max\) 然后分讨即可。