Solution：

　  先求出两种变化的第一次和第二次变化到目标的时间。

     对这四个时间的具体情况需要一些特判 。

     然后直接从1到2*N枚举其中一个时间的倍数，然后输出第一个满足要求的答案。

　  或者求出循环节后用拓展欧几里得求出最小解。

 

 

 

 

 

---

 

题意：

　　给定一个长度为n（<=2*10^5）的序列，分别求出长度为（1~n）的区间的最小数的最大值。

 

 

Solution：

　　可以先预处理以每个数为答案的最长区间。

      即从每个数分别从左和从右找到第一个小于它的数的位置，可以用单调栈O（n）处理。

      假设x的左右分别是l，r。那么区间1~(r-l+1)的值可以对x取max。实际上只需更新ans[r-l+1]，最后对ans[i]=max(ans[i],ans[i+1]).就行了

      时间复杂度O（n）

 

 

 

 

---

 

题意：

　　每次从一个数列（最多2e5个数）中添加或删除一个数，输出数列中互质的数对的数目。（询问不超过2e5）

 

Solution:

   容斥原理。

   可以预处理每个数的约数，记录cnt[x],当前数列中有多少个x的倍数。

　然后利用容斥计算出删除或加入这个数对答案产生的影响。

 

 

 

 

---

 

 

Solution：

　　图论。

　　由于题目已经保证有解。需要注意到这个保证具体有哪些性质。

　　可以发现只有同一行或者同一列的点能互相影响，包括间接在同一行列的。

     那么可以针对行和列建图，根据行列给结点标号，需要放鱼的点变成边。

     这样能够互相影响的点的集合就连通了。下面只需要对边染色。

     这样的一个连通的图中中，需要满足任意点连接的边不同颜色的边的差小于等于1.

 　 如果把不同颜色的边当成一个点的出边和入边，问题就变成了找这个图的欧拉路了。