A.签到题

仔细阅读代码，发现题目需要你维护一个线段集合，***插入线段，删除线段和求线段并长度。
我们考虑一种非常暴力的做法：对于这个数轴建出线段树，然后插入删除对应了区间加值操作。
我们来考虑一下询问操作：最朴素的方法是查询每个点是否有值然后统计答案。我们可以考虑对每一个线段树上的节点维护一个 min 值，这样遍历到一个节点的时候如果当前节点的 min > 0 那么说明这个线段树节点对应的区间是所有线段并的一部分。
当然这样的话还是不一定能过的，但是注意到数据随机生成，所以查询操作仅为总操作的 ，且删除操作大概率不会触发。

时间复杂度最差是的，但是由于数据随机生成，所以可以过。

B. Graph

这是一道正常的 Div2 难度题目（可能算不上）
题目要求的是障碍点经过总次数不超过 k 次的最短路。
我们可以考虑拆点：将点 v 拆成 k 个点 ，表示经过这个点时已经强行走过了多少不让走的障碍点。
然后按照我们拆点的定义直接建边即可。
我还是来讲讲怎么建边吧......
考虑把每个无向边 u-v 拆成有向边 和 ，然后我们考虑有向边 ，如果 $u$ 为障碍点的话对于每一个 连向 ，否则就由 连向。
然后建立超级起点 s 连向起点的第一个状态一条长度为 0 的单向边，每一个终点的状态向超级终点 t 连长度为 0 的单向边，最后在这张大图上跑最短路算法即可。

C. Study

签到题。
考虑我们只需要知道每一个单词最后是哪一次被背了就可以，那么对于每一行/列都记录该行/列最后一次被背诵的时间，输出的时候对于每一个点对应的行列数组求一个 max 即可。

D. Data Structure

阅读伪代码不难发现这是一个二叉搜索树。
注意到二叉搜索树的性质：左子树 < 节点 < 右子树。
我们可以考虑把所有的操作先读进来，记录一下每个数字是第几个被插入进来的，然后按照数字大小排个序。
考虑我们这次正在处理区间 [l,r]，如果能找到该区间最早被插入的数字 mid，那么就能把区间 [l,r] 递归分解为两个小问题 [l,mid-1] 和 [mid+1,r]（因为序列已经按照值排好序）。所以我们可以通过这种分治的方法来解决这个问题。

由于没有保证是个排列，如果想利用排列性质需要离散化。

时间复杂度 O(nlogn)

至于直接按照伪代码模拟的话，构造出一组有序数据不难卡到

E.Gift

首先可以明确的是：如果图不存在环那么肯定无解（因为走不回去啊）。
那么我们可以把一种路径的答案表示为：（ n 表示经过边的数量）
嗯......经典分数规划形式。考虑枚举答案 ans，可以得到判断式 ，用一些小学移项技巧可以得到。

F. Edges

这还是一道签到题......
通过数据范围 n = m-1 不难发现这是一棵树，注意到树上只有根和叶子的度可能为 1。
于是题目转变求为了一棵根为 S 的树，选择性切掉一些边，使得所有的叶子都不能到达根的最小代价。
让我们考虑树形dp（其实可能就是个统计算不上dp）：设 表示使得以 v 为根的子树内的叶子到不了 v 的最小代价，转移显然枚举每一条边切不切就可以了。
方程大概是这样：设当前我们要更新的点是 u，u 的一个儿子是 v，他们之间的边的边权是 w。则有转移方程

G.Sequence

注意到每一个元素 。
考虑加入的贡献，也就是答案增加了与插入的这个数互质的个数。我们如何快速计算这个东西呢？显然 NOIP 初赛告诉我们可以容斥。也就是说与一个数 x 互质的数的个数 = 总数-与 x gcd 为 2 的个数 - 与 x gcd 为 3 的个数 + 与x gcd 为23的个数......

这样就可以容斥了。注意到 ，所以容斥的复杂度是。可以通过。

要求的答案为：

设d的倍数有个，那么答案为：

每次插入和删除的时候只要枚举***作的数的因数然后维护一下即可。
复杂度 O(A log A + N log A)

H.Dynamic Graph

我们观察一下 有什么性质。

所以发现它是个经过一定次数迭代后与原函数相等的函数.....
仿照 B 题的做法拆点建图就可以了，每一个点拆成 $3$ 种不同的状态，设边 ，则由 连向 。

注意一下取绝对值和不要写 SPFA 算法就可以了。
时间复杂度 O((m+n)logn)

I.Xor

考虑求出题目中给出的递推式的一个封闭形式的解：

看到二进制异或就可以想一下是否可以按位处理。
我们考虑异或运算会造成贡献的唯一可能就是当前位上的二进制数字不相同，那么对于每一位，贡献就是 A 第 j 位出现 1 的次数 B 第 j 位出现 0 的次数 + B 第 j 位出现 1 的次数 A 第 j 位出现 0 的次数。 （乘法原理）
最后按照这一位对总答案的贡献统计一下就可以了。

时间复杂度 。

J.Math

时间复杂度 。