Codeforces Round 969 (Div. 1) C. Eri and Expanded Sets（线段树维护差分数组gcd+双指针+尺取）
题目
转化一下题意就是，
给定一个n(n<=4e5)，代表数组a的长度，
求有多少区间，满足区间内两两差分后得到的新数组的gcd∈{0,1}
实际t(t<=1e4)组样例，保证sumn不超过4e5
思路来源
乱搞ac+jiangly代码
题解
一个重要的性质是，
区间内从小到大排好序相邻两项两两差分的gcd，等于区间内不排序相邻两项两两差分的gcd
以下的代码1是用了这个性质的，所以直接维护相邻项gcd即可，比较好写
代码2是在权值线段树上强行排了一下序的，非常难写
双指针维护一下，
对于枚举的右端点r，满足区间[l,r]的相邻项差分数组的gcd=1的最靠右的l，
由于gcd只会缩成因子，所以对于所有<=l的位置x，[x,r]的gcd都是等于1的，直接ans+=l
具体代码里是，在[l,r]区间长度不短于2的前提下，试着把当前l往右挪一个，
只要gcd为1的话就可以一直往右挪，否则break，并往左回滚一个
特别地，gcd=0和gcd=1不能放在一起维护，否则不满足双指针的单调性了，所以这里分开统计的
gcd=0的段就是区间内所有值都相同的段，尺取即可
代码1
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=4e5+10;
int t,n,a[N],l,r,kd;
int gcd(int x,int y){return !y?x:gcd(y,x%y);
}
struct segtree{int n;struct node{int l,r,v;}e[N<<2];#define l(p) e[p].l#define r(p) e[p].r#define v(p) e[p].vvoid up(int p){v(p)=gcd(v(p<<1),v(p<<1|1));}void bld(int p,int l,int r){l(p)=l;r(p)=r;v(p)=0;if(l==r){return;}int mid=l+r>>1;bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);up(p);}void init(int _n){n=_n;bld(1,1,n);}void chg(int p,int x,int v){if(l(p)==r(p)){v(p)=v;return;}int mid=l(p)+r(p)>>1;chg(p<<1|(x>mid),x,v);up(p);}bool ok(){int x=v(1);if(!x)return 0;x-=x&(-x);return !x;}
}seg;
int main(){sci(t);while(t--){sci(n);rep(i,1,n){sci(a[i]);}seg.init(n);int l=1;ll ans=0;rep(r,2,n){//gcd=1的区间 满足x<=l的所有[x,r]seg.chg(1,r,abs(a[r]-a[r-1]));if(!seg.ok())continue;while(l+1<r && seg.ok()){seg.chg(1,l+1,0);l++;//printf("l:%d r:%d query:%d\n",l,r,seg.query());}//printf("l:%d r:%d query:%d\n",l,r,seg.query());if(!seg.ok()){seg.chg(1,l,abs(a[l]-a[l-1]));l--;}//printf("l:%d r:%d ok:%1d\n",l,r,seg.ok());ans+=l;}int p=0;rep(r,1,n){//gcd=0的区间 满足所有值都相同的区间if(r==1 || a[r]==a[r-1])p++;else ans+=1ll*p*(p+1)/2,p=1;}ans+=1ll*p*(p+1)/2;printf("%lld\n",ans);}return 0;
}代码2（乱搞ac）
相当于给动态维护的区间[l,r]拍到一棵权值线段树上了，
并且需要维护每种数字出现的个数，和当前出现的数字的种类数，比较繁琐
#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=4e5+10;
int t,n,a[N],b[N],x[N],q[N],c,l,r,kd;
int gcd(int x,int y){return !y?x:gcd(y,x%y);
}
int LG(int n){return std::__lg(n);// int highestBit = 0;// while (n >>= 1) {// highestBit++;// }// return highestBit;
}
struct segtree{int n;struct node{int l,r,v;}e[N<<2];#define l(p) e[p].l#define r(p) e[p].r#define v(p) e[p].vvoid up(int p){v(p)=gcd(v(p<<1),v(p<<1|1));//if(p==1)rep(i,1,17)printf("p:%d v:%d\n",i,v(i));//while(v(p) && v(p)%2==0)v(p)/=2;}void bld(int p,int l,int r){l(p)=l;r(p)=r;//printf("p:%d l:%d r:%d\n",p,l,r);if(l==r){v(p)=0;return;}int mid=l+r>>1;bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);up(p);}void init(int _n){n=_n;bld(1,1,n);}void chg(int p,int x,int v){if(l(p)==r(p)){//if(v==410)printf("vvv");//while(v && v%2==0)v/=2;v(p)=v;return;}int mid=l(p)+r(p)>>1;chg(p<<1|(x>mid),x,v);up(p);}int cnt(int p,int ql,int qr){if(ql<=l(p)&&r(p)<=qr)return v(p);int mid=l(p)+r(p)>>1,res=0;if(ql<=mid)res|=cnt(p<<1,ql,qr);if(qr>mid)res|=cnt(p<<1|1,ql,qr);return res;}bool ok(){int x=v(1);x-=x&(-x);return !x;}int query(){return v(1);}
}seg;
struct BitPre{ // 求前缀和(可改为max等)int n,tr[N];void init(int _n){n=_n;memset(tr,0,(n+1)*sizeof(*tr));}void add(int x,int v){for(int i=x;i<=n;i+=i&-i)tr[i]+=v;}int sum(int x){int ans=0; for(int i=x;i;i-=i&-i)ans+=tr[i];return ans;}int askp(int p){return sum(p)-sum(p-1);}// 树状数组求从小到大第k个, 1<=k<=sum(n), 1<=x<=nint kth(int k){int x=0;for(int i=1<<LG(n);i;i>>=1){if(x+i<=n && k>tr[x+i]){x+=i;k-=tr[x];}}return x+1;}
}tr;
void add(int r){if(!q[b[r]])kd++;q[b[r]]++;//printf("r:%d kd:%d\n",r,kd);//q.insert(r);tr.add(b[r],1);int pre=tr.sum(b[r]-1);if(pre){int w=tr.kth(pre);//if(r==5)printf("r:%d w:%d delta:%d\n",r,w,x[b[r]-1]-x[w-1]);seg.chg(1,b[r],x[b[r]-1]-x[w-1]);}int now=tr.sum(b[r]),all=tr.sum(c);//printf("r:%d now:%d all:%d\n",r,now,all);if(now<all){int w=tr.kth(now+1);//if(r==5)printf("r:%d w:%d delta:%d\n",r,w,x[w-1]-x[b[r]-1]);seg.chg(1,w,x[w-1]-x[b[r]-1]);}
}
void del(int r){q[b[r]]--;if(!q[b[r]])kd--;tr.add(b[r],-1);if(tr.askp(b[r]))return;seg.chg(1,b[r],0);int now=tr.sum(b[r]),all=tr.sum(c);//printf("del r:%d now:%d all:%d\n",r,now,all);if(now<all){int w=tr.kth(now+1);//printf("xw:%d br:%d\n",x[w-1],x[b[r]-1]);if(now){int pre=tr.kth(now);//printf("del l:%d now:%d all:%d w:%d\n",r,now,all,w,pre);seg.chg(1,w,x[w-1]-x[pre-1]);}else{//printf("del l:%d w:%d zero xw:%d\n",r,w,x[w-1]);seg.chg(1,w,0);}}
}
int main(){sci(t);while(t--){sci(n);c=0;kd=0;rep(i,1,n){sci(a[i]);q[i]=0;x[c++]=a[i];}sort(x,x+c);c=unique(x,x+c)-x;rep(i,1,n){b[i]=lower_bound(x,x+c,a[i])-x+1;}//rep(i,0,c-1)printf("i:%d x:%d\n",i+1,x[i]);tr.init(c);seg.init(c);int l=1;ll ans=0;// rep(r,1,n){// vector<int>now;// now.pb(x[b[r]-1]);// per(l,r-1,1){// now.pb(x[b[l]-1]);// sort(now.begin(),now.end());// int g=0,las=now[0];// for(auto &v:now){// g=gcd(g,v-las);// las=v;// }// if(g==0 || g==1){// printf("l:%d r:%d g:%d\n",l,r,g);// break;// }// }// }rep(r,1,n){add(r);//printf("l:%d r:%d query:%d\n",l,r,seg.query());///if(!seg.ok())continue;if(kd==1)continue;//printf("r:%d kd:%d\n",r,kd);if(!seg.ok())continue;while(kd>1 && seg.ok()){del(l);l++;//printf("l:%d r:%d query:%d\n",l,r,seg.query());}//printf("l:%d r:%d query:%d\n",l,r,seg.query());if(kd==1 || !seg.ok())add(--l);//printf("l:%d r:%d query:%d\n",l,r,seg.query());ans+=l;}int p=0;rep(r,1,n){if(r==1 || a[r]==a[r-1])p++;else ans+=1ll*p*(p+1)/2,p=1;}ans+=1ll*p*(p+1)/2;printf("%lld\n",ans);}return 0;
}