Day 0

坐高铁，住宾馆，写烂题，大概没有什么好说的就咕咕咕了吧=x=

Day 1

早上7:30起床，匆匆忙忙赶到酒店大厅吃了顿早饭就拄着拐杖上路了（中间差点摔一跤==果然我还是不能驾驭的了拐杖啊Qw）
7:50到达长沙一中，轻松快乐地开始了一天的被吊打学习。上午的任务是一套毒瘤题 （被大佬———>说是水题所以划掉了）

T1 帽子戏法

一道非常非常烂的暴力，立方体区间染色统计，n<=40，是个人都A了。然而本蒟蒻不知为啥写起了三维前缀和，结果式子推错果断爆零了Qw

T2 最长序列

题目描述是给定进栈序列，求出字典序最大的出栈序列。对进栈出栈顺序进行模拟推导，易得若当前数字之后没有大于该数字的，该数字即可出栈。由此，该问题转化为动态区间最值，直接单点修改区间查询最值线段树即可。时间复杂度O(n\ log\ n)。
P.S.:考后听大佬说可以模拟O(n)搞定，只是听不懂==我大概是太弱了吧==
（据说本题完全达不到提高组D1T2难度，但是蒟蒻根本不在乎这些==）

T3 思考熊的马拉松

（思考熊是啥）
大概是本场最难。然而T1的三维前缀和和T2的线段树调试几乎花掉了所有时间，题面基本没看。下午认真仔细的看完之后表示只会暴力好吧Qw，果断摸一眼题解
首先由统计跑的比谁都快的熊跑完之前的“套圈”次数知统计范围是从0时刻到 \frac{LA}{v_{max}} ，对于每两只熊 v_{i} 和 v_{j}(v_{j}>v_{i} )，易知v_{j}“套圈”一次v_{i}需 a_{ij}=\left \lfloor \frac{A}{v_{j}-v_{i}} \right \rfloor 时间，则总”套圈”次数为
\frac{LA}{v_{max}} / a_{ij} = \left \lfloor \frac{L ( v_{j}-v_{i} )}{v_{max}} \right \rfloor。
则得出答案为
\sum_{i=1}^{n} \sum_{j=i+1}^{n} a_{ij} = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \left \lfloor \frac{L(v_{j}-v_{i} )}{v_{max}} \right \rfloor
此时对v进行排序，O(n^{2})枚举即可得出答案。
然而这个算法对于本题10组数据， n<=10^{5}的数据范围而言，还是\mathit{Too\ young, too\ simple}。是时候寻找比西方记者跑的还快的算法了！
对于上面的式子 \sum_{i=1}^{n} \sum_{j=i+1}^{n} \left \lfloor \frac{L(v_{j}-v_{i} )}{v_{max}} \right \rfloor ，我们强行忽略向下取整，进行展开，得
\sum_{i=1}^{n} \sum_{j=i+1}^{n} \left \lfloor \frac{L(v_{j}-v_{i} )}{v_{max}} \right \rfloor = \sum_{i=1}^{n} \left [ \left(n-2*i+1 \right)\left \lfloor \frac{Lv_{i}}{v_{max}} \right \rfloor \right ]
接下来考虑由忽略向下取整带来的误差。易知
\left \lfloor a-b \right \rfloor = \left \lfloor a \right \rfloor – \left \lfloor b \right \rfloor + \left \lfloor \lbrace a \rbrace – \lbrace b \rbrace \right \rfloor
则
\left \lfloor \frac{L \left(v_{j}-v_{i} \right )}{v_{max}} \right \rfloor = \left \lfloor \frac{Lv_{j}}{v_{max}} \right \rfloor – \left \lfloor \frac{Lv_{i}}{v_{max}} \right \rfloor + \left \lfloor \lbrace \frac{Lv_{j}}{v_{max}} \rbrace – \lbrace \frac{Lv_{j}}{v_{max}} \rbrace \right \rfloor
考虑到 \lbrace \frac{Lv}{v_{max}} \rbrace = \frac{Lv \mod v_{max}}{v_{max}} ,则 \left \lfloor \frac{L \left(v_{j}-v_{i} \right )}{v_{max}} \right \rfloor = \left \lfloor \frac{Lv_{j}}{v_{max}} \right \rfloor – \left \lfloor \frac{Lv_{i}}{v_{max}} \right \rfloor + \left \lfloor \frac{Lv_{j} \mod v_{max}}{v_{max}} – \frac{Lv_{i} \mod v_{max}}{v_{max}} \right \rfloor 。
设 m_{i} = \frac{Lv_{i} \mod v_{max}}{v_{max}} , m_{j} = \frac{Lv_{j} \mod v_{max}}{v_{max}} 。对m_{i}与m_{j}进行讨论。
当 m_{j} \geqslant m_{i} 时，显然 \left \lfloor \frac{L \left(v_{j}-v_{i} \right )}{v_{max}} \right \rfloor = \left \lfloor \frac{Lv_{j}}{v_{max}} \right \rfloor – \left \lfloor \frac{Lv_{i}}{v_{max}} \right \rfloor 。
当 m_{j} \lt m_{i} 时，则 \left \lfloor \frac{L \left(v_{j}-v_{i} \right )}{v_{max}} \right \rfloor = \left \lfloor \frac{Lv_{j}}{v_{max}} \right \rfloor – \left \lfloor \frac{Lv_{i}}{v_{max}} \right \rfloor -1 。
此时求出m数组的逆序对个数b,则答案为 \sum_{i=1}^{n} \left [ \left(n-2*i+1 \right)\left \lfloor \frac{Lv_{i}}{v_{max}} \right \rfloor \right ] – b
该算法时间复杂度为O(n\ log\ n),通过所有测试点。

下午迎来了两位长沙一中的AK巨神讲题，期间偶然发现在座的ouuan（可惜对面似乎并不认识我们==），为T3准备切掉了Luogu P1908。Day 1至此结束==。