云做题= =

BZOJ 3626 [LNOI2014]LCA

看到这个题首先没啥思路……看到$l \le i \le r$第一个想到的是主席树Orz

对于$l \le i \le r$考虑将其分成前缀和相减的形式。之后问题就变成了多次询问对于编号为$1 \to i$的点到$z$的LCA的深度和。

此时还是没什么思路……?没有强制在线,所以考虑一下离线。考虑维护一个集合,每次插入一个点,查询一个点对于集合里点的答案。(之后还是没想到Orz)因为深度等于根节点到它有多少点,所以直接链覆盖链查询就……行了……

BZOJ 3922 Karin的弹幕

这道题一看等差数列!%来%去!一看就是根号分治!还想对了QwQ

询问大于根号的暴力就好了,小于的就不会了……具体应该是建立线段树$rt[i][j]$表示$\mod i=j$的线段树。这样的线段树一共有$\sqrt{n} * \sqrt{n} = n$棵。每次修改一个数的时候在对应的线段树上修改就好了,时间复杂度为$n \sqrt{n} \log{n}$

BZOJ 4152 [AMPPZ2014]The Captain

这道题看到了min()之后就傻了……不满足传递性= =

想到了类似DP的转移……实际上就是最短路。但是边数太多了,啥也没有不能传递……

事实上将所有点按两维各排一次序,依次连边就是对的,在这两维下都有传递性,所以得证。

BZOJ 4514 [Sdoi2016]数字配对

这题一看数据范围就是网络流= =

暴力建图,之后二分配对次数求最大费用最大流就OK了。

(不是不详细写是这题真的不难= =

BZOJ 5020 [THUWC 2017]在美妙的数学王国中畅游

首先这题一定是LCT维护动态树上的链信息。三种函数可以开三棵LCT......但是同一函数咋合并呢?

并不能合并Orz通过泰勒展开+维护0~15阶导即可。没看懂一会再详细理解Orz