I love tree题意：给一棵树，每次操作选择一条链，从起点到终点点权依次增加$1^2,2^2,…n^2$，单点询问当前点权​ 容易想到树剖，然后考虑在线段树上维护这个问题 发现可以转化成选择一段区间$[l,r]$，对于每个点$x$，该位置增加的值为$(x-h)^2$​​，把平方项展开后得到$x^2+h^2-2xh$​，对这三项分别线段树维护即可（分别维护$x^2,-2x$​出现的次数和$h^2$的和） 有时候dfs序和修改顺序是反的，就是对于区间$[l,r]$​，每个点增加量分别是$n^2,(n-1)^2,…,1^2$​，实际上就是每个位置增加量变为$(h-x)^2$​​，h为r+1，而显然$(x-h)^2=(h-x)^2$​，因此这种情况下线段树不需要进行任何修改，只要调整传入的h参数即可 树剖时还需要稍微注意的是，这里对链的修改存在先后顺序，常规的树剖对于两个端点x,y是一起往上跳的，那么这里只在x往上跳时修改，y往上跳时先用vector记录哪些点需要修改，等x修改完再去修改y     阅读全文

06. Xor sum07. Pass!09. KD-Graph10. zoto题意：给出一个序列，离线查询m个区间$[l_i,r_i]$中，在数值区间$[d_i,u_i]$中有多少个不同的数，n=1e5 首先考虑在数值区间上维护问题，也就是维护一个支持单点修改和区间查询的数据结构，很容易想到用线段树之类的方法实现$O(\log n)$的修改和查询 离线查询若干个区间，可以再想到莫队算法，每次修改复杂度$O(\sqrt n)$​，查询$O(1)$​，将上述两种结构合并后发现，修改复杂度达到了$O(\sqrt n\log n)$​，显然超时 于是为了使总复杂度限制在$O(n\sqrt n)$​，需要在数值区间上维护一个$O(1)$​修改，$O(\sqrt n)$​查询的做法，这个方法就是分块，维护$num[i]$记录数i出现的次数，$sum[i]$​记录第i个块中不同数的个数，两者合并起来刚好是$O(n\sqrt n)$     阅读全文

B. CannonG. League of Legends题意：给定n个区间，要求将它们分成k组，每组之间有交，最大化每组交长度之和 简化问题，对于如果一个大区间能够完整包含某个小区间，则该大区间只有两种最优决策： 单独归为一组，贡献r-l 与任意一个其包含的小区间归为一组，不对结果产生影响 可以用反证法证明结论，假如大区间和其他区间归为一组，那么将该大区间移出该组，该组的交一定不下降，再放入其包含的小区间组中，小区间所在的组的交也不下降，即大小区间在同一组的决策一定最优 于是可以把所有大区间取出来，单独讨论所有小区间，可以发现，若将剩下的区间按照左端点从小到大排序，其右端点也一定是有序的，接着考虑dp，$f[i][j]$​表示考虑前i个区间，分成j组的最优答案，而一组的贡献只与最左和最右两个区间相关，显然有转移$f[k][j+1]=\max\limits_{r[i+1]-l[k]>0} \{f[i][j]+r[i+1]-l[k]\}$     阅读全文

    阅读全文