T1  询问中三元组个数满足  对,合法的的个数是 对求和所有的倍数的之和即可 复杂度是调和级数 T2  给出两个串,求串的子串个数使得包含至少一个  正难则反直接转成串的子串个数使得不包含一个 那么 后直接对每个起止点求一下扩展范围即可 T3  给出排列，求位置中字典序小的数  先给***做法，考虑字典序是全序关系，直接先对排序后得到绝对位置再主席树 更好的做法是直接在可持久化树上插入并二分 T4  给出一些不相交的圆，多次询问从一个圆到另一个圆路径经过弧的最小值  关于具体题意可以直接自己试试些暴力过大样例 考虑建出一个森林一棵树使得每个点代表一个圆，树上的父亲对应的圆是最小的包含的圆，即...

注意到不相交的情况太多(我考场上写换根写疯了) 首先考虑反求问题，不相交的路径数=所有路径数-相交路径数 考虑相交有哪些情况  我们把第三种颜色互换一下就变成了第二种 我们发现绿色的链总是过黑链的的 我们考虑枚举这个 他可以是两条只在子树内的链或者是一条子树内的链和一条从子树内(可以不进)到子树外的链 因此我们只需要算过一个点子树内的链长为方案数以及从子树内(可以不进)到子树外的链长为方案数 考虑一条链拆成两条 设从出发,子数内单链长为的方案 则 设从出发,子数外单链长为的方案 则 就是来自父亲上面的，父亲下面不过自己的  合并的时候是类似背包的,我们把前面的儿子()与合并 因此 更简单

有一个长为的数组，它是由长为的数组,,...,重复次得到的。定义这个数组的一个区间的权值为它里面不同的数的个数，现在，你需要求出对于这个数组的每个非空区间的权值之和。答案对取模。  注意到计算每一个区间的影响是很难的,因为我们能表示一个区间颜色种类数的方法是最快的 的项链 而这道题让我们放弃 这又是一个套路了，既然我们不好直接求，那么拆分问题 给一个相似的例子 求两两异或的和 肯定正着做不好做，但考虑到，这个问题在时就很好做 因此想到拆位 对于这道题也是一样，考虑计算每种颜色贡献的区间 仿佛也不好做，但正难则反，计算每种颜色不会贡献的区间很简单 那就是相邻的两个颜色间的所有区间 对的序列我们可...