比赛链接：http://jzoj.net/senior/#contest/home/2833
Seq
题面
考场
题目变简单了。这道题一个递推式很显然地看出可以做矩乘。那考虑怎么构造矩阵。
因为他都是前面式子相乘得到的下一项，而递推式里的常数 $b_i$ 又在指数上，可以想到两个等底数的式子相乘就等于他们的指数相加。那么只需要在指数上做矩乘维护一个递推后的指数和就好了。
这么构造矩阵的话，转移矩阵会很好看：
$\begin{bmatrix}
0 &1 & 0 & …&0 & 0\\
0 & 0 & 1 & …&0 & 0\\
&&&…\\
0 & 0 & 0 & …& 1& 0\\
0 & 0 & 0 & …&0&1\\
b_k&b_{k-1}&b_{k-2}&…&b_2&b_1\\
\end{bmatrix}$
构造起来也很简单。然后普通矩乘就好。
注意这里跑起来会有点慢，经过反复卡常 $+O3$ 之后本地仍然 $1.6s+.$ 开网之后在 $customtest$ 测了一下发现开 $O3 ~400ms+$，不开 $2000ms+…$ 然后交了 $O3.$ 拍了很久没错就觉得应该是满分了。
出分：$100pt.$
$code:$ https://paste.ubuntu.com/p/87Rk2K453B/
Dream
题面
考场
挺喜欢题面的。然后发现好像可以直接贪心。因为一个 $t$ 只能对应一个 $[l,~r]$，所以我们可以类似选区间的策略按左端点排序然后尽量选右端点靠左的区间和 $t$ 配对，这样区间更靠右的就有可能和后面的点配对从而有更优的答案。
具体实现起来就把区间按左端点排序，从小到大考虑 $t$ ，每一次首先把所有左端点小于 $t$ 的区间假如考虑中，因为后面的 $t$ 不减而我们要找最小的右端点，所以我们只需要用一个小根堆存这些区间的右端点，在找区间的时候如果堆顶比 $t$ 还要小，就直接弹出，因为它不能和 $t$ 配对就更不可能和 $t$ 后面的数配对。然后如果能配上一个就计入答案并弹出堆顶。（因为有可能一个满足的区间都没有，就是堆为空）
代码也很简单了。
出分：$100pt.$ //其实当时没想要拿满，但好像也举不出反例就交了。
$code:$ https://paste.ubuntu.com/p/n2XGdh5xkT/
tree
题面
考场
先暴力吧，就是暴力两个点然后暴力中间的点走过了一个点对没有。
然后觉得这个枚举另一个点的过程好像可以在搜出去的过程中解决，但是没往下想。//这个是可以的。
然后开始看特殊数据。
一条链还只有一对点的话，直接左边右边讨论。
菊花图的一对点的话，也可以直接讨论，这个讨论了我很一会。
然后由于第一题卡常卡了很久，谁知道它臭氧优化那么快。。 没时间了。
出分：$20pt.$ //可能讨论挂了吧。毕竟没有造数据看。
正解
？？矩形面积并？？神奇。。
还是先从序列上下手的，把问题转化成求不合法的对数，这样原来的答案就是总对数减。
求不合法的对数的话，就是所有包括这两个点 $[l_i, r_i]$ 的一个区间，这样就是要区间的左端点 $\leq l_i$，右端点 $\geq r_i$。这个东西的解集可以看成一个二维的东西，具体而言就是一个矩形，因为它就是所有满足 $x \in [1,l_i],y\in [r_i,n]$ 的点对。这个就是一个矩形了。然后对每一个求一个并就是求矩形面积并了。
这是序列上的，那树上怎么办呢？那我们就在 $dfs$ 序上面考虑就好了。考虑点对 $(x,~y)$就有两种情况：
1. $(x,y)$ 不是相互的祖先，那么一对答案 $(u,v)$ 要满足 $u$ 在 $x$ 的子树里面，$v$ 在 $y$ 的子树里面，那么在一个 $dfs$ 序上就可以直接转化成两段区间。
2. $(x, y)$ 有祖先后代关系，不妨设 $x$ 是 $y$ 的祖先，那么一对答案 $(u,v)$ 要满足 $u$ 在 $y$ 的子树里面，$v$ 在整棵树除了 $y$ 所在的 $x$ 的子树里面。这个就是整个区间减一个区间，拆成两个区间即可。
然后就是矩形面积并了。
那它怎么写呢？？？
既然这个已经咕了很久，今天又是七夕，那就来写一下他吧。这个还是单独放在另一个博客里吧：矩形面积并
然后和普通的矩形面积并不同，它的坐标是比较小的，所以不需要离散化，除此之外，因为一对点就算是算面积也只能被算一次，所以要严格保证所有表示矩形区间的横坐标小于纵坐标，大于就换一下，以为换一下不影响计数。而且因为边界都要算上，所以再加矩形的时候吧终边（上边）纵坐标 $+1$ 之后再加，保证上面那条线被算到了。
最后用 $\frac{n\times (n-1)}{2} - cnt$ 就可以得到答案了。
$code:$ https://paste.ubuntu.com/p/BDvhkHGKDy/