这个题也是看了一晚上，各种题解各种论文各种ppt emmmmmmm
话说发现真的线段树这东西不能看别人的代码，怎么看怎么看不懂，非得自己写一遍才是。感觉市面上常见的线段树也就两种写法，一种是pushdown以及在update预判返回的时候把维护子节点的事情做了，维护只维护当前节点所以又叫pushup，另一种是pushdown和预判都只改变标记，而所有的维护都交给maintain来做，(⊙﹏⊙)我一直写的是后一种，但是这里写前一种貌似比较方便（🌫）因为update在这里兼具了更新和搜索的功能，所以最好是在pushdown的时候就把维护子节点的事情做了。（感觉自己对pushdown标记的理解之前还是不到位啊emmmm还是得写）
继续阅读“[线段树][区间最值操作][论文题][难] HDU5306 Gorgeous Sequence”
比赛时候wa到哭，后来发现优化错了，把优化去掉玄学AC（这可是三个for啊这复杂度）
后来想一下，之所以能玄学过，就是因为题目保证了一定有解，如果无解的话那三个for还真有可能跑一遍，不说三个了两个跑一遍都够呛。。
我这里的玄学算法就是，对横纵坐标分别标记，当一个点在纵方向上被至少n-1个举行覆盖的时候才考虑这个横坐标，然后在这个横坐标上的所有纵坐标，也只有当被至少n-1个覆盖到的时候才考虑它，当然这只是必要条件而不是充分条件，然后对于一个要考虑的点遍历所有矩形（没错就是这么暴力）如果有超过1个没覆盖到这个点就退出直接不考虑。。。就这么超级暴力+剪枝，玄学过了cf的所有数据，emmm 继续阅读“[CF][区间标记方法][暴力] codeforces 1028C Rectangles”
连续做的又一道预处理+贪心的题目，一开始因为复杂度的原因一直没有下手，看了官方题解才意识到复杂度是nlogn，因为调和级数求和是logn。。。
贪心策略就是每次都选择能覆盖到的范围内的最右边的非block的点，如果这个点等于原来的出发点就直接return -1，因为说明不可行。这时候我们需要预处理出来每个点对应的它左边离他最近的那个非block的点（也有可能是他自己），当然这个预处理就很简单了。主要的思考难度在于没想到可以这么预处理，其次是复杂度的分析没有到位。
错误的点的话是对题意的理解：这里要求覆盖整条线段，而不仅仅是覆盖整点，但是放灯却只能在0到n-1的整点上放。。。第二个错误是如果0处禁止放的话那直接就是输出-1了，原来的算法在这里会失效，因为那个总是多考虑一步，而没有考虑出发点是不是合法的。
首先确定，什么时候是NO，因为把ai全部异或起来一定是整个矩阵全异或，bi同理所以这俩数字应该相等，xor为0，如果不为0一定是不存在的。所以，如果存在，那么a全部xor和b全部xor一定是相等的，记为tmp
否则的话，把b1到bm-1全放到第一行的左边m-1个空位，剩下的右边那个补上一个t使得这一行xor为a1，此时最右边一列的xor为tmp^a1^t=tmp^(b1^bi..^bm-1)==bm，所以这样构造的矩阵一定满足要求！！！
继续阅读“[XOR][思维][构造] codeforces 1016D Vasya And The Matrix”
还是找星星，但是数据量升高了，不能用n^3复杂度的算法了
这里可以用六个预处理的矩阵来表示信息，前四个分别为上下左右到当前位置的连续的星个数，这样就不用每次到一个坐标都从新求了。后两个分别为两个标记矩阵，这里的思想很像之前有个AC自动机替换禁忌词的题目，因为那个题目禁忌词可能互相冲突，互相交错，互相包含，而这个里面的不同的星星也会出现这种情况，所以采用了类似的方法：在左端点标记+1，右端点标记-1，然后再把矩阵从左往右过一遍，h[i][j]=h[i][j]+h[i][j-1]，这样的话，就可以确定出来一个点有没有被星星覆盖到：如果他的h或v大于0就被覆盖了，否则就没有。所有的矩阵预处理都是n^2的复杂度，总共6*n^2大概。
继续阅读“[思维][预处理][区间信息技巧] codeforces 1015E2 Stars Drawing (Hard Edition)”
都是泪啊啊啊啊啊啊啊啊啊啊啊啊啊
汪聚代哥一队打了79，v5的一批Ooooooorz 我们就很惨了，4题，300多名。。据说校前三可以去现场赛，然后我们第六凉凉。。
这个题真的是。。。真的是就差了那么一点，一层窗户纸，捅破就恍然大悟，过不去就死活想不出来了。我甚至也想到了官方题解中的类似于二分图的配置，可是没想到怎么去合并，不对，是我根本就没想合并。。。。。根本就没有意识到传递性啊啊啊啊啊啊啊啊惨的一批
最扯淡的是后面发现是原题。。。虽然有一点不一样，但是能理解原题的话就完全可以做这个了，啊啊啊啊啊啊啊啊啊啊啊啊啊啊
然后lyq差点把1005做出来，沙雕数论题，她会推公式不会实现，我会实现不懂公式，如果我们不是云操作的话可能就做出来了，在线交流真的难受。。。
还有就是1007，赛后看了一眼完全可做的样子，然而最后思维全死在这个A题。。。。决定去cf上刷一波进阶贪心了aaaaaaaa
继续阅读“[比赛][思维][贪心] CCPC网络赛 HDU6438 Buy and Resell”
https://cn.vjudge.net/problem/HDU-1299
学到了设k求整数解个数的方法？emmm似乎非常常用的样子
wa在ans写在if外面了，这样会多乘。。。
这个题的官方题解简直玄学，根号5取模，然后转化成等比数列，服气。
还好评论区有人给了更简便的做法：广义斐波那契数列。任意两个广义斐波那契数列相加仍然是斐波那契数列，而且只要知道了前两项的和就可以知道任意一项的和和任意一项的开始的前缀和。比如若第一二项为a,b,那么手推几下就可以发现，fab[n]=af[n-2]+bf[n-1]，然后前缀和是fsum[n]=f[n+2]-f[2]（这个也很容易推出来，甚至奇数项偶数项分别的和都能推出来）,然后这时候就很简单了，对于每一个区间只需要保存其左端点处的a，b就可以了，把ab做成lazy tag就可以实现区间修改了。注意这时候pushdown的时候，对于右孩子要计算出来fibab到这个点是多大才可以。一如既往的，add操作需要在maintain里加单节点特判（我也不知道为什么但是已经习惯了）还有一点注意ta一定是+的第一个，tb一定是+的第二个。
准备再用等比数列方法做一遍吧，看看是怎么个操作。。今天写了一下等比数列的操作方法，感觉比原来的方法简单emmm
继续阅读“[线段树][区间等比/等差数列修改] CodeForces – 446C DZY Loves Fibonacci Numbers”
Huh，比赛的时候花了三个小时把这个正解是用后缀自动机的题肝了出来，我也不知道我怎么做到的。
想了很多策略之后发现自己是错的就很难受，最后终于想到正确策略：在height数组上做一个长度为k的滑窗，每次检查滑窗两端点之外的height是否比这一整段内的最小值大，注意这里面的一整段最小值M就是这一整段的公共最长公共前缀的长度，这个东西和他的前缀是在这里出现了k次的，那么怎么知道他是不是在滑窗外面出现呢，和两端点的height比较一下就行了，取两端点中的最大值P，这个说明是之外的点与滑窗两个端点的最大公共前缀，而所有的在滑窗内的满足P<len<=M的前缀都是仅出现了一次的子串！！！
wa的话，需要特判k为1的情况，，因为height这个数组是个间隔定义的东西，所以这种只有一个的需要单独处理，这时候实际上区间内的最长公共前缀就是排名在此的后缀本身
https://cn.vjudge.net/problem/CodeForces-920F
跟上一道HDU的题目很像，也是求快速收敛函数的和，因为有结论n的约数个数期望为sqrt(n)。每次遇到一个数就将其质因数分解然后求约数个数，这里可以开一个1e6的数组把处理过的n存下来，记忆化，就可以省下来很多时间（大概吧呵呵）。另外一个需要注意的点是收敛的终点可能是1也可能是2，我这里的方法是把读入的1全变成2，然后输出的时候减去前缀和差分就行了，因为1是怎么都不会变的，2也是不会变的，这样可以保证正确。
