提高组模拟赛， shanganze 2h AK
me 只会两道,被踩爆了
把简单题想复杂了，写太慢了
1.
谔谔，不知道为什么浪费好长时间
就做个前缀和
然后想用 set 但求不了 个数
然后写了个线段树
2.
一眼
每一列答案单调，一起算
3.
考虑枚举 gcd
然后是个计算直径
这样还并不能通过
考虑到数据随机，所以 \(\sum num_{gcd}\) 是 \(n \log n\) 级别
所以每次计算直径时只把用到的边加进来即可
4.
一眼想到 boder 了，然后就寄了
先考虑字符串构造的过程
就是把大写放右边，小写放左边
然后发现可以用题目中提示的哈希 \(O(1)\) 判断弱循环节
考虑每一个 弱循环节 \(x\)
出现位置一定是一段连续的区间 \(x , r_x\)
因为每个字符要对应的字符其实是固定的，不合法后后面一定不合法，而且 \(x\) 时刻一定合法
然后可以对每个 \(x\) 二分出其出现区间
询问变成
区间 \(x \le q \le r_x\) 的 \(x_{max}\)
然后这个东西可以对 \(x \le q \le r_x\) 扫描线， \(x\) 在 \(x\) 时刻激活，在 \(r_x + 1\) 删除
然后查询区间 max
相关新闻
