一行超人

B.我们可以强行把数字按照从大到小加入，当当第一次形成了一个>=k的长度的连续的已经被选出来的数的时候，那么ans[k]一定就是刚加进去的这个数。

C.注意到询问实际上是求$$[gcd(a[i],a[j])==1]$$

  用莫比乌斯反演转化成求$$\sum_{d|a[i]且d|a[j]}μ[d]$$

  然后这个公因数的话就可以记录一个$s[x]$表示有x这个因子的数的个数，然后对因子分开算贡献。

E.给出n个字符串，每次询问s[l,r]中字符串s[k]出现了多少次。

  这个问题有很多做法。

  我考场上想的是转化成前缀差，然后就可以一个一个字符串加入广义SAM，然后查询一个字符串出现了多少次。

  然而这需要动态维护right集合。我以为和BZOJ2555一样大力出奇迹就直接暴力更新了。

  然后发现WA了。原来是因为广义SAM插入的时候有可能在树的中间，这样就不能暴力更新了。除非每次dfs一遍子树？

  考完试后想了想如果我们事先把整个SAM建出来，然后每个字符串跑一遍，那么子树中编号∈[l,r]的个数就是我们的ans。

  这一步可以主席树或者离线之后树状数组搞定。

  然后AC自动机可以在fail树上进行同样的操作。

  后缀数组的做法也很直观。不过最近SAM做多了根本没往SA想。

  我们对所有串连在一起建立SA，那么s[k]出现的时候一定作为某个后缀的前缀。我们可以二分出s[k]向左向右拓展的最远点然后就成了和上面一样的问题。

还是太naive了。在A上花费了太多时间。然后还被hack了一次。最后还fst了。

不过上了黄还是蛮开心的

A.首先我们可以找出上下各第一次到达a1，a2的时间，然后找一下下一次到达a1，a2的时间。

中间特判掉无解和有部分解的情况。

那么剩下的可以exgcd。

也可以枚举上面那个走的循环节的个数，然后下面每一次就是一个新的函数，不超过m次肯定出现循环。所以答案可以在$O（m）$内找到。

我考场上直接让上下两个指针一个循环节一个跳着走。然后这样复杂度是不确定的。

然而走10*m次也能AC