由于某些题目年代过于久远，代码不再附赠
Walk
给定n个点m条单向边，边权为1
每个点有一定的点权，点权在2^20以内
若vali&valj=valj则i到j之间还有一条长度为1的单向边
现在从1出发，求到各个点的距离，若无法到达则为-1
我们将图分层
额外的边可以看作点与点权连边然后点权和点权连边最后再回到点
其中只有点权到点的边权设置为1，其余为0，岂可满足题目要求
显然这样的问题广搜即可，但我们要让边权为0的状态最优先；
access
有一棵 n 个节点，n-1 条边的树。树上有 m 条路径，定义两条路径相交仅当
这两条路径经过至少一个相同的点。小 D 想知道：从这 m 条路径中选择两条相交
的路径的方案数。
显然，两条链相交，必然有一条链的最低点被另一条包含
那么我们将点用欧拉序标号，然后根据欧拉序的性质，我们可以用树状数组维护一个点到根的路径上包含了多少点
但我们要注意两个最浅点相交的情况，此时答案要减去i*i-C（i，2）次 （i为深度）
father
对字符串进行一系列的区间操作，然后让你输出字符串的前k个，经典的“倒着做”问题。
如果倒着一个个的去还原，复杂度是O(nk)的，可以拿到40分。
想到倒着做之后就可以考虑优化了。
因为考虑到如果有操作[l,r]的话，那么[r+1,2r-l+1]的区间的答案是跟[l,r]区间的答案是一样的，所以可以用一个f[i]表示i这个点的答案是与哪个点的答案是一样的。
那么如何去处理这个点的答案是与那个点的答案一样的？
我考虑用暴力出奇迹，常数又大的线段树。
每个线段树存储这段区间内，独立点的个数（就是f[i]=0的点，及别的点的答案不影响这个点的答案），然后每次循环[r+1,2r-l+1]这段区间去更新线段树，每次找到第为r+1的点，因为1~r暂时被算作独立点，然后把r+1这个点修改为无效点，然后把这个点的位置q找出来，然后更新f[q]。当然f[q]的更新值也要用线段树来找。
小澳的方阵
给定一个矩阵，每次指定一行或者一列，在上面放上一种数字
问最终状态是什么
n,m<=1000,n*m<=10^5,q<=10^6。
我们发现n和m很少
将这个问题倒过来看
最后一个操作肯定不会被修改
且同一行同一列最多进行一次操作即可
也就是说我们最后要处理的操作只有 n+m个
成绩调研
石神显得有些心不在焉。最近恍恍惚惚，还请了两天假。
这一次的考试，学生的成绩分为k等，成绩单上按照学生的学号排序。此外，学校要抽一些同学的考
卷去调研，石神将这个任务委派给了你。 抽取的样本有如下要求：
学号连续的学生
得到1等的学生数量在[l_1,r_1]区间内
得到2等的学生数量在[l_2,r_2]区间内
现在请问有多少种抽取样本的方法。
发现每一个l所对应r区间是连续而单调得
所以我们只要对上界和下界进行维护就好了
计算下界可以转化成：给定一个序列，支持修改某个位置上的数，维护全局最大值。
而且这里的修改比较特殊，一定是把数字改大，所以我们不需要用到任何数据结构。
上界可以考虑把操作反过来，对于每一个确定得左边界，可以把有边界可以取到的范围大小累加
