题意：略
题解：略
题意：略
题解：略
题意：略
题解：略
题意：略
题解：略
题意：略
题解：略
题意：略
题解：略
题意：略
题解：略
题意：略
题解：略
题意：略
题解：略
题意：略
题解：略
题意：略
题解：略
题意：有$N$个珠子，第$i$个颜色为$C_i$，价值为$V_i$。你要选出至少$3$个串成项链，使得价值和最大并且相连两个颜色不一样。
题解：预处理前缀和，然后一段相邻不一样的一起处理即可。
题意：有$H \times W$的格子，有红，青，黑三种颜色，一开始被红黑染色了。每次可以对格子做一次操作，操作后，所有格子同时发生如下变化：如果这是个红色格子，并且相邻的有青色格子，那么这个格子变成青色。
有$Q$个限制，第$T_i$次操作后，如果位置$(X_i, Y_i)$是红色，那么这个会变成青色。求出最少操作几次才能使得全部格子变成青色。
题解：令$d(i,j)$表示位置$(i,j)$最早什么时候变成青色，把所有限制加进去，跑个Dijkstra即可。
题意：给出$N$个点的树，第$i$条边连接$A_i$和$B_i$，边权为$C_i$。有$Q$个询问，每次询问第$Z_j$条边不能走之后，在$Y_j$分钟内，点$X_i$能够到达多少点。
题解：树分治，然后可以直接统计。
题意：略
题解：略
题意：有$N$个草莓，第$i$在位置$A_i$，会在$T_i$时刻成熟。你一开始在位置$0$，每秒最多走一单位距离。你只能在草莓成熟后再采摘。求出摘完所有草莓并回到位置$0$的最小耗时。
题解：肯定要先走到最远的草莓的位置，然后从后往前看看时间够不够当前草莓成熟。够的话直接采了往回走，不够的话先等等。
题意：有个$1$到$N$的整数，每次可以执行下面操作：把这个数变成他和他的数位和之和。求出有多少数可以变成$N$。
题解：$x$能够变成$y$构成了一棵树，直接从$N$开始dfs即可。
题意：有个包含$0$到$9$的数字键盘，一开始你在$0$的位置。你可以上下移动，或者按下一个键。求出最小操作次数，使得能够得到一个模$M$余$R$的整数。
题解：直接bfs即可
题意：定义石头剪刀布表达式，用R表示石头，S表示剪刀，P表示布。
-
$x+y$ 的结果：如果$x \ne y$，那么结果为$x$和$y$胜出那个；否则，结果为$x$。 -
$x-y$ 的结果：如果$x \ne y$，那么结果为$x$和$y$失败那个；否则，结果为$x$。 -
$x*y$ 的结果：如果$x \ne y$，那么结果为不是$x$，也不是$y$的那个；否则，结果为$x$。
给出一个长度为$N$的表达式$E$，有(，)，+，-，*和RSP?，你需要把?换成RSP某个，使得最终结果为$A$。求方案数，对$10^9+7$取模。
题解：用栈处理这个表达式，操作数栈存储一个数组$ways(x)$表示结果为$x$的方案数，然后定义下+，-和*运算即可。
题意：给出$N+1$个整数$A_1,A_2,\dots,A_N,A_{N+1}$和$N$个整数$B_1,B_2,\dots,B_N$。对于每个$i=1,2,\dots,N,N+1$，你需要求出删掉$A_i$后，剩下数组一一匹配后$\max(A-B,0)$的最大值。
题解：显然各自排序，然后一一匹配是最优的。删掉一个数后，可以通过前缀和后缀取个最大值得到答案。
题意：给出一个长度为$N$的字符串$S$，你可以删掉一个首字符，一个末尾字符，或者删掉中间一个字符。使得最后得到的字符串是$K$个J，然后$K$个O，最后是$K$个I。求出最少需要删几次中间字符。
题解：枚举第一个J出现在哪里，那么接下来O和I都要尽量往左靠。
题意：有$N$个邮票在周长为$L$的圆周上，第$i$个在位置$X_i$，需要在$T_i$时刻前拿走。一开始在位置$0$，每秒可以顺时针或者逆时针走一个单位距离。求出最多能够拿到多少邮票。
题解：令$dp(l,r,k,0/1)$表示当前$0$左边的$l$个邮票和$0$右边$r$个邮票都走过了，总共取得了$k$个邮票，当前位置在左侧还是右侧时的最少用时。转移比较显然。枚举下一次往左还是往右即可。
题意：有$N$个点$M$条边的有向图，第$i$条边从$U_i$到$V_i$，边权为$C_i$，可以花$D_i$代价改变边的方向。你可以最多修改一条边的方向，使得从$1$到$N$的最短路和从$N$到$1$的最短路之和加上修改代价最小。
题解：求出翻转每条边后从$1$到$N$的最短路以及从$N$到$1$的最短路即可。考虑删掉第$i$条边后求$1$到$N$的最短路，显然新的最短路是$1$到$V_i$的最短路+$U_i$到$N$的最短路+$C_i$。先预处理出$1$到$i$的最短路和$N$到$i$用反向边的最短路，那么如果第$i$条边不在$1$到$V_i$的最短路上，那么最短路不变；否则可以删掉这条边重新求最短路。$N$到$U_i$的也是类似。因为毕竟边只有$O(N)$条，因此复杂度是$O(N^3+M)$的。
题意：有一个数组$S_1,S_2,\dots,S_N$。令$S_i(0)=S_i,S_i(t)=\max{S_{i-1}(t-1),S_{i}(t-1)}$。现在有$Q$个询问，你需要求出$S_{L_j}(T_j)+S_{L_j+1}(T_j) + \dots + S_{R_j}(T_j)$的值。
题解：把$S_i(t)$画成一个$(N+1) \times N$的矩阵，可以发现$S_i$的出现位置是一个平行四边形。这个平行四边形与$i$左边第一个大于$S_i$的位置和$i$右边第一个大于等于$S_i$的位置有关。问题等价于给出$(N+1) \times N$的矩阵里的$N$个平行四边形，然后询问第$T_j$行内$L_j$到$R_j$位置的和。
然后这个平行四边形可以转化为$3$个直角三角形加加减减。我们把询问变成前缀和加加减减的话，就是要考虑一个三角形对一个前缀和询问的贡献。假设有个$[L_i, R_i)$的三角形，权值为$W_i$，然后你需要查询第$T$行里前$x$列的前缀和。可以发现，
- 如果$T \ge R_i - L_i$的话，这个三角形对这个前缀和没有任何贡献。
- 如果$x \ge L_i+T$，那么这个三角形的贡献是$W_i \times (x - L_i - T + 1)$
- 如果$x < L_i + T$，这个三角形对这个前缀和也没有任何贡献。
于是可以这么考虑，我们可以一开始把所有$[L_i, R_i)$都加上一个$W_i$。然后按照$T$从小到大处理每个询问，遇到$T = R_i - L_i$的话取消这个三角形的修改，我们可以直接查询$x$的前缀和，但是会有东西多加了，具体为：
- 如果$x \be L_i + T$，多加了$W_i \times T$
- 如果$L_i \le x < L_i + T$，多加了$W_i \times (x - L_i+1)$
这个可以额外维护两个树状数组来分别维护下。
题意：给出两个长度为$2N$的数组$A_1,A_2,\dots,A_{2N}$和$B_1,B_2,\dots,B_{2N}$。你需要选出$N$个位置全部保留$A_i$，剩下$N$个位置全部保留$B_i$，使得最后得到的数组$C_1,C_2,\dots,C_{2N}$递增。
题意：可以分治然后FFT合并，但是这样复杂度是$O(N \log^2 N)$的，过不了。可以发现的是，令$dp(i,j)$表示前$i$个里选了$j$个A是否可行，那么$dp(i,\cdot)$中一的位置肯定是连续的。那么我们其实可以dp出这段连续值的左边界和右边界。方案构造也是显然的。
题意：给出$N$个矩形，第$i$个矩形左右边界是$L_i$和$R_i$，上下边界是$U_i$和$D_i$。你需要选出$K$个点，使得每个矩形内至少有一个点。保证一定存在一个解。
题解：考虑一维的情况，如果$K=2$的话，第一个点肯定是放$R_i$最小的那个位置，第二个点肯定是放$L_i$最大的那个位置比较好。
因此我们可以先求出$\min_R, \max_L, \min_U, \max_D$。注意到如果$\max_L \le \min_R$的话，说明只要选出来的点$x$坐标在$[\max_L, \min_R]$内的话，就可以忽略掉$x$坐标了。当$\max_D \le \min_U$的时候也是类似。于是可以假设$\min_R < \max_L$并且$\min_U < \max_D$。
也就是说，这$4$条线上我们都得有个点放在上面，也可以放在角上从而覆盖多条边，然后就是分情况讨论了。
-
$K=1$ ，在这种情况下肯定无解 -
$K=2$ ，我们肯定要放在两个对角上 -
$K=3$ ，首先肯定要放在一个对角上。不妨枚举一下，然后把已经覆盖的矩形删掉，剩下就是$K=2$的情况。 -
$K=4$ ，有点放在对角上的话，和上面类似，可以枚举一下变成$K=3$的情况。
接下来可以假设$K=4$并且每个点一定是放在每条边的中间。考虑通过扫描线枚举$x=min_R$上的那个点$p_R$，那么可以维护：
-
$U$ 表示未被$p_R$覆盖，并且和$\min_U$有交，和$\max_D$没有交的矩形集合 -
$D$ 表示未被$p_R$覆盖，并且和$\max_D$有交，和$\min_U$没有交的矩形集合 -
$UD$ 表示未被$p_R$覆盖，并且和$\max_D$有交，和$\min_U$也有交的矩形集合 -
$L$ 表示上述三类以外的所有矩形
然后我们来贪心确定$\min_U$和$\max_D$上的点，假设$p_U.x < p_D.x$。那么$p_U.x$肯定就是$U$和$UD$里面矩形$R_i$的最小值。知道了$p_U$后，我们可以类似的确定出$P_D$。就是$D$和$UD$中未覆盖矩形$R_i$的最小值。然后剩下来的只剩下$\max_L$这条边，只需要检查下剩下来的矩形是否在这条线上有交即可。可以用线段树维护这些矩形，然后就是查询后缀最大值，最小值。也可以把矩形集合划分的更加具体，然后求后缀最小最大即可。
题意：有一个边长为$N$的直角三角形，三个顶点坐标分别为$(0,0)$，$(N,0)$和$(0,N)$。有$M$个点在三角形里面，一开始坐标为$(X_i,Y_i)$。有两种类型的操作：
-
procedure H，如果一个点$(x,y)$满足$0 \le x \le N-l,0 \le y \le l$，那么这个点会移动到$(N-l,y)$。 -
procedure V，如果一个点$(x,y)$满足$0 \le x \le l,0 \le y \le N-l$，那么这个点会移动到$(x,N-l)$。
现在给出$Q$个操作：
- 计算第$P_j$个点现在的位置；
- 用一个长度为$L_j$的线段执行
procedure H； - 用一个长度为$L_j$的线段执行
procedure V； - 加入一个新的点$(A_j,B_j)$
题解：考虑用Treap或者动态开点的线段树维护点集，每个点集$x$和$y$坐标都递增。那么一次procedure H或者procedure V，就是拿出一些点集，然后把它们合并成同一个点集。可以证明，总的操作涉及的点个数是$O(M+Q)$的。用另外一个线段树维护这些点集，每次procedure H或者procedure V的时候就可以快速找出所有涉及到的点集。然后用线段树合并暴力合并点集即可。
题意：交互题。有$2N$只变色龙，其中$N$只性别为X，另外$N$只性别为Y。每只变色龙有一个初始颜色$C_i$，保证性别为X的变色龙初始颜色都不一样，且对于每个性别为X的变色龙，都恰好存在一个性别为Y的变色龙和它初始颜色一样。
现在你需要通过交互找出每对颜色相同的变色龙，已知
- 任意一只变色龙都恰好喜欢另一只性别不同的变色龙。
- 任意一只变色龙一定只喜欢和他颜色不一样的变色龙。
- 不存在两只变色龙喜欢同一只变色龙。
每次你可以询问一些变色龙集合$P$，然后会返回这个集合里有多少不同的皮肤颜色。对于一只变色龙$s$，如果它喜欢的变色龙$t$存在，那么它的皮肤颜色会变成$C_t$，否则皮肤颜色是$C_s$。你最多询问$20000$次。
题解：首先如果询问$i$和$j$后返回的颜色数$1$的话，显然$i$和$j$初始颜色一样或者其中一个喜欢另一个。我们不妨在$i$和$j$之间连一条边。显然这样一个图是二分图，并且每个点度数很小。因此我们可以考虑通过一些询问构建出这个图。
考虑按照$1,2,\dots,2N$的顺序加入每个点，在加入第$i$个点的时候，我们可以把$1,2,\dots,i-1$分成两个集合，每个集合直接都没有边。然后考虑可以通过二分知道$i$和哪些点相邻。现在我们可以考虑根据这个图来计算答案。
注意到，每个点的度数要么是$1$，要么是$3$。如果一个点$v$度数为$1$，那么肯定存在一个点$u$，它俩互相喜欢，这个说明和$v$直接相连的点肯定是颜色一样的。我们可以先把这些点都处理掉。接下来对于一个度数为$3$的点$v$，我们可以考虑询问三次来计算$v$喜欢的节点。假设$v$相邻的点为$u_1,u_2,u_3$，你可以询问${v,u_i,u_j}$，出现颜色数是$1$的话，说明剩下那个是$v$喜欢的点。那么可以把这些边都删掉，剩下的就是颜色一样的边。
题意：有$N$个点，一开始之间没有任何边，有$M$条有向边会依次加入。每次加入边之后，你需要求出重复执行完下面过程后，图中边的条数：
- 找出一个三元组$(x,y,z)$，$x$到$y$有边，$y$到$z$有边，$z$到$y$有边，$z$到$x$没有边，然后加入一条$x$到$z$的边。
题解：注意到，如果$x$和$y$互相有边，$y$和$z$互相有边，那么执行上面的过程后$x$和$z$也一定互相有边。我们把这种任意两点有互相有边的点当成一个整体。考虑两个这样的东西$A$和$B$，如果$A$里面有边到$B$，且$B$之间有边到$A$，那么显然可以把$A$和$B$合并成同一个。
因此对于每对$(A, B)$我们维护从$A$出去到$B$的边表集合。对于加入的一条边$u$和$v$，先找出他们所在的集合$U$和$V$。如果$V$有边到$U$，那么会发生一次合并。合并的时候可以启发式合并。然后可以发现，合并之后会有一些新的边加入，你需要递归的做这个事情。
题意：有$2N$个数$h_1,h_2,\dots,h_{2N}$，其中$i$恰好出现两次。有$N$次操作，每次操作如果$h_i$满足而对于任意$j > i$且$h_j \ne h_i$，那么$h_i$不变，其他数都减少$1$。现在告诉你$N$次操作后，$h_{A_1},h_{A_2}, \dots, h_{A_N}$还至少为$1$。求出$h$的方案数，对$10^9+7$取模。
题解：对于一个初始的状态$h_1,h_2,\dots,h_{2N}$，我们可以考虑如下过程来求哪些位置是可以留下来的：
- 从后往前考虑每个数$h_i$，同时维护$mark(x)$表示地震完后高度为$x$的是否确定了。
- 如果$mark(h_i)$不存在，显然这个位置$i$是要留下来的。
- 如果$mark(h_i)$存在，显然如果能找到一个小于$h_i$的最大$x$，使得$mark(x)$不存在，那么$h_i$也可以留下来，并且$h_i$最终高度是$x$。
可以发现如果我们维护了一个最大的$y$，表示$1,2,\dots,y$里的高度值都确定了，如果$h_i \le y$肯定是不能留下来的，否则可以留下来。于是可以考虑dp这个$y$。
令$dp(i,j)$表示考虑了位置$i+1,i+2,\dots,2N$后，最终高度为$1,2,\dots,j$的位置都已经确定了的方案数。显然如果位置$i$没留下来，那么当前位置有$j-remove_i$种填法，其中$remove_i$表示$i+1,i+2,\dots,2N$中没有留下来的位置个数。下面考虑位置$i$留下来的情况。
我们加入位置$i$后，可能会导致确定的高度变多，不妨假设新确定下来的高度为$k$。那么这就说明我们要从之前的位置里选出$k-j-1$个来，然后确定初始高度，使得$j+1,j+2,\dots,k$这些最终位置都确定下来。显然这个方案数只和$k-j-1$的大小有关，不妨记为$ways(k-j-1)$。于是我们的转移方程可以写成$dp(i,j) \cdot \binom{keep_i-j}{k-j-1} \cdot ways(k-j-1) \cdot (k-j+1)$，其中$keep_i$表示$i+1,i+2,\dots,2N$中留下来的位置个数。
注意到我们每个高度都重复填了两次，所以最后$\frac{dp(0,N)}{2^N}$就是答案。
题意：$N \times N$的格子里，对于第$i$列，从$1$到$A_i$行的格子都是白色的，剩下格子都是黑色的。现在在这个基础上有$M$个格子$(X_j,Y_j)$被染成了黄色，把它改成黑色的代价是$C_j$。你需要把其中一些黄色格子改成黑色，使得不存在这样的子矩形：子矩形里面没有白色格子同时包含至少$2$个黄色格子。求出最小代价。
题解：从上往下依次考虑每个极大的子矩形，显然每个子矩形里面最多只保留一个黄格子。我们可以对这个子矩形构建一个树形结构。
假设某个子矩形不保留任何黄格子，显然最优值就是把子节点求个和。如果这个子矩形在位置$x$保留了一个黄格子，考虑$A_x$那一行，我们知道这个子树下有一些区域一定不能放黄格子，这个在树上对应了一条路径。我们需要把这条路径的岔路上的节点求和当做最优值。这个可以DFS序+树状数组求和搞定。
别解：先转化成保留代价和最大的黄格子，那么，对于每一列，显然只能保留一个黄格子。令$dp(i,y)$表示在第$i$列的第$y$行保留了一个黄格子的最优代价。考虑从$A_i$最小的那一列开始，依次把每一列加入。显然，你加入一列之后可能会和左边或者右边的列合并成一个大的连通块。
假设新加入的这一列是$f$，它对应的$a_i=y$，并且和左边的$g$合并了，我们需要求出他们合并后的新的dp值$h$。可以发现，$g$里面$y^\prime \le y$的都没用了，因为肯定是合法的，我们只需要保留一个最大的即可。显然有$h(i)=\max(f(i)+g(y),g(i)+f(y))$。假设我们采用启发式合并的方法来求$h$的值，并且额外维护一个$h_tag$，那么其实就是等价于先给$f$整体加一个$g(y)$，然后对于每个$i$，那$f(i)$和$g(i)+g(y)$取最大值。这个用一个std::map即可很方便的实现。
题意：在长度为$L$的圆周上，有$N$个人和$M$棵苹果树。第$i$个人在位置$A_i$处，第$j$棵苹果树在$B_j$处。每个苹果树同时最多结一个苹果，一个苹果被摘走后，$C$后会长出一个新的。每个人以$1$单位距离每秒的速度沿圆周绕行，遇到有苹果的树的话，会摘走苹果。有$Q$个询问，直到$T_k$时刻，第$V_k$个人摘了多少次苹果。
题解：首先我们可以考虑人不懂，然后树做逆时针方向运动。那么这样一来，每棵苹果树$j$第一次被哪个人$NB_j$采摘是确定的，同时也可以确定出在$WB_j$秒后会被这个人采摘。然后一旦这个苹果树被第$i$的人采摘了，那么下一次采摘这个苹果树的人$NA_i$也是确定了，距离下次采摘的时间间隔$WA_i$也确定了。这些都可以通过二分处理出来。可以发现，所有人构成一个环套树。然后考虑一个询问。
如果询问的人$V_k$不在环上，那么显然之后这个人下面的子树内的苹果树能够被这个人采摘。令$depth(u)$表示树上节点$u$距离根的权值和，显然一个苹果树$j$在$T_k$时刻能够被$V_k$采摘当且仅当：$depth(NB_j)+WB_j-depth(V_k) \le T_k$。这个可以通过求出DFS序，然后离线询问出来。
如果询问的人$V_k$在环上，那么情况有点复杂。首先第$j$棵苹果树应该能够到达这个环，也就是说$depth(NB_j)+WB_j \le T_k$。之后，这个苹果树可能在环上无限绕圈。假设环长为$L$，然后随便选一个起点把环拉成一条链。令$sum(u)$表示起点到环上一个点$u$的距离，$top(v)$表示树上一个点往上会走到环上一个点$v$。那么显然这个苹果树$j$的贡献为 $$ \lfloor \frac{T_k-sum(V_k)+L}{L} \rfloor +1 - \lfloor \frac{depth(NB_j)+WB_j - sum(top(NB_j) + L)}{L} \rfloor - [(T_k-sum(V_k)) \bmod L < (depth(NB_j)+WB_j - sum(top(NB_j)) \bmod L] - [sum(V_k) \le sum(top(NB_j))] $$
显然这个也是可以离线，然后用树状数组维护的。
题意：通信题。有一个$N$个点$M$条边的连通无向图，Anthony住在$0$号点，也知道图的样子。Catherine要去$0$号点找Anthony，但是他不知道图的样子。Anthony需要给每条边标记一个$0$到$A$的值，使得Catherine能够根据这些标号来到达$0$号点。假设Catherine初始点到$0$的距离是$d$，那么Catherine需要走不超过$d+B$步。
题解：对于$A \ge 3$，显然给一条边$(u,v)$标记为$\min(dist(u), dist(v)) \bmod A$就可以了。
接下来考虑一条链的情况，我们肯定是需要用不超过$3$步确定当前走的方向，然后如果走反了则用$3$步回到原点，接下来往前走。可以发现，我们从起点开始走$3$步的话其实可以获得$5$条边的标记状态。如果我们能够给整条链按照某个周期给边染色，然后通过这个周期我们可以用$5$条边信息确定在这个周期的位置的话，链的问题就解决了。然后可以发现，周期长度为$6$就够了。通过打表可以发现以下这几个都是可行的：110100, 101100, 110010, 011010, 100110, 010110, 101001, 011001, 100101, 001101, 010011, 001011。
然后，如果不是一条链的话，对于每个度数大于等于$3$的点，考虑把父亲的边染成$x$，儿子的边都染成$1-x$。于是当我们在走链的时候，按照上述方法染色；走到一个度数超多$2$的点后，直接判定往哪个方向走即可。
题意：有一棵$N$个点的树，每个点有一个$1$到$K$的颜色$C_i$。你每次可以选择两种不同的颜色$x$和$y$，把所有颜色为$y$的点改成颜色$x$。求出最小操作次数，使得存在一个颜色$x$满足所有颜色为$x$点都是连通的。
题解：其实就是选出一个连通块，使得里面颜色数最少，然后出现过的颜色都在这个连通块内。考虑树分治，假设这个连通块过这个分治重心$r$。也就是$r$必选，然后你就知道哪些颜色也必选，依次加入每个颜色直到不能加为止。用一个并查集做即可。
题意：提交答案题。有一个$R \times C$的格子，每个格子有P，W和G三种颜色。你需要选出一些连续的$1 \times 3$或者$3 \times 1$的子矩形。使得这个格子颜色依次为PWG或者GWP。每个格子最多属于一个子矩形，求出最多能选出多少个子矩形。
题解：可以先预处理出所有可能的子矩形。然后不断迭代以下过程，直到符合要求为止：
- 选出所有没有使用的子矩形集合$S$
- 按照一个随机的顺序枚举$S$里的所有子矩形
- 如果这个子矩形可以放下去，那么就放下去
- 如果这个子矩形和之前另一个子矩形相交，可以把之前那个拿掉，把当前这个放下去
- 如果这个子矩形和之前多个子矩形相交，那么无视这个矩形。除非答案很长时间没有被更新了，那么你需要拿掉这些矩形，然后放下当前这个。
按照这个过程，除了第$5$组数据跑了几分钟以外，其他都很快出解。
题意：数轴上有$N$个点，依次标号为$1$到$N$。一开始所有点都是黑色的。有$M$次操作，第$i$次操作会在$T_i$时刻把$L_i \le x \le R_i$的点都染色成白色，代价是$C_i$。如果第$x$个点在当前时刻是黑色的，那么下一个时刻$x-1$和$x+1$会被染黑。你需要选出代价和最小的操作，使得按照$T_i$顺序做完这些操作后，所有格子都变成了黑色。
题解：显然如果存在一个$L_i=1,R_i=N$的操作的话，我们可以只选这个操作，因此这种操作可以先全部去掉。考虑建立一个坐标轴，横坐标是时间$t$，纵坐标是$N$个点的位置$y$。然后一次操作$i$对应了在$t=T_i$处放一条$L_i \le y \le R_i$的线段，然后在$t=T_i+k$时刻这个区间会变成：
-
$L_i \ne 1$ 并且$R_i \ne N$，会变成$[L_i+k,R_i-k]$ -
$L_i=1$ 但是$R_i \ne N$，会变成$[1,R_i-k]$ -
$L_i \ne 1$ 但是$R_i = N$，会变成$[L_i+k,N]$
然后可以发现，随着$k$变大，如果和另一个操作$T_j$的区间$[L_j,R_j]$有交的话，那么这两个区间可以合并。在某个时刻这个区间变成$[1,N]$的话，我们就找到了一组解。
考虑从$L_i=1$的操作出发，一个$T_j \le T_i$的操作$j$能和它合并的条件是$L_j+T_i-T_j \le R_i + 1$；一个$T_j \ge T_i$的操作$j$能和它合并的条件是$R_i-(T_j-T_i) + 1 \ge L_j$。
我们把满足上面条件的$i$和$j$建立一条从$i$到$j$的有向边，每个点$i$的权值为$C_i$，那么显然从某个$L_s=1$的操作$s$出发，到达某个%R_t=N$的操作$t$的最短路就是答案。用一个线段树优化的Dijkstra就可以搞定了。
题意：略
题解：略
题意：略
题解：略
题意：给出长度为$N$的字符串$S$，总共有$N+1$个位置，依次从$0$标号到$N$。每次可以选择一个$i$ (
题解：$2^{N/2}$枚举切法即可。
题意：有一个长度为$2N$的序列$A_1,A_2,\dots,A_{2N}$。一个序列是好的，当且仅当存在一个$B$使得$A_1,A_3,\dots,A_{2N-1} \ge B$并且$A_2,A_4,\dots,A_{2N} < B$。你每次可以选一个$A_i$，变成$(A_i+1) \bmod K$或者$(A_i-1) \bmod K$。
现在有$Q$个操作，每次给出一个区间$[L_i,R_i]$和一个数$X_i$，对于每个$j$ (
题意：有$N$只动物，第$i$只喜欢第$L_i$只。第$i$只的防御力为$A_i$，拥有$X_i$个毒药。对于每个动物$i$，你需要求出杀掉除了第$i$只和第$L_i$只以外所有动物所需要的最小攻击力。你有两种方法杀死动物：
- 选择一只动物，然后毒死它，消耗一个毒药。
- 选择一只动物，用攻击力杀死它。你的攻击力必须大于等于这只动物的防御力加上所有活着的还喜欢它的动物的防御力之和。
题意：有$N$个点，一开始没有边。总共有$N-1$次加边操作。每次会给出一个$A_i$，保证$1$能够到达$A_i$，但是不能到达$i+1$，然后用一条长度为$C_i$的边连接$A_i$和$i+1$。
每次操作完求出$\sum_{i=2}^{N}dist^K(1,i)+\sum_{i=3}^{N}dist^K(2,i)+\dots+\sum_{i=N}^{N}dist^K(N-1,i)$，对$10^9+7$取模。如果$p$不能到达$q$，$dist(p,q)=0$。
题解：首先有个公式$x^n=\sum_{i=0}^{n}S(n,i)(x)i=\sum{i=0}^{n} \frac{S(n,i)}{i!} \cdot \binom{x}{i}$。因此我们可以通过维护组合数的方式来求$dist^K(p,q)$。
先把所有边插进去，然后树分治