• 左区间内的数目

• 右区间内的数目

• 跨区间的数目

$\sf\color{red}\large\text{维护前缀 gcd、后缀 gcd。}$

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



#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 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()
{
for(ri i=1; i<=n; i++)
{
}
build(1,1,n);
for(ri i=1; i<=m; i++)
{
if(opt==1)
{
modify(1,1,n,l,r);
}
else
{
printf("%lld\n",query(1,1,n,l,r).val);
}
}
}


#### first_fan

Just Do It,But Not Just Do It.

### 2 条评论

23333~

#### first_fan · 2019年5月22日 11:28 下午

谢谢~我会继续努力为 MiNa! 做贡献！