眨眼间就Day4了。很快就可以回去了~

---------------------------------------------------------------------------

还是吃不惯辣。可是居然还没上火。

--------------------------------------------------------------------------

今天考得不错到了rank5。

-------------------------------------------------------------------------

第一题：

给出一棵树，每个节点有权值，有若干个查询，每次查询要求输出树上从u到v的路径上如果把权值a看成权值b那么有几种不同的权值出现。(n<=50000,m<=100000,1<=权值<=n，有20%的数据n<=100,40%的数据是一条链。)

【这一看就是COT2的加强版。没做过cot2只知道cot2很神。想了想应该是莫队算法的树上版，但是没写过。于是对小数据暴力，对链的数据用树状数组和函数式线段树做到了离线O(mlogm+nlogn)。或者就是像标程那样去把树转成DFS序列然后用莫队算法。

讲一下在链上的O(mlogm+nlogn)的离线算法。先假设不存在那个奇怪的（将某一权值看成另一权值）。把所有询问都读入存起来，然后根据右端点排序。对于每一个元素Ai，设pre=最大的j使得Aj=Ai。那么这个数能够对左端点在[pre+1,i]范围内的查询贡献1个不同的权值。所以就用一个树状数组维护一下前缀和就好了。然后再把那个奇怪的限制加进来。这个限制只能够在（查询区间中权值a和权值b都出现了）的时候影响答案，并且会让答案-1.那么还剩下一个问题，即给出一个区间[l,r]，判断某一个权值有没有出现于其中。那么建一棵函数式线段树就能在O(logn)解决一次查询。所以总复杂度就是O(nlogn+mlogm)】

第二题：

- -尼玛题面太复杂了而且太难。这种奇怪的自动机模型- -。自己去看评测包吧。

第三题：

定义一个数优美：这个数的各个数位可以被分成两组，使得这两组之和相等。求区间[l,r]中有多少个数优美。(l,r<=10^9)

【- -这种题出得好失败简直为打表而生。可惜当时不敢打10000个数的表不然就AC了- -。正解是这样的：因为一个数优美与否只与组成它的各位数有关，所以这个数将其重排列之后是否优美与原数相同。于是就可以生成所有各位数递增的优美数，发现在10^9范围内只有1W个左右，那么对于每一个数枚举其排列看看有多少在查询范围内即可。】

--------------------------------------------------------------------------------

今天又是我发cena包。好高兴。没有在昨天发了cena包之后遭到悲惨下场。