题目链接：https://loj.ac/problems/search?keyword=joisc+2018。
「JOISC 2018 Day 1」道路建设
用$\rm LCT$维护颜色，显然每条实链里的颜色是一样的。
那个操作和$\rm access$也是一样的，所以可以在$\rm access$的时候把颜色段记录下来，然后用树状数组求偏序，顺便再$\rm splay$上打标记把这条链都染上给定的颜色。
代码还挺好写的，复杂度$O(n\log ^2 n)$。
code。
「JOISC 2018 Day 1」帐篷
普及组$\rm dp$题，$f_{i,j}$表示$i\times j$的矩形的答案，转移的时候考虑新增一列就行了。
code。
「JOISC 2018 Day 2」修行
好仙啊，研究了半天题解才搞明白。
首先可以把方案数转成概率，即恰好$k-1$个$a_i>a_{i+1}$的概率。
然后这个东西等价于$n$个$[0,1)$的随机变量，恰好$k-1$个$a_i>a_{i+1}$的概率。
考虑通过$a_i$构造一组$b_i\in [0,1)$，使得$b_i$的前缀和的小数部分等于$a_i$，那么显然每个$a_i>a_{i+1}$的位置$b_i$前缀和的整数部分都要加一。
显然$a_i,b_i$是一一对应的。
也就是说这个东西等价于现在有$n$个$[0,1)$的随机变量$b_i$满足$k-1\leqslant \sum b_i<k$的概率。
考虑这个东西怎么算，首先我们只需要求$<k$的概率，最后在减一下就好了。
考虑$n=3$的情况，实际上这个概率就等于一个$1\times 1\times 1$的立方体被一个斜着的面切掉一部分之后剩下的体积，这个斜着的面满足解析式$x+y+z=k$。
那么高维情况是一样的，也是算一个体积。
考虑利用容斥去掉$[0,1)$的限制，枚举至少$x$个$b_i\geqslant 1$，那么限制就变成了$\sum b_i<k-x$，其中$b_i\in [0,+\infty)$。
这样就很好算了，这就相当于坐标系的一个象限被截出来的体积，三维情况体积就是$(k-x)^3/6$。
注意到每增加一位相当于多了一重积分，所以$n$维的体积就是$(k-x)^n/n!$。
复杂度$O(n\log n)$。我是不是想太复杂了啊，后面这部分是我自己yy的。。不知道准不准确
code。
「JOISC 2018 Day 2」最差记者 3
注意到每个人的行动都是形如：先停$x$步之后，马上瞬移到$x$步之后，也就是前面那个人之后。
设$f_i$表示第$i$个人的循环节长度，那么：
- 如果$d_i\leqslant f_{i-1}$，那么$f_i=f_{i-1}$。
- 否则$f_i=\lceil d_i/f_{i-1}\rceil *f_{i-1}$。
注意到$f_i$要么不变要么至少翻倍，所以如果我们把$f_i$相等的缩起来，一共就只有$O(\log n)$段，那么直接暴力就好了。
code。
「JOISC 2018 Day 3」比太郎的聚会
注意到$\sum y_i\leqslant 10^5$，那么我们可以对$y_i$的大小分块讨论。
如果当前$y_i>\sqrt {n}$那么直接暴力$\rm dp$一遍，一共$O(n\sqrt n)$。
否则我们预处理出每个点最远的$\sqrt n$个点是哪些，然后每次查询就好了。
总复杂度$O(n\sqrt n)$。预处理还是挺巧妙的，我之前写的带$\log$的就$\rm TLE$了。
code。