Day1

没什么感觉便到了武汉，这里似乎和成都也没什么不同，下榻的酒店周围非常奇妙，明明是城乡结合部却异常繁华。
开摆！

Day2

记忆文件缺失.jpg

Day3

昨天晚上睡得比较晚，今天好想睡觉。。。
三道阴间分块/数据结构题，全部写暴力可以得到199的高分。

T1：
给定长度为 \(n\) 的序列，每次给定\(l,r\) ，查询 \(\sum_{i=l}^{r}2^{a_i}\)的二进制表示中 \(1\) 的个数是多少。
首先可以知道一个数最多对它之后的\(log\)位造成贡献，于是可以对序列离散化。
然后考虑回滚莫队怎么做。
显然对于每一群左端点在同一块的询问，右端点每次移动只贡献一次，然而左端点的贡献不好算，考虑优化左端点的贡献。
根据左端点的位置将值域分成 \(\sqrt{n}\) 块，每一块内维护一个int存最开始的log位和接下来连续的1最多到哪里。各种复杂度均摊下来之后是每个块向下一个块只进位一次。

T2：
单点修改，查区间内长度不超过 \(c\) （给定的数）的最大子段和。
按照c分块，块内部是一个单点修改求最大子段和，线段树维护。
再在所有的块上套一棵线段树维护答案。
对于区间间的答案，将右边的前缀max和左边的后缀max对齐后发现要求的是对应位置的和的最大值，同时要支持两者的区间加，线段树维护。

T3：
给定a数组和排列b，每次询问给出l，r，询问所有\(l<=b_i<=r\)中所有i在a中形成的连通块内部各自的小z的袜子的和。
第一种做法：考虑先将所有的\(a_i\)按照数从小到大排序，相同的数构成一段连续的序列，序列内部再按在原序列中的下标排序。此时相邻的两个数相同的数造成贡献仅当原下标对应y的区间最大和最小值都被选了。
再对处理后的序列分块，块内设有\(B\)个数，则可以预处理出\(B^2\)种选l，r对应的答案和前后缀最大连续段。直接拿询问上去跑。
直接开数组开不下，可以只维护相邻的两个块，算对每一个答案的贡献。
第二种做法：对颜色根号分治，颜色个数大于\(\sqrt{n}\)时跑莫队，小于\(\sqrt{n}\)二维数点。