我感觉我信概药丸了（为啥非要作死写奇怪的东西呢）

T1：JabberWocky

Idea：lxl Solution：lxl Std：lxl Data：lxl&zcy

https://www.luogu.org/problemnew/show/P4118

https://www.lydsy.com/JudgeOnline/problem.php?id=5394

首先要会拓展欧拉定理（我一个出数据结构的怎么就开始数论了呢）

$a^x\;mod\; p\;=\;a^{x\;mod\;Φ(p)+(x>Φ(p)?Φ(p):0)}\;mod\;p$

然后可以发现对一个数取欧拉函数，log次就会变成1（这个性质烂大街了吧），然后任何数mod 1都是0就可以停下来了（不要停下来啊）

然后直接这样写会发现WA了（这种东西肯定会有一堆细节啦）

以下这段抄自zcy的题解：

首先我们发现后面的phi[p]这一项是可能不会加的。这个怎么办呢？

首先可以按照相逢是问候那题的套路返回判断是否取模，以此作为是否加上这一项的依据。

当然这么做需要讨论的东西会有点多，挺麻烦的。

后来就想到了也写在讲评里的办法，就是因为这个不断地幂次增长速度极快，很少几项就能够增长到远大于模数的地步。

那就先暴力的处理前面几项，然后再正常做，这样就减少了讨论次数。

但是这么搞还会存在一个问题，就是如果前几个常数次暴力处理的全是1，增长就是假的。

不过考虑到有1的话后面的全都被变成了1，所以完全没有必要担心这个，找到1就从1开始做好了。

然后还会存在一个问题，就是如果得到的是0次方，$x^0 = 1$

这个虽然数据不会存在这个问题，但是取模后会出现。

这个地方稍微注意一下就好了。

然后应该就没有什么坑了。

时间复杂度应该是 $O( mlognlog^*v )$

空间复杂度 $O( n + m )$

对这题的评价：3/11

T2：Which Dreamed It

Idea：lxl Solution：lxl Std：lxl Data：lxl

https://www.luogu.org/problemnew/show/P4692

https://www.lydsy.com/JudgeOnline/problem.php?id=5395

思路非常简单，就每个颜色在每一段开一个set，然后每次修改的时候计算一下贡献就可以了

有一些细节需要注意

时间复杂度 $O( ( n + m )logn )$ , 空间复杂度 $O( n + m )$

对这题的评价：3/11

T3：JabberWockyII

Idea：ccz Solution：ccz Std：ccz Data：ccz

https://www.luogu.org/problemnew/show/P4693

https://www.lydsy.com/JudgeOnline/problem.php?id=5396

这是一道简单模拟题。

可以将有根有序树动态地剖分为一些水平路径和竖直路径，满足性质：

1.竖直路径表示一个点序列，每个点是上一个点的孩子；

2.水平路径表示一个点序列，这些点的父亲相同，每个点是上一个点右边的第一个点；

3.树上每个点在且只在一条路径中出现；

4.对每个点，它的孩子可以被表示成0到2条水平路径，除了至多一个点在某条竖直路径上。

不难实现两个操作：

水平访问：给定一个点w，保证w有至少一个孩子，将w的孩子表示为一条水平路径；

竖直访问：给定一个点w，将w在树上到根的路径变为一条两端为w和根的竖直路径。

接下来不难进行每个操作：

A和B是把一条路径从水平变为竖直或从竖直变为水平，可以打标记实现，注意维护4条性质

C为换根，竖直访问然后打上翻转等标记，需要注意对孩子顺序的规定

D和E只需进行水平/竖直访问然后进行普通的区间修改查询

F为初始化，略

可以发现竖直路径的变化和lct很接近，因此复杂度分析可以参考lct的一些结论。

时间复杂度 $O( mlog^2n )$ , 空间复杂度 $O( n + m )$

据@negiizhao 说可以做到 $O( mlogn )$？

对这题的评价：10/11

这套题就T3比较毒瘤，其他都很简单吧

按照惯例放上可爱的妹子的图：