Day 4

似乎还有一天就要结束在长沙一中五天的集训了呢=u 那么今天就稍微写一点废话感想吧
四天的题目，不得不说，基本都值得一做（AK的dalao们务必装作没看见！！！）。每一天的题目都能学到新的东西=v（比如Day 1的考场打线段树，Day 2的矩阵加速，Day 3的乘法逆元，以及今天的常数优化、DP推导等）
那么，来看看今天的题吧！=v

T1 贪吃蛇

第一题终于不是毒瘤数论啦！读完题面就能发现这是一道模拟题，使用队列保存蛇的身体所在的坐标，就能轻松愉快地AC第一题。
然而！对于边界条件的判断咱手抖打错了 == 于是100->85 == 无比快乐

T2 分糖果

根据提高组的惯例，T2又一次考察了DP。本题是Luogu上的一道原题
对于题目中给出的条件进行分析，可以发现

T3 排序

是的没错！这次的T3也需要用到求逆序对。不过这次更加直接，题面中直接要求求逆序对==
那么，该怎么处理呢？理解题意，发现对于前50%的数据可以使用O(mn\ log\ n)的算法，即对于每次询问，在数组中选取小于p_{i}的元素，放入另一个数组中，对这个数组进行排序后依次放回后求一遍逆序对即可。
但显然，该算法的时间复杂度还不够优秀，在测试中只能获得50分的好成绩。考虑如何优化。对于每一个数字，发现经过排序后每一个数字都不会产生逆序对，并且之后也不会再产生逆序对。那么，我们可以预处理每一位数字之后比它小的数字，即逆序对个数，每次询问时将其减去即可。
然而，我们仍需要花费O(n)的时间对数字进行选取。现在考虑一种更优的做法。我们维护对于每个下标区间中的最小值，每次询问时从a[p_{i}]到最小值这个区间中的逆序对个数减去即可。注意到一个数字只会导致总逆序对个数减小一次，那么，该算法的期望时间复杂度为O((n+m)\ log\ n)。

下午终于认出了CYJian巨佬（原来巨佬每天都给我们讲题啊QwQ） 晚自习颓了一会slay顺便被天泽龟吊打。回到宾馆摸完这篇日记=u