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)$     阅读全文