编程题：线段树+双指针扫描
最近，斯拉夫科一直在研究自然数序列。如果序列中所有元素的最大公约数大于$$1$$，他会发现一个有趣的序列。
昨天，他在车库里发现了一个由$$N$$个自然数组成的序列。由于他真的很无聊，他决定通过问一些简单的问题来让自己保持忙碌。每个查询可以是以下两种类型之一：
$$1.$$将序列中$$X$$位置的值更改为$$V$$。
$$2.$$确定序列间隔$$[L，R]$$中包含的感兴趣的连续子阵列的数量。
### 输入格式:
输入的第一行包含数字$$N$$和$$Q (1≤N, Q≤105)$$，分别表示序列中的元素数和查询数。
下一行包含$$N$$个自然数$$A_{i} (1≤A_{i}|≤10^{9})$$，代表初始序列中的数字。
以下$$Q$$行中的每一行都包含以下形式的查询：
* 行中的第一个数字可以是$$1$$或$$2$$，表示查询的类型。
* 如果查询类型为$$1$$，则任务中会出现两个数字：$$X (1 ≤ X ≤ N)$$和$$V (1 ≤ V≤ 109)$$。
* 如果查询类型为$$2$$，则后面跟着两个数字：$$L$$和$$R (1 ≤ L ≤ R ≤ N)$$，它们表示左右间隔边界。
### 输出格式:
对于每个类型$$2$$的查询，输出任务中感兴趣的连续子数组的数量。
### 输入样例1:
in
5 1
8 4 3 9 1
2 2 5
### 输出样例1:
out
4
### 输入样例2:
in
5 3
2 3 6 4 1
2 1 4
1 3 1
2 3 5
### 输出样例2:
out
6
1
### 输入样例3:
in
4 3
2 2 2 2
2 1 4
1 2 3
2 1 4
### 输出样例3:
out
10
5
答案：若无答案欢迎评论
昨天，他在车库里发现了一个由$$N$$个自然数组成的序列。由于他真的很无聊，他决定通过问一些简单的问题来让自己保持忙碌。每个查询可以是以下两种类型之一：
$$1.$$将序列中$$X$$位置的值更改为$$V$$。
$$2.$$确定序列间隔$$[L，R]$$中包含的感兴趣的连续子阵列的数量。
### 输入格式:
输入的第一行包含数字$$N$$和$$Q (1≤N, Q≤105)$$，分别表示序列中的元素数和查询数。
下一行包含$$N$$个自然数$$A_{i} (1≤A_{i}|≤10^{9})$$，代表初始序列中的数字。
以下$$Q$$行中的每一行都包含以下形式的查询：
* 行中的第一个数字可以是$$1$$或$$2$$，表示查询的类型。
* 如果查询类型为$$1$$，则任务中会出现两个数字：$$X (1 ≤ X ≤ N)$$和$$V (1 ≤ V≤ 109)$$。
* 如果查询类型为$$2$$，则后面跟着两个数字：$$L$$和$$R (1 ≤ L ≤ R ≤ N)$$，它们表示左右间隔边界。
### 输出格式:
对于每个类型$$2$$的查询，输出任务中感兴趣的连续子数组的数量。
### 输入样例1:
in
5 1
8 4 3 9 1
2 2 5
### 输出样例1:
out
4
### 输入样例2:
in
5 3
2 3 6 4 1
2 1 4
1 3 1
2 3 5
### 输出样例2:
out
6
1
### 输入样例3:
in
4 3
2 2 2 2
2 1 4
1 2 3
2 1 4
### 输出样例3:
out
10
5
答案：若无答案欢迎评论
