太壮观了兄弟们,可是之前 \(8\) 题难度评分都高一档的啊。
GSS1
区间最大子段和板子题,用线段树随便过。
GSS2
相同的数只算一次,我们离线询问,顺序插入数组中的值,设这个值上一次出现在 \(pos\)(经典套路),每次插入的时候都 \([pos+1,i]\) 区间加当前值,表示这些位置的后缀和加这么多。到了一个询问 \([l,i]\) 时等价于查询 \([l,i]\) 位置后缀和的历史最大值,用维护历史最值的线段树即可。
GSS3
就是 GSS1 的带单点修版,同样简单。
GSS4
区间开方区间求和板子。
势能分析一个数 \(x\) 开方次数 \(O(\log \log x)\),在数组上建并查集,快速跳过值为 \(1\) 的位置。
GSS5
询问左 / 右端点分别在给定范围内的最大区间和。
同 GSS1,维护区间前后缀 \(\max\) 和区间内 \(\max\) 然后分讨即可。
标签:GSS,后缀,max,pos,杀青,SPOJ,GSS1,区间 From: https://www.cnblogs.com/shaojia/p/16751485.html