题目链接:[Ynoi2011]初始化神仙trick+卡常题，前缀后缀和根本没听过。根号分治+分块。对于修改操作，发现是跳着修改，考虑根号分治。若\(x\ge\sqrt{n}\)，直接暴力更改，复杂度\(O(\sqrt{n})\)。反之，可以将序列抽象成一堆大小为\(x\)的段，如图，\(l,r\)是查询的区间。发现\(

题目描述给你一棵\(n\)个节点的树，每个节点有一种颜色，有\(m\)次查询操作。查询操作给定参数\(l\r\x\)，需输出：将树中编号在\([l,r]\)内的所有节点保留，\(x\)所在连通块中颜色种类数。每次查询操作独立。对于\(100\%\)的数据，所有出现过的数在\([1,10^5]\)之间，保证每

P5311Ynoi2011成都七中点分树好题，太妙了。思路看到树和连通块，考虑点分树。但是从这里发现原树和点分树的联系实在太小，貌似不可做。可以发现对于一个询问，一个点如果和\(x\)在一个连通块内，那么这个点到\(x\)的最大最小节点编号肯定都在\([l,r]\)这个范围内。可以证明，

洛谷传送门转化一下题意，变成求\(x\)在只经过编号\(\in[l,r]\)的点，能走到多少种颜色。考虑建出点分树。一个结论是原树上的一个连通块，一定存在一个点，使得它在点分树上的子树完全包含这个连通块的所有点。证明考虑点分治的过程，一个连通块如果没被其中一个点剖开就一定在同一

好题，牛牛的一个套路。先树剖一下，我们可以很简单的用树状数组维护每个点的真实值。对于每个点只维护所有轻儿子的信息，对于每次询问的时候暴力加入当前点，重儿子以及父亲的信息，查询第\(k\)大，再删除信息即可。考虑链修改的影响。因为只维护的是轻儿子的信息，那么只有链上的所有轻

我永远喜欢数据结构。题目传送门给出\(n\)个点的树，点有颜色\(a_i\)。有\(q\)次询问，每次询问给出\(l,r,x\)，求保留\([l,r]\)范围内的节点时，\(x\)所在联通块中有多少种本质不同的颜色。询问之间相互独立。不保留一个点的定义是，将这个点以及与其相邻的边全部删除。

题目传送门本来不想写这道\(shabi\)卡肠题的，但还是写了。分块+根号分治。考虑对\(x\)的大小分类讨论：若\(x>=\sqrt{n}\)，很明显最多只会加\(\sqrt{n}\)次，暴力加即可，用分块维护每个块内的\(sum\)，查询就直接散块加上整块即可。若\(x<\sqrt{n}\)，考虑累加\(x,y\)相同的

「Ynoi2011」成都七中题意：询问\(([l,r],x)\)，表示将树中编号在\([l,r]\)内的所有节点保留，求\(x\)所在连通块中颜色种类数可以转化为从\(x\)出发且只经过节点范围在\([l,r]\)的路径上的颜色种类数，是路径问题且多次询问，所以可以考虑点分树但是可以发现，一个节点的答案可

d1t1初始化题意一个长度为\(n\)的序列,\(q\)次操作。询问\([l,r]\)的区间和。将所有\(\bmodx=y\)的下标位置加\(z\)。\(n,q\leq2\times10^5\)。题解

P5309[Ynoi2011]初始化考虑暴力，模拟题意，时间复杂度竟是\(O(\frac{n^2}{x})\)，那么对于\(x\ge\sqrt{n}\)的修改就可以暴力了，这不是根号分治吗。再去考虑\(x<\sqrt{n}

一般情况下，程序运行消耗时间主要与时间复杂度有关，超时与否取决于算法是否正确。但对于某些题目，时间复杂度正确的程序也无法通过，这时我们就需要卡常数，即通过优化一些操作的

linkSolution不是分块的Ynoi。/jk我们注意到树上一个连通块一定存在一个节点使得连通块里面所有节点都在它子树内。点分树同理。那么对于一次查询\((l,r,x)\)，我们可以