开考没有一道题一眼，感觉要没，不好搞。开考就一直看T1，想出来20pts暴力解法，之后就一直停滞不前，尤其是T3直接蒙了。想了一个多小时还没开始写，感觉真的没了。开写T1暴力先放放，去搞T2，很快写出来但是被自己证伪了，于是去看T3。想出来一个完完全全的大搜索但是感觉连部分分都拿

开考题目难度应该是升序的，开T1发现看着不简单，就有点突突。T2看起来比较简单，想到了双指针，但是方向不对，搞了20min出不来就回去看T1。开写T1想出来就很好写了，想到两个点就可以组成一条边从而确定一个正方形（当然没有对角线），直接\(\mathcal{O}(n^2)\)暴力枚举判断就可以了，

说是总结这个东西很有帮助，所以就写一下。开题先看了一遍感觉前三题还有希望，第四题直接寄了，期望根本就不会，还是自己太菜。T2比较难看，T3感觉像裸的分组背包，T1看着好些，直接开题。开写T1很明显的前缀和维护，然后就去想双指针考虑单调性，发现既然是求余数怎么可能有单调性。然后

就是收集了trick。线段树的扩展用法单侧递归线段树历史最大值线段树(卢瑞恩)\(\text{SegmentTreeBeats}\)其中历史最大值线段树和\(\text{SegmentTreeBeats}\)的历史最值操作可以结合。如果由区间修改操作会影响\(\text{SegmentTreeBeats}\)的势能，具体的，每操作

信友队集训游记漫长的信友队集训营团队：提高1班这是我们的同学洛谷号：任子杭老师：_xuefeng徐驭凡：Saint_ying_xtf洪淇：2011qiqi冯思哲：fsz171411许禄海：xuluhai123王小鲁：Littlelu孙轩宇：孙轩宇sunxuanyu陈国栋：AK_CCF汤浩：Stasis张君维：zhangjunwei从7月9日报道说起~~~7/9：

信友队暑假集训第2次测试总结：本次比赛都出的以前做过的题，但本蒟蒻确只写了320（悲第一题：排行榜一道水题，秒A#include<bits/stdc++.h>usingnamespacestd;stringans[105],s[105],t[105];intvis[105];intmain(){intn;cin>>n;memset(vis,0,sizeofvis);

考虑矩形数量的规模大概是\(O(n^4)\)量级的，故很难通过枚举的方式直接做。弱化问题，如果只统计正着的矩形，个数是\(O(n^3)\)量级的。而斜着的矩形都是可以被一个恰当的正矩形包含的，此时两者对应顶点距离相同，存在性可以由顶点位置取与判断。即，我们可以将一个边长为\(x\)正矩形

注意到关键性质\(a_i\)是\(a_{i+1}\)的因数，故小决策在\(\frac{b_j}{a_j}\)更大时是严格优于大决策的，而\(a_j\)相同的决策之间显然只有\(b_j\)最大的有用，故最终至多只会保存\(O(\logm)\)个有决策。对于倍数增量的东西一定要敏感，多联系到量级上。然后考虑如何处理询

\(h\)的存在暗示我们从后到前增量来做。考虑建出失配树，则对于树上两点\(x,y\)，设\(a_x\)表示\(x\)到根的长度之和，则两者的绝对代价即为\(\max(a_x,a_y)-a_{lca}\)。显然可以把两部分拆开来做。每次插入节点，一定会把它作为原树的一个新叶子。对于\(\max(a_x,a_y)\)，其实就