Codeforces Round 969 (Div. 1) C. Eri and Expanded Sets（线段树维护差分数组gcd+双指针+尺取）

题目

转化一下题意就是，

给定一个n(n<=4e5)，代表数组a的长度，

求有多少区间，满足区间内两两差分后得到的新数组的gcd，除去所有2的因子后∈{0,1}

实际t(t<=1e4)组样例，保证sumn不超过4e5

思路来源

乱搞ac+jiangly代码

题解

一个重要的性质是，

区间内从小到大排好序相邻两项两两差分的gcd，等于区间内不排序相邻两项两两差分的gcd

补充一下证明：

只需证交换相邻两个的时候成立即可，

交换两个的时候会影响到差分数组的两个数，

不妨 a b c d，交换b和c，有a c b d，

显然gcd(b-a,c-b,d-c)=gcd(c-a,c-b,d-b)

以下的代码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的段就是区间内所有值都相同的段，尺取即可

学弟问了下为什么是gcd，cf题解也没解释，想了比较久，想出一个构造

以下函数，返回gcd除尽所有因子2之后的值，并且能和操作一一对应

def f(x,y):
    if x<y: 
        return f(y,x)
    if y%2==0:
         return f(x,y/2)
    if x%2==0:
          return f(x/2,y)
    if x==y:
         return x
    return f((x+y)/2-y,y)

这个函数的意思就是，如果有能除以2的优先除以2，

否则说明两段是奇数的，一定能取中点，继续递归下去，

比如0 3 10，差分之后是3 7，

你可以操作0和10生成一个5，使之变成3 2 5，

那这个(x+y)/2-y就是这个2，f(3,7)递归下去是f(3,2)，

俩数遇到2的因子就不断除以2，肯定还可以让set里这两段相邻，

递归下去就是gcd除去所有2的因子之后的值了

代码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].v
	void 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].v
	void 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<=n
    int 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;
}