Uoj#435. 【集训队作业2018】Simple Tree

发表于 分类于 ， ， 阅读次数：

题意：给出一棵 个点的有根树，点有点权，支持下列操作：

  • 将 到 的路径上的点点权加上 (其中 )

  • 询问在 到 的路径上有多少个点点权

  • 询问在 的子树里的点有多少个点点权

强制在线，，时限 。

首先树剖，转化成序列问题：

  • 将 加上 (其中 )

  • 询问

考虑分块，整块维护有序序列（将相同数缩合起来），加减时移动指针，散块暴力重构。

查询时散块暴力，整块直接读取答案。

设块大小为 。

考虑树链剖分拆路径形成的 个区间，由于不相交，整块 个，散块 个。

重构时可以归并，复杂度 ，移动指针的复杂度均摊后和重构复杂度相同。

总复杂度为 ，取 可得复杂度为 。

然而我的分块水平不够，上面那个做法实在有点难写……

考虑 或者 的数，可以视作不会被 的修改所影响。

那么我们只需要考虑 以内的数。

每个块开一个桶，维护后缀和，这样修改就十分简便了。

但是，受到空间复杂度的限制，块大小不能开太小。