T1

询问中三元组个数满足

对,合法的的个数是

对求和所有的倍数的之和即可

复杂度是调和级数

T2

给出两个串,求串的子串个数使得包含至少一个

正难则反直接转成串的子串个数使得不包含一个

那么 后直接对每个起止点求一下扩展范围即可

T3

给出排列，求位置中字典序小的数

先给***做法，考虑字典序是全序关系，直接先对排序后得到绝对位置再主席树

更好的做法是直接在可持久化树上插入并二分

T4

给出一些不相交的圆，多次询问从一个圆到另一个圆路径经过弧的最小值

关于具体题意可以直接自己试试些暴力过大样例

考虑建出一个森林一棵树使得每个点代表一个圆，树上的父亲对应的圆是最小的包含的圆，即不存在满足

然后变成树上的讨论，在此不表

if(vis[x]^vis[y])printf("%d\n",dep[x]+dep[y]-2);//不同树
else lca=LCA(x,y),printf("%d\n",dep[x]+dep[y]-2*dep[lca]-(x!=lca)-(y!=lca));//同树

考虑优化建树

首先可以用树，也不表

实际上观察到性质一个圆从圆心向上走碰到的第一个非自己的圆一定是父亲或兄弟中的一个

所以首先把左右边界扫描线掉，然后把区间内有覆盖的上下弧加进来

碰到的最低是下弧代表找到兄弟，碰到最低是上弧代表找到父亲

实现可以用