求X-Y之间和p互质的数的和，典型的容斥问题，求和用等差数列求和，注意首项末项是多少。

首先记录下不修改的答案，离线处理，存下询问，输出的时候，遇到一个操作1，就遍历前面的操作，把修改加上去，注意要判重，只保留最后一次修改。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include
       
         using namespace std; typedef long long ll; ll ans; int pri[1234]; int top; int n,m,a,b,c; ll gcd(ll a,ll b) { return a%b==0?b:gcd(b,a%b); } ll cal(ll num) { int x=a; int y=b; int fir; int tmp=y/num-x/num; if(x%num==0) fir=x,tmp++; else fir=num*(x/num+1); if(fir>y) return 0; int en=fir+(tmp-1)*num; return (fir+en)*1ll*tmp/2; } void dfs(int p,ll num,int flag) { if(num>b) return; if(p) {ans+=flag*cal(num);} for(int i=p+1;i
        
         1) pri[top++]=c; dfs(0,1,-1); out[i]=(a+b)*1ll*(b-a+1)/2-ans; } else { scanf("%d%d",&b,&c); d[i][1]=b; d[i][2]=c; } } for(int i=1;i<=m;i++) { if(d[i][0]==1) { ll ans=out[i]; int cnt=0; for(int j=i-1;j>=1;j--) { if(d[j][0]==2&&!vis[d[j][1]]) { vis[d[j][1]]=true; rec[cnt][0]=d[j][1]; rec[cnt][1]=d[j][2]; cnt++; } } for(int j=0;j
         
          =d[i][1]&&rec[j][0]<=d[i][2]) { ans-=( gcd(rec[j][0],d[i][3])==1?rec[j][0]:0 ); ans+=( gcd(rec[j][1],d[i][3])==1?rec[j][1]:0 ); } } printf("%I64d\n",ans); } } } return 0; } /* 123 100 1 1 1 10 11 2 2 3 2 2 5 1 1 10 2 */