【题解】洛谷 P4435 ​​Garaža 前后缀 gcd ——first_fan

先分析下此题题意：

需要我们实现的操作：

单点修改序列元素

查询某个区间内 gcd 非 1 的子串数目

我们考虑用线段树维护区间内答案个数。

那么一个区间的所求数目即由 $\sf\large\text{三部分}$组成：

• 左区间内的数目

• 右区间内的数目

• 跨区间的数目

那么只要知道怎么求跨区间的就简单了。

首先跨区间的子串不是个个都有用，只有 gcd 非 1 的才有贡献

考虑怎么记录跨区间的、gcd 非 1 的子串数目：
$\sf\color{red}\large\text{维护前缀 gcd、后缀 gcd。}$

可以用数组或 pair 记录 gcd 的值和数量，为了节约空间，此处用 vector 套 pair 记录。

另建一个 pair 用于存储 r 区间前缀的 gcd 数即可。

后缀同理。

怎么用上述信息求跨区数量？

枚举左区间后缀以及右区间前缀

枚举过程中右移左区间后缀时右区间也会右移或不变（单调右移）。

接下来双指针完成即可。

本题唯一的难点就是向上更新的操作，其余的更改、查询操作都十分常规，另外如果看 first 或 second 不爽可以用两个数组代替 pair。

#include<bits/stdc++.h>
#define ri unsigned register ll
#define ll long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define leaf (l==r)
using namespace std;
const ll maxn=1e6+7;

ll read()
{
    ll x=0;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}

ll a[maxn];

struct segment_tree
{
    ll l;
    ll r;
    ll val;
    vector<pair<int,int> > pre;//前缀
    vector<pair<int,int> > sub;//后缀
} seg[maxn];

segment_tree pushup(segment_tree l,segment_tree r)//向上更新
{
    segment_tree nd;
    nd.l=l.l;
    nd.r=nd.r;
    nd.pre.clear();
    nd.sub.clear();
    for(ri i=0; i<l.pre.size(); i++)
    {
        nd.pre.push_back(l.pre[i]);
    }
    for(ri i=l.pre.size(); i<l.pre.size()+r.pre.size(); i++)
    {
        ll res=__gcd(l.pre[l.pre.size()-1].first,r.pre[i-l.pre.size()].first);
        if(nd.pre[nd.pre.size()-1].first==res)
        {
            nd.pre[nd.pre.size()-1].second+=r.pre[i-l.pre.size()].second;
        }
        else
        {
            nd.pre.push_back(make_pair(res,r.pre[i-l.pre.size()].second));
        }
    }
    for(ri i=0; i<r.sub.size(); i++)
    {
        nd.sub.push_back(r.sub[i]);
    }
    for(ri i=r.sub.size(); i<l.sub.size()+r.sub.size(); i++)
    {
        ll res=__gcd(r.sub[r.sub.size()-1].first,l.sub[i-r.sub.size()].first);
        if(nd.sub[nd.sub.size()-1].first==res)
        {
            nd.sub[nd.sub.size()-1].second+=l.sub[i-r.sub.size()].second;
        }
        else
        {
            nd.sub.push_back(make_pair(res,l.sub[i-r.sub.size()].second));
        }
    }
    nd.val=l.val+r.val;
    ll cur1=l.sub.size()-1;
    ll cur2=0;//双指针
    ll len=l.sub[0].second;
    ll lw=0;
    bool flg=0;
    while(1)
    {
        int gcd=flg?cur2-1:cur2;
        while(cur1>=0&&__gcd(l.sub[cur1].first,r.pre[gcd].first)==1)
        {
            cur1--;
            flg=0;
        }
        if(cur1<0)
        {
            break;
        }
        if(flg)
        {
            cur1--;
        }
        len=l.sub[cur1].second;
        while((unsigned)cur2+1<=r.pre.size()&&__gcd(r.pre[cur2].first,l.sub[cur1].first)!=1)
        {
            lw+=r.pre[cur2].second;
            cur2++;
        }
        if(__gcd(l.sub[cur1].first,r.pre[cur2-1].first)!=1)
        {
            nd.val+=len*lw;
        }
        if(cur1<=0)
        {
            break;
        }
        flg=1;
    }
    return nd;
}//two pointer 完成
void build(ll nd,ll l,ll r)//建树
{
    if(leaf)
    {
        seg[nd].pre.push_back(make_pair(a[l],1));
        seg[nd].sub.push_back(make_pair(a[l],1));
        seg[nd].val=a[l]==1?0:1;
        seg[nd].l=seg[nd].r=l;
        return;
    }
    ll mid=(l+r)>>1;
    build(ls(nd),l,mid);
    build(rs(nd),mid+1,r);
    seg[nd]=pushup(seg[ls(nd)],seg[rs(nd)]);
}
void modify(ll nd,ll l,ll r,ll pos,ll val)//单点修改
{
    if(leaf)
    {
        seg[nd].pre.clear();
        seg[nd].sub.clear();
        seg[nd].pre.push_back(make_pair(val,1));
        seg[nd].sub.push_back(make_pair(val,1));
        seg[nd].val=val==1?0:1;
        return;
    }
    ll mid=(l+r)>>1;
    if(pos<=mid)
    {
    modify(ls(nd),l,mid,pos,val);
    }
    else
    {
        modify(rs(nd),mid+1,r,pos,val);
    }
    seg[nd]=pushup(seg[ls(nd)],seg[rs(nd)]);
}
segment_tree query(ll nd,ll l,ll r,ll L,ll R)//区间统计，大写为所问区间，小写为当前区间
{
    if(L<=l&&R>=r)
    {
        return seg[nd];
    }
    ll mid=(l+r)>>1;
    segment_tree a,b;
    bool flgl=0;
    bool flgr=0;
    if(L<=mid)
    {
        a=query(ls(nd),l,mid,L,R);
        flgl=1;
    }
    if(R>mid)
    {
        b=query(rs(nd),mid+1,r,L,R);
        flgr=1;
    }
    if(flgl&&flgr)
    {
        return pushup(a,b);
    }
    return flgl?a:b;
}

unsigned ll n,m;
//代码中的这些有关 unsigned 的声明是因为消除 warning，可以忽略。

int main()
{
    n=read();
    m=read();
    for(ri i=1; i<=n; i++)
    {
        a[i]=read();
    }
    build(1,1,n);
    for(ri i=1; i<=m; i++)
    {
        ll opt=read();
        ll l=read();
        ll r=read();
        if(opt==1)
        {
            modify(1,1,n,l,r);
        }
        else
        {
            printf("%lld\n",query(1,1,n,l,r).val);
        }
    }
}

调试调了很久，可能是由于递归调用频繁，并不能防止部分 TLE，但是经过吸氧还是可以过的。

猜测一下：如果手写 vector 并使用数组代替 pair，gcd 函数也自己写的话，应当能省下很多的调用时间。$\sf\Huge OwO$