- 给定一个长度为(n)的正整数序列。
- (q)次操作，分为两种：单点修改；询问一段区间有多少个(gcd ot=1)的子串。
- (n,qle10^5)
线段树+暴力
考虑用线段树来维护，那么每次合并两个区间时，答案就可以拆成两个区间各自的答案加上跨区间的答案。
要求跨区间的答案，我们只需对每个区间维护一个前缀栈和一个后缀栈，记录所有可能的前缀/后缀(gcd)及出现次数。
由于(gcd)只会越变越小，所以这个栈的大小不超过(log_210^9)。
计算答案的时候只需在左区间的后缀栈中枚举，同时用尺取法在右区间的前缀栈中扫，维护好右区间中能与左区间当前(gcd)配对的前缀大小，乘上左区间当前(gcd)出现次数统计答案。
代码：(O(nlog^2n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define LG 32
#define LL long long
using namespace std;
int n,a[N+5];I int gcd(CI x,CI y) {return y?gcd(y,x%y):x;}
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[30],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('
');}
}using namespace FastIO;
struct Data
{
LL V;int T1,S1[LG],C1[LG],T2,S2[LG],C2[LG];
I Data() {V=T1=T2=0;}I Data(CI v) {V=v!=1,S1[T1=1]=S2[T2=1]=v,C1[1]=C2[1]=1;}
I friend Data operator + (Con Data& A,Con Data& B)//合并
{
RI i,j,g;Data t;t.V=A.V+B.V;//两区间各自答案
for(t.T1=A.T1,i=1;i<=A.T1;++i) t.S1[i]=A.S1[i],t.C1[i]=A.C1[i];//复制左边的前缀栈
for(i=1;i<=B.T1;++i) (g=gcd(t.S1[t.T1],B.S1[i]))^t.S1[t.T1]?(t.S1[++t.T1]=g,t.C1[t.T1]=B.C1[i]):t.C1[t.T1]+=B.C1[i];//把右边前缀栈中的元素加入
for(t.T2=B.T2,i=1;i<=B.T2;++i) t.S2[i]=B.S2[i],t.C2[i]=B.C2[i];//复制右边的后缀栈
for(i=1;i<=A.T2;++i) (g=gcd(t.S2[t.T2],A.S2[i]))^t.S2[t.T2]?(t.S2[++t.T2]=g,t.C2[t.T2]=A.C2[i]):t.C2[t.T2]+=A.C2[i];//把左边后缀栈中的元素加入
RI o=0;for(j=1;j<=B.T1;++j) o+=B.C1[j];//初始移在最右边
for(i=1,j=B.T1;i<=A.T2;t.V+=1LL*A.C2[i++]*o) W(j&&gcd(A.S2[i],B.S1[j])==1) o-=B.C1[j--];return t;//在左区间中枚举，尺取法在右区间中扫
}
}O[N<<2];
class SegmentTree
{
private:
#define PT CI l=1,CI r=n,CI rt=1
#define LT l,mid,rt<<1
#define RT mid+1,r,rt<<1|1
#define PU(x) (V[x]=V[x<<1]+V[x<<1|1])
Data V[N<<2];
public:
I void Bd(PT)//建树
{
if(l==r) return (void)(V[rt]=Data(a[l]));RI mid=l+r>>1;Bd(LT),Bd(RT),PU(rt);
}
I void U(CI x,CI v,PT)//单点修改
{
if(l==r) return (void)(V[rt]=Data(v));RI mid=l+r>>1;x<=mid?U(x,v,LT):U(x,v,RT),PU(rt);
}
I Data Q(CI L,CI R,PT)//区间查询
{
if(L<=l&&r<=R) return V[rt];RI mid=l+r>>1;if(R<=mid) return Q(L,R,LT);
if(L>mid) return Q(L,R,RT);return Q(L,mid,LT)+Q(mid+1,R,RT);
}
}S;
int main()
{
RI Qt,i;for(read(n),read(Qt),i=1;i<=n;++i) read(a[i]);S.Bd();
RI op,x,y;W(Qt--) read(op),read(x),read(y),op==1?S.U(x,y):writeln(S.Q(x,y).V);return clear(),0;
}