NC15557 连续区间的最大公约数
这道题没有修改，只有查询。查询最大公约数还是比较简单的，但是查询子区间的最大公约数也等于整个区间的最大公约数的数量，这就不这么快乐了。假设我们两个孩子区间的 和 他们子区间满足条件的数目
，要合并成父亲区间，父亲区间的
就是对两孩子的
再取一个
，但是满足这个新的
的子区间数目没有办法仅从孩子的
解析出，因为子区间可能是两个孩子区间的一部分,这里我就记这种情况为“中间情况”。所以我们需要在节点中保存更多的信息来维护出“中间情况”。
有一个重要结论，也是做这道题最最关键的一个结论，就是随着区间变长， 一定是不上升的 。也就是说，一个从端点扩展区间的
不可能是中间高两边低的，也不可能是两边高中间低的。那么，我们维护两个向量
，分别表示从区间左端点和右端点向另一端扩展的
变化情况。先给出定义代码：
struct myPair{
ll gcd, len; //扩展长度
};
struct node{
vector<myPair>l,r;
ll noGcdCnt = 0, gcd = 0,len = 0; //不是区间gcd的区间数目，区间gcd，区间长度
}t[maxn<<2]; 先解释 的含义，它的元素类型是我自定义的一个类型。下面的表格可以直观解释它的用法(被牛客打了水印，建议去博客看)：
可以看出 是区间
的
和能维持的长度
，在这个例子中
向量有
个元素;
意义类似,是从右往左进行扩展。得到了从端点向中间扩展的
变化情况，加上一个
变量表示不是这个区间
的区间数目,即区间内部的情况，这三者就可以求出合并后新区间的
。也就是说，我们通过两孩子向量的扩展求出“中间情况”，通过两孩子的
求出在孩子区间内部的其他情况。来分析一下这个合并代码求
的那部分（还有一部分要求合并的向量，先不写），需要用到结构体运算符重载的知识，不会的可以查一下这方面的知识。
node operator+(const node & rr)const{
node fa; //用于返回的合并节点
fa.gcd = Gcd(gcd, rr.gcd); //新区间gcd是两节点的gcd再取gcd
fa.len = len + rr.len; //长度直接加
/*计算noGcdCnt部分：
* ①判断孩子的gcd是否等于父亲的gcd，等于就直接加上原来的noGcdCnt，
* ②否则孩子任何一个子区间的gcd都不可能等于父亲的gcd，因为父亲的gcd一定是最小的，
* 孩子区间的gcd一定大于等于父亲区间的gcd，
* 假如孩子的一个子区间gcd等于父亲的gcd，但是整体的gcd却大于这个子区间，这是不可能的
* 所以直接加上孩子所有子区间的数目，即(len + 1) * len / 2
* */
fa.noGcdCnt += (fa.gcd == gcd) ? noGcdCnt : (len + 1) * len / 2;
fa.noGcdCnt += (fa.gcd == rr.gcd) ? rr.noGcdCnt : (rr.len + 1) * rr.len / 2;
/*计算“中间情况”
* ① tot记录右区间rr从左端点扩展的子区间 和 左区间从右端点扩展的子区间
* 构成的中间区间的gcd不等于父亲gcd的情况下，右区间rr从左端点扩展的子区间长度(耐心理解一下)。
* ②last记录右区间rr的向量l 最后一个满足上述情况的向量下标。
*/
ll tot = rr.len,last = rr.l.size()-1;
//左区间从它的右端点向左扩展
For(i,0,r.size()-1) {
//子区间构成的区间的gcd如果等于父亲的gcd，减去
while(last >= 0 && Gcd(rr.l[last].gcd,r[i].gcd) == fa.gcd ) tot -= rr.l[last--].len;
//否则加上子区间的子区间所有不等于父亲gcd的数目
fa.noGcdCnt += r[i].len * tot;
}
return fa;
} 可能你会不太理解后面怎么计算“中间情况”，为什么不是两个向量同时从中间开始扩展，而是右区间向量一开始就在另一端？原因就是这样可以保证不漏区间的情况下时间复杂度最短。还记得上面那个结论吗？**随着区间变长， 一定是不上升的**。所以如果下面这个条件成立：
Gcd(rr.l[last].gcd,r[i].gcd) == fa.gcd
那么对于所有大于等于 的左区间向量与右区间构成的中间区间
一定等于父亲的
，因为如果不等于的话只有可能是比父亲的
要小，这是不可能的，因为父亲的
已经是最小的了（区间长度最长），而这部分区间我们是要减掉的。所以减掉是正确的，因为后面用不到了。这样时间复杂度就是两个向量的长度和了。
来看一下这个帮了我们大忙的向量是怎么维护出来的,会比刚才维护 好理解。
//父亲先继承左区间的左向量，右区间的右向量
fa.l = l, fa.r = rr.r;
//维护父亲左向量
For(i,0,rr.l.size()-1)
//如果右区间的左向量的一个区间是父亲左向量的倍数（注意谁是谁的倍数），长度延长
if(rr.l[i].gcd % fa.l.back().gcd == 0) fa.l.back().len += rr.l[i].len;
//否则，加入新向量
else fa.l.push_back({Gcd(rr.l[i].gcd, fa.l.back().gcd), rr.l[i].len} );
//维护父亲右向量，类似
For(i,0,r.size()-1)
if(r[i].gcd % fa.r.back().gcd == 0) fa.r.back().len += r[i].len;
else fa.r.push_back({Gcd(r[i].gcd, fa.r.back().gcd), r[i].len} ); 这里就是模拟一下扩展过程就行了，注意延长的条件。
剩下的和普通线段树差不多，没了修改就不需要 和懒标记了。注意我是在建树的时候读入的，查询的时候返回的是一个节点。
:
#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define ls now<<1
#define rs now<<1|1
#define mid (l+r)/2
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef long long ll;
typedef __int128 lll;
const int maxn = 1e5+9;
int n,m,num[maxn];
ll Gcd(ll a,ll b){
if(a == 0) return b;
if(b == 0) return a;
while(b^=a^=b^=a%=b);
return a;
}
struct myPair{
ll gcd, len;
};
struct node{
vector<myPair>l,r;
ll noGcdCnt = 0, gcd = 0,len = 0;//不是区间gcd的区间数目，区间gcd，区间长度
//重载 + 运算符，用于合并本节点（左孩子）和另一个结点rr（右孩子），注意本节点在左边，rr在右边，返回新节点
node operator+(const node & rr)const{
node fa; //用于返回的合并节点
fa.gcd = Gcd(gcd, rr.gcd); //新区间gcd是两节点的gcd再取gcd
fa.len = len + rr.len; //长度直接加
/*计算noGcdCnt部分：
* ①判断孩子的gcd是否等于父亲的gcd，等于就直接加上原来的noGcdCnt，
* ②否则孩子任何一个子区间的gcd都不可能等于父亲的gcd，因为父亲的gcd一定是最小的，
* 孩子区间的gcd一定大于等于父亲区间的gcd，
* 假如孩子的一个子区间gcd等于父亲的gcd，但是整体的gcd却大于这个子区间，这是不可能的
* 所以直接加上孩子所有子区间的数目，即(len + 1) * len / 2
* */
fa.noGcdCnt += (fa.gcd == gcd) ? noGcdCnt : (len + 1) * len / 2;
fa.noGcdCnt += (fa.gcd == rr.gcd) ? rr.noGcdCnt : (rr.len + 1) * rr.len / 2;
/*计算“中间情况”
* ① tot记录右区间rr从左端点扩展的子区间 和 左区间从右端点扩展的子区间
* 构成的中间区间的gcd不等于父亲gcd的情况下，右区间rr从左端点扩展的子区间长度(耐心理解一下)。
* ②last记录右区间rr的向量l 最后一个满足上述情况的向量下标。
*/
ll tot = rr.len,last = rr.l.size()-1;
//左区间从它的右端点向左扩展
For(i,0,r.size()-1) {
//子区间构成的区间的gcd如果等于父亲的gcd，减去
while(last >= 0 && Gcd(rr.l[last].gcd,r[i].gcd) == fa.gcd ) tot -= rr.l[last--].len;
//否则加上子区间的子区间所有不等于父亲gcd的数目
fa.noGcdCnt += r[i].len * tot;
}
//父亲先继承左区间的左向量，右区间的右向量
fa.l = l, fa.r = rr.r;
//维护父亲左向量
For(i,0,rr.l.size()-1)
//如果右区间的左向量的一个区间是父亲左向量的倍数（注意谁是谁的倍数），长度延长
if(rr.l[i].gcd % fa.l.back().gcd == 0) fa.l.back().len += rr.l[i].len;
//否则，加入新向量
else fa.l.push_back({Gcd(rr.l[i].gcd, fa.l.back().gcd), rr.l[i].len} );
//维护父亲右向量，类似
For(i,0,r.size()-1)
if(r[i].gcd % fa.r.back().gcd == 0) fa.r.back().len += r[i].len;
else fa.r.push_back({Gcd(r[i].gcd, fa.r.back().gcd), r[i].len} );
return fa;
}
}t[maxn<<2];
void build(int now,int l,int r){
if(l == r){
t[now].len = 1;
t[now].noGcdCnt = 0;
cin>>t[now].gcd; //从这里读入数据，一个数gcd就是它本身
t[now].l.clear();
t[now].r.clear();
t[now].l.push_back({t[now].gcd,1});t[now].r.push_back({t[now].gcd,1});
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
t[now] = t[ls] + t[rs]; //合并，相当于pushup
}
//注意返回的是一个节点
node query(int now,int l,int r,int x,int y){
if(x <= l&& r <= y ) return t[now];
node lef,rig;
rig.len = lef.len = -1;
if(x <= mid) lef = query(ls,l,mid,x,y);
if(y > mid) rig = query(rs,mid+1,r,x,y);
if(lef.len == -1) return rig; //无左区间
else if(rig.len == -1) return lef; //无右区间
return lef + rig; //左右区间都有，合并
}
int main(){
speedUp_cin_cout
int T,cas=0;int l,r;
cin>>T;
while( T-- ){
cout<<"Case #"<<(++cas)<<":"<<endl;
cin>>n;
build(1,1,n);
cin>>m;
while( m-- ){
cin>>l>>r;
node ans=query(1,1,n,l,r);
//区间左右可能的子区间数 - 不等于gcd的子区间数 = 等于gcd的子区间数
cout<<ans.gcd<<" "<<(1ll * (ans.len + 1) * ans.len / 2 - ans.noGcdCnt)<<endl;
}
}
return 0;
} 
京公网安备 11010502036488号