序列上过于水的问题就放到树上
二分+哈希完美解决
我们需要求一个点的(k)级祖先，可以用长链剖分，维护一个点到根的正反哈希，判断(lca)的方位
求(lca)请用欧拉序，本题卡常
最大值最小问题，考虑二分
正序需要考虑减少到(0)的问题，我们考虑倒序处理
假设所有数初始为(mid)，每天晚上会减少(a[i])，但是每天可以选择(k)个增加(p)，问最后是否所有数字都大于(h[i])，且中途不能小于(0)
我们开一个堆记录每个数字第一次高度小于(0)的天数，然后模拟(m)天的过程，如果当前堆顶的天数小于当前枚举天数则无法实现
好鸡儿神仙一道题
根据我根本没有见过的套路，我们可以设计如下(dp)状态保证不重不漏的计数：
(f[i][j][k])表示在(S)中从前往后匹配到了第(i)个，从后往前匹配到了第(j)个，回文串前后各匹配了(k)位
(g[k])表示包含了整个(S),且前(k)位和后(k)位已经确定的方案数
我们定义匹配上一个字符串的位置，指这个字符串在新串中最外侧出现的位置
为什么方便讨论，我们先说(|S|+m)为偶数的情况
那么我们可以开始讨论转移状态
(1.s[i]==s[j]) && (i-j<=1)
那么有一种情况会让整个字符串都匹配上，其他(25)种情况都只会让(k+1)
(f[i][j][k+1]+=f[i][j][k]*25)
(g[k+1]+=f[i][j][k])
(2.s[i]==s[j]) && (i+1<j)
和上面一种情况类似
(f[i][j][k+1]+=f[i][j][k]*25)
(f[i+1][j-1][k+1]+=f[i][j][k])
(3.s[i]≠s[j])
这样有24种情况会让匹配不变
(f[i][j][k+1]+=f[i][j][k]*24)
(f[i+1][j][k+1]+=f[i][j][k])
(f[i][j-1][k]+=f[i][j][k])
最后对于(g)，既然已经匹配完成，那么(26)种字符都可以转移
(g[k+1]=g[k]*26)
显然这个(k)可以矩阵快速幂，复杂度降低到(|S|^6log(|S|+m))
好像根本过不去
考虑压缩状态：我们发现一个点从((0,n-1))走到整个序列都匹配上的状态，只会经过两种点
一种是有两条出边和(24)个自环的点，我们称之为红点，另一种是有一条出边和(25)个自环的点，我们称之为绿点
终点会有(26)个自环，但是所有路径都要经过终点，所以不在考虑范围
可以发现，如果一条路径上有(i)个红点，那么只会有(frac{|S|-i+1}{2})个绿点
我们把经过红点和绿点个数相同的路径称为同一类路径
观察发现，同一类路径中，方案数不同当且仅当走过的路径不同
这样一道路径计数问题上我们发现红点和绿点出现的顺序对答案没有影响，我们可以认为所有红点在起点侧，绿点在终点侧
那么我们需要稍微改变一下(g)的定义，定义(g[k])为经过了(k)个红点的方案数
我们在矩阵内，对第(i)个红点到第(i+1)个红点连(1)边，对相应的绿点连(g[i])边，对自己连(24)
第(i)个绿点对第(i+1)个绿点连(1)，对自己连(25)，终点对自己连(26)
点数为(frac{3}{2}|S|),可以大力矩阵乘法了
然后再考虑一下(|S|+m)为奇数的情况：
在最后一步时，包含两个字符的绿点没办法直接转移到终点了，所以我们考虑把这个方案数去掉
我们先跑一下(frac{n+m+1}{2})次的矩乘，算出答案
然后把(g[k])变成(f[i][i+1][k])，去掉终点的自环，因为只有最后一步有限制
再跑一下(frac{n+m+1}{2})次的矩乘，用原来的答案减去
考虑卡常，我们发现只会从编号较小的点向编号较大的点转移，所以我们矩阵乘法部分可以加一个(frac{1}{6})的常数
分析一波，发现环上的点都不能选
再分析一下，发现两个环之间的路径也不能选
再看看题解分析分析，发现我们只要拓扑排序就可以把可选集合找到
我们发现可选的点分为两类
一类是有根树，这种是一个连通块中的某个点和环上点相连，那么这个点必须在当前连通块内其他点都选完之后再选
一类是无根树，不存在点和环相连，所有点都可以作为最后一个选的点
对于有根树，直接树上背包
(f[i][j])表示(i)子树中选了(j)个方案数
注意这个是有顺序区别的，转移的时候乘上一个组合数
对于无根树，我们可以枚举哪个点是最后一个被选的点，即枚举哪个点作为根，(dp)值对应位相加
对于(n)个点遍历了(i)个点的情况，其他(n-i)个点作为根的时候都统计到了，所以除以(n-i)
特殊的，遍历了(n)个点的情况不用除
合并的时候卷积一下就可以了，数据范围很小可以暴力卷
直接预处理出每个点树上最远的距离(d[i])
然后考虑对于每个(lim)，直接用双指针法枚举，用并查集维护连通性
注意我们要按(d)从小到大枚举，这样可以保证删除掉的点不会影响后面的连通性
把题解里我看不懂的部分都删掉也能过
不失一般性地考虑(n>m)的情况
显而易见的结论：(mod gcd(n,m))相同的数字才会轮换到一起，每个组只要有一个人初始快乐最后都会快乐
我们令(d=gcd(n,m))，可以发现分在一组的情况当且仅当两个数字对(d)取余相同
我们发现如果(d)大于初始快乐人数，那么一定无法令所有人快乐，这样我们可以把组数降低到(10^5)级别
我们让(n,m)都除以(d)，此时(n,m)互质，注意如果一开始所有人都快乐返回(-1)，这里需要特判
然后我们考虑同余类最短路，其实就是把余数相同的节点放在一起跑最短路
考虑一个初始快乐的女生，假设他的编号是(j)，那么它在第(j)天令编号为(j)的男生变快乐
那么在(j+m)天，这个女生会令((j+m)\%n)号男生快乐
但是我们发现如果这样连边点的数量是(10^9)级别的
考虑题目性质，如果一个男生((j+m)\%n)一开始不是快乐的，那么它显然比(j)号男生更晚变快乐，那么(j)号男生就没有用了，不需要加入最短路
我们发现其实只有初始快乐的那几个人需要作为节点跑最短路，我们只要考虑一下节点之间的边权
用(exgcd)计算，设(i+x*mequiv j(mod n))
注意此时(n,m)互质，我们只需要求一个(x)出来，然后根据(j-i)不同去乘不同的数
总结一下：设置一个超级源点(S),(A_i)是女生初始快乐节点，(B_i)是对应男生节点
(S->B_i) 边权为(i)
(B_i->A_j) 边权为(x*m) 这个边本来含义是女生经过数轮后感染其他女生但是由于需要加上一个第一轮的(i)，就可以直接用(B_i)代替
跑最短路，求其中最长的一条返回
CF熟悉的结论题
先考虑乘法，这些乘法啥时候乘对于最后的结果来说没有区别，对于所有的乘法操作我们可以考虑放到最后进行排序，选择最大的几个
然后考虑加法操作，我们发现加法其实是可以转化为乘法的，但是转化的过程中顺序对于转化结果有影响
贪心地考虑，一定是最大的数字先被加，所以对于每个位置来说，每个加法操作前和操作后的数字都是一定的，那么就很容易转化为乘法
考虑赋值操作，肯定一个位置只会赋一个值，那么我们每个位置只保留一个最大的值
然后会发现，赋值操作和加法操作基本没有区别，完全可以变作加法加入操作(2)
至此我们把三个操作都变成了乘法，贪心地选就可以了
有三条路径不想交当且仅当一颗生成树被两条非树枝边覆盖
暴力覆盖，有一条边被两条非树枝边覆盖就可以结束了
偷(Kewth)聚聚的图：
考虑路径情况只可能是(d->lca),(d->b->a->lca),(d->c->lca)
路径暴力找就可以了
神仙转化题
如果存在点((x,y))，那么令(a[x]=y)，然后我们求(max-min==r-l)的区间数量
考虑求一个(max-min+l)的值，我们发现这个值大于等于(r)
所以我们只要求区间最小值的数量
用线段树和单调栈维护可以(O(nlogn))
考虑下最优选择方案显然是每条路径都选两个叶子节点，且这样选一定是联通的
考虑无论怎么选，直径的某个端点必然在方案中，所以我们以直径的两个端点为根建两颗树，然后在每棵树中选(2*y-1)个叶子节点，把节点到根的权值全部加上
如果全部叶子节点都可以被选到，那么权值就是所有边之和
把所有叶子节点按贡献排序，注意有些地方会重复应该删去
如果(x)节点在排名前(2*y-1)个叶子节点的路径上，那么答案就是前(2*y-1)个叶子节点的贡献和
否则我们可能会出现两类情况：
(1.)去掉贡献最少的链，加上一条包含(x)的最长链
(2.)把离(x)最近的某条链下半部分换成(x)所在最长链
对于这种情况，我们需要从(x)向上找第一个所在链排名在前(2*y-1)内的点
如果边权都为(1)，根据长链剖分复杂度分析，暴力跳复杂度应该为(O(sqrt{n}))
但是边权不为(1)，那么我们考虑用倍增
有一种模拟的味道？
考虑一下，每个点出度入度都是偶数，每个点的总度数是偶数，那么这张图是一张欧拉回路
将度数为奇数的点两两连边，如果总边数不是偶数，那么随便找个点加个自环
跑个欧拉回路，然后隔一条边换一个方向
先跑两个(dij)求出每个点到(s,t)的最短距离，然后离散化让值域降低到(n)级别
考虑我们不知道终止状态，所以(dp)倒推到起始状态
设(dp[0/1][x][y])表示先手为(a、b)，剩下((x,y))以及右下角时先手的最大得分
设(ns[i][j])是下边第一个有数字的位置，(nt[i][j])是右边第一个有数字的位置,(s[i][k])是矩阵后缀和
(f[0][i][j]=s[i][j]-f[1][ns[i][j]+1][j])
(f[1][i][j]=s[i][j]-f[0][i][nt[i][j]+1])
(f)数组的值直接设为后缀最小值
判断的时候让(ret=s[1][1]-2*f[0][1][1])，判断(ret)的正负
原来的四种操作：((0,1),(0,-1),(1,0),(-1,0))对于每一维度有三种操作(1,-1,0)，且一维为(1,-1)，另一种只能为(0)
一个经典(trick)：考虑旋转坐标系，一个点坐标变为((x+y,y-x))
那么四种操作变为((1,1),(-1,-1),(-1,1),(1,-1))，每一维的操作可以分开考虑
用奇偶性判断有没有解，如果同一轮中两个点之间距离与时间奇偶不同无解
相邻两轮之间奇偶必须相同
设(S_l)为一个循环内加了多少个(1)，(S_{i})表示(i)时刻加了多少个(1)
有等式(S_{t\%l}=x_i-S_l*(t/l))
按照(t\%l)排序可以列出一系列不等式(0<=S_b-S_a<=b-a)可以化为(0<=p*S_l+q<=d)来解出可行的(S_l)的范围
注意(S_l)在范围内应该取与上面求出奇偶性相同的值
那么可以把每个点的坐标都加上(S_l*(t/l))
考虑没有人数限制，那么(n_1=min{r_i},n_2=max{l_i})时最优
同时(n_1)只能增大,(n_2)只能缩小
再根据限制调整(n_1,n_2)大小，用二分图染色将老师分组
官方版本：每个点横纵坐标之间连一条边
题意变成对每条边定向，使得每个点入度和出度最多相差(1)
然后跑一遍欧拉回路
(shadowice1984)神仙题解：
(x)坐标相同的点两两配对，(y)坐标相同的点两两配对，二分图染色
智商不够，数据结构来凑
(solution1：)
广义(SAM)上线段树合并维护([l,r])串内的(endpos)集合大小
(solution2:)
(AC)自动机(fail)树上(dfs)序建可持久化线段树（蜜汁熟悉感）
建出(AC)自动机后，每个串跑一遍
对于每个前缀，会被包含它的前缀贡献一个权值
那么我们求的就是(fail)树上某个子树内编号在([l,r])内的权值
我们以(dfs序)建主席树，求([l,r])范围内的值
假设(A)集合在圆内，值域为(E),点数为(n)
朴素算法：
枚举(A)集合中的两个点，令圆过这两个点，那么圆心必定在这两个点的中垂线上，用其他的点确定圆心可取的范围判断能否成立
复杂度(O(n^3))
优化：
假设原平面是(xOy)
根据我也不知道哪想到的结论，我们把原本二维平面中的点全部映射到曲面(z=x^2+y^2)上，得到点集(A^{'},B^{'})
考虑一个任意与原平面不垂直的平面(ax+by+z=c)，与曲面的解析式联立可以得到(x^2+ax+y^2+by=c)，惊喜的发现这是一个圆的方程
那么我们的问题变为，能否找到一个与原平面不垂直的平面使得(A^{'})都在平面下方，(B^{'})都在平面上方
据说(z=x^2+y^2)是一个下凸的平面，所以(A)的上凸壳就是(A^{'})的上凸包端点
有结论是凸包集合大小是(n^{frac{2}{3}})，咱也不会证
为了找到一个合法划分平面，我们让平面强行和(A)上凸壳的棱相切即可
但是三维的话又不太好实现，我们还是考虑二维平面
枚举每一条棱对应的点对，然后用朴素算法实现判断
据说可以分治求三角剖分。。。给定一个凸包，任选一条边((a,b))，在凸包上找到一个点(c),使得((a,b,c))构成的三角形外接圆包含整个凸包
分治((a,c),(c,b))
这图不是(DAG),草
设(f[now][j])表示现在在(now)点，已经花了(j)个时间
枚举后继节点得到方程(f[now][j]=min{val_{(now,t)}+sumlimits_{k=1}^{t}p_{(now,t),j+k}*f[t][j+k]})
当(j+k>t)时，代价是(dis[t][n]+x)
暴力(dp)是(O(mt^2))
设(g_{(u,v),t}=sumlimits_{k=1}^{T}p_{(u,v),k}*f[v][t+k])
(f[u][t]=min{g[_{(u,v),t}})
我们将(p)数组翻转得到
(g_{(u,v),t}=sumlimits_{k=1}^{t}p_{(u,v),T-k}*f[v][t+k])
这个挪挪下标大概能分治(FFT)吧，，，有点懵，回头再填坑
考虑如果某些询问在一个环上，那么肯定能安排上
我们先把缩点，建出森林
然后树上差分打上方向标记
由于有样例二那种一个往左一个往右的毒瘤情况，我们需要大力(dp)
将线段按端点排序
设(f[i][j])表示到第(i)条线段，右边界为(j)的前缀最大值
显然(f[i][j]=max{f[i][k]},k<j)
对于向左的线段，有可能有贡献的只有中间某一段
for(int i=a[i].l+1;i<=a[i].x;++i) f[i][j]=max(f[i][j],f[i][j-1]+c[j]-c[j-1]);
对于向右的线段，枚举右端点考虑向右会做出多少贡献
对于覆盖到的某个端点位置，如果这个端点位置向左可以超出当前线段左端点，我们将它算在贡献内
int maxn=f[i-1][a[i].x];
for(int j=a[i].x+1;j<=a[i].r;++j)
{
f[i][j]=max(f[i][j],maxn+c[j]-c[a[i].x]);
if(id[j]&&a[id[j]].l<a[i].x) maxn=max(maxn,f[i-1][a[id[j]].l]+c[a[i].x]-c[a[id[j]].l]);
}
答案(y=ax^{frac{3}{2}})显然是一个下凸函数，考虑如果是序列问题，那么显然可以三分
在树上，我们则进行点分治
考虑答案点，显然它向四周移动都会使答案变大，所以我们任意选择一个点，向着答案会缩小的那颗子树移动，则只会选择一颗子树
我们用点分治，计算所有子树的导数
导数形式是(frac{3}{2}*val_x*dep_x^{frac{1}{2}})，暂且称作(d_i)
向某个子树(i)移动时，答案的导数是(sumlimits_{fa[t]=now}d_t-d_i)
我们找到导数小于(0)的那个子树找重心递归下去
复杂度(O(nlogn))
奇妙性质大发现：
我们发现如果两个集合的交只有两个点，那么这两个点一定是非叶子节点且之间有一条边
特判(1)个点和(2)个点，以及只有(1)个和(2)个非叶子节点的情况
然后(bitset)优化
复杂度(O(frac{n^3}{w}))
这洛谷给的题意实在狗屎。。。
第一行给定数个字母的元音和辅音
接下来(m)个要求，其他的不用解释了
预处理出来每个字符大于它的第一个元音和辅音字符
参照(2-sat)建图
从后向前一个一个贪心地修改原串，然后用(2-sat)法判断是否可行
如果同一位置两个情况都被遍历到退出
设(l[i])为(1-i)中(LIS)的长度，(p[i])为上一项的位置
(f[i])为长度为(i)的(LIS)最后一项的最小值，(g[i])为它的位置
我们先给最后加一项正无穷保证被选到减少细节
假设每个数可以填多次，因为填同一个数肯定不会出现在同一个(LIS)中
非空项我们可以在(f)上二分找到上一项
空缺项从大到小枚举长度，当(f[j])小于当前数字时更新(f[j+1])和(g[j+1])
然后倒序还原序列，最后一项无穷大肯定入选
维护三个变量，当前长度(i)，当前位置(j)，当前数字(x)
如果是非空项，上一项是空的，二分找最大的能填入的数字
如果空项，在前面找第一个长度为该项(-1)，且数字小于(x)的项
如果非空项找不到，就找上一个空项，填能填的最大数字
其他空项随便填
对于每次合并建立一个虚点，将(x)编号改为虚点，(y)并到虚点下
先把森林建出来，那么每个位置的答案就是这个位置最近一次清空到现在为止的总和
用树状数组维护每个时刻的加和，递归统计答案