P4435

nullqtr_pwp · 2023-08-18 22:46:11 · 题解

题意：单点修改；给定区间，查询有多少子区间的 \gcd>1。

考虑只查询一次。这种子序列计数问题容易想到分治。

设当前递归到 [l,r]，设要找的是有多少满足条件的 [L,R]\in[l,r]。我们只需要计数跨区间的（因为 L,R 都在一个区间的可以递归求解），即 L\in [l,mid],R\in(mid,r] 的数量。

注意到 \text{gcd} 是单调不增的。可以对左区间算后缀 \gcd 和，右区间算前缀 \gcd 和。注意到这两个的单调性，可以双指针求，具体就是右指针在 mid+1 往右扫，左指针在 l 往右扫。可以 O(len) 求解，其中 len 是区间的长度。结合分治的复杂度是 O(n\log n)。

考虑拓展到线段树上。因为线段树本身就是分治的结构，我们可以考虑对每个线段树的节点维护前缀 \gcd 和与后缀 \gcd 和以及该区间的答案，这样具有可合并性，这些左子的信息和右子的信息可以合并得到该节点的答案，符合线段树的信息可合并性。

但是直接莽会寄，因为直接维护前缀和，后缀和的时空复杂度都是爆的。注意到前缀和，后缀和的更新方式是 \gcd，注意到 a\ne b 时有 \gcd(a,b)\leq \lfloor\dfrac{a}{2}\rfloor（不妨设 a\ge b），因此 \gcd 和的种类数是 \log A 的（A 是值域，对这个结论的解释是每次至少减半），所以我们可以维护前缀后缀和的种类以及出现的位置，方便计算答案。

具体就是用若干个 pair<int,int>，分别描述该位置上 \gcd 和的值和第一次出现这个值的位置。而对于一个节点，最多会有 \min(r-l+1,\log A) 个。

然后直接线段树维护这些前缀 \gcd 和，后缀 \gcd 和，区间答案即可。唯一的难点就是合并信息。这个的话就是先继承左子和右子的答案，然后使用双指针计算跨区间的 [L,R]。然后更新前缀 \gcd 和，后缀 \gcd 和就好了。

总时间复杂度 O(n\log n\log A)。

// Problem: P4435 [COCI2017-2018#2] Garaža
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4435
// Memory Limit: 500 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define mx3(a,b,c) ((a>b?a:b)>c?(a>b?a:b):c)
#define mn3(a,b,c) ((a<b?a:b)<c?(a<b?a:b):c)
#define infll 1e16
#define inf 1e9
#define pii pair<int,int>
#define F(i,a,b) for(int i=a;i<=(b);i++)
#define dF(i,a,b) for(int i=a;i>=(b);i--)
#define wh(lzm) while(lzm--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define vi vector<int>
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
const int mod=998244353,maxn=114514;
#define ls (o<<1)
#define rs (o<<1|1)
struct seg{
    vector<pii>pre,suf;
    int l,r;
    ll v;
}t[maxn<<2];
int n,k,lzm;
seg pushup(seg a,seg b){
    if(!a.pre.size()) return b;
    if(!b.pre.size()) return a;
    if(b.l<a.l) swap(a,b);
    seg rt;
    rt.l=a.l,rt.r=b.r;
    rt.v=a.v+b.v;
    int as=a.suf.size(),bp=b.pre.size();
    int ap=a.pre.size(),bs=b.suf.size();
    rt.pre=a.pre,rt.suf=b.suf;
    int now=a.pre[ap-1].fi;
    for(pii i:b.pre){
        int tt=__gcd(now,i.fi);
        if(tt<now) rt.pre.eb(tt,i.se);
        now=tt;
    }
    now=b.suf[bs-1].fi;
    for(pii i:a.suf){
        int tt=__gcd(now,i.fi);
        if(tt<now) rt.suf.eb(tt,i.se);
        now=tt;
    }
    int j=-1;
    dF(i,as-1,0){
        pii now=a.suf[i];
        int len;
        if(i==as-1) len=now.se-a.l+1;
        else len=now.se-a.suf[i+1].se;
        for(;j<bp-1&&__gcd(b.pre[j+1].fi,now.fi)>1;++j);    
        if(j==-1) continue;
        ll ad;
        if(j==bp-1) ad=1ll*len*(b.r-b.l+1);
        else ad=1ll*len*(b.pre[j+1].se-b.l);
        rt.v+=ad;
    }
    return rt;
}
void update(int o,int l,int r,int pos,int x){
    if(l==r){
        if(x>1) t[o].v=1;
        else t[o].v=0;
        t[o].suf.clear(),t[o].pre.clear();
        pii add=make_pair(x,pos);
        t[o].pre.pb(add);
        t[o].suf.pb(add);
        t[o].l=t[o].r=l;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(ls,l,mid,pos,x);
    else update(rs,mid+1,r,pos,x);
    t[o]=pushup(t[ls],t[rs]);
}
seg query(int o,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r) return t[o];
    int mid=(l+r)>>1;
    if(qr<=mid) return query(ls,l,mid,ql,qr);
    if(ql>mid) return query(rs,mid+1,r,ql,qr);
    return pushup(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
}
int a[maxn];
void build(int o,int l,int r){
    t[o].l=l,t[o].r=r;
    if(l==r){
        int x=a[l];
        if(x>1) t[o].v=1;
        else t[o].v=0;
        t[o].suf.clear(),t[o].pre.clear();
        pii add=make_pair(x,l);
        t[o].pre.pb(add);
        t[o].suf.pb(add);
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[o]=pushup(t[ls],t[rs]);
}
signed main(){
    n=read(),lzm=read();
    F(i,1,n) a[i]=read();
    build(1,1,n);
    wh(lzm){
        int op=read(),l=read(),r=read();
        if(op==1) update(1,1,n,l,r);
        else printf("%lld\n",query(1,1,n,l,r).v);
    }
}

附一句，这题双倍经验 CF1004F。