原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ7.html这题是Unknown的弱化版。如果这个问题出在序列上，那么显然可以CDQ分治+斜率优化+凸包上二分来做。那么它出在树上？点分治。写挂了好多地方调了好久，自闭了。#pragmaGCCoptimize("Ofast","...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ394.html首先我们发现一个数不能既被往左换又被往右换。也就是说不能有任何一个数左边有比他大的，又被有比他小的。也就是最长下降子序列长度不超过2。所以我们一定可以找到2个上升序列包含所有的数。于是容易想到$O(n^2)$的d...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ290.html真是一道好题！首先，如果不是仙人掌直接输出0。否则，显然先把环上的边删光。问题转化成多个树求解，把答案乘起来即可。现在我们考虑如何求一个树的答案。再转化一下题意可以变成选出若干条长度至少为2的路径使得它们两两没有...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ291.html结论：这个写错的树状数组支持的是后缀加和后缀求和。这里的后缀求和在x=0的时候比较特殊，返回0。于是我们需要查询v[L-1]和v[R]相同的概率是多少。我们可以用树套树维护一下左端点在一个区间内，右端点在另一个区...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ375.html首先，我们可以建出一个k个点的自动机，第i个点表示当前数对k取模为i-1。显然每一个点有m-1条出边。然后，稍加观察，我们就可以发现，如果一些节点的出边集合是相同的，我们就可以将他们合并。具体是怎样的节点呢？对于...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ374.html想出正解有点小激动。不过因为傻逼错误调到自闭。不如贺题首先我们考虑如何$O(n)$求一个答案。首先，计算两条路径的贡献时，由于两国连续交战数次只算一次，所以我们可以只看这两条路径的交的最深点。也就是说，我们可以对...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ395.html记得同步赛的时候这题我爆0了，最暴力的暴力都没调出来。首先我们看看68分怎么做——求两个串的本质不同的公共子串个数。　　它是一个模板题，然而我当时并不会，甚至连SAM都忘了怎么写QAQ。&...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ407.html套路啊。先按照两个节点顺序各搞一个kruskal重构树，然后问题转化成两棵kruskal重构树，不断询问，每次询问让你判断是否有点同时存在于第一棵树的一个子树和第二棵树的一个子树中。这个东西就转成dfs序之后主席...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ185.html首先暴力DP是$O(3^nn^3)$的，大家都会。我们换个方向考虑。假设我们求的是树上每一个节点到图上的节点的映射，而且图上的一个点可以被树上多个点映射到，那么就是求图上所有点都被映射到至少一次的方案数。我们发现...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ314.html　　如果只加不减，那么瞎势能分析一波可以知道暴力模拟的复杂度是对的。　　但是有减法怎么办？？？　　再搞一个类似的，维护减了多少。　　那么，询问一个数位的值的时候，我们只需要得到两部分值中这一位的值是多少，以及是否...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ195.html　　首先询问都可以放到最后处理。　　对于操作，我们把它差分一下离线下来。　　现在的问题就是从第一棵树到第n棵树扫一遍，并不断维护树的形态。　　容易感受到这棵树会有删节点之类的操作，所以自然想到LCT。　　但是要涉...

原文链接https://www.cnblogs.com/zhouzhendong/p/IOI2018Day1T1.html　　首先二分一下，花费2次操作求出第一位的字符。　　假设第一个字符是Y，答案字符串的长度为i-1的前缀是S，我们考虑如何只花费1次询问得到下一个字符。　　press(SAA,SAB,SAX,SB)-...

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ1058.html　　考虑用两个multiset分别维护两个答案。　　一个直接按照权值维护，另一个维护一下相邻位置的差。　　比较容易想到如何维护的吧，不多讲，看代码吧。#include<bits/stdc++.h>...

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ1095.html　　有N个点，每一个点是黑色或者白色，一开始所有点的颜色都是黑色。有M次操作，每次操作有两种类型：1.修改一个点的颜色；2.查询树上所有黑色点对之间的距离最大值。　　$Nleq100000,mleq50000...

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ4566.html　　给定两个字符串$s1$和$s2$，问有多少$a,b,c,d$满足$s1[acdotsb]=s2[ccdotsd]$。　　$|s1|,|s2|leq200000$　　建个广义SAM，然后统计一下。　　模板题...