先分析下此题题意：
需要我们实现的操作：
单点修改序列元素
查询某个区间内 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$
2 条评论