The sum of gcd(モチーム:メンテナンス区間GCD和)
原題:http://acm.hdu.edu.cn/showproblem.php?pid=5381
タイトル:
n配列,q回クエリ,l,rをクエリするたびに,lからrまでのすべてのサブ区間のgcdと出力
解析:
まずモウ隊で、並べ替えて問い合わせました.次の質問は質問区間を維持する問題です.現在のクエリが
これは
このような複数の区間のgcd値はlogn種の可能性のみであり,区間が長くなるにつれて減少することは明らかである.では、
詳細手順:現在の前処理iを右端とするすべての区間をvr[i]に入れ、pairで保存し、firstをgcd値、secondを最後(最も左)のgcdをこの値のpos とする.まず はvr[i-1]を遍歴している.vr[i-1]に格納されているのも同じgcd区間の情報であるため、iが直接接続すれば である.は、gcdが同一であると仮定すると が変化する.前処理結果使用可能コードの注釈セクション を参照
タイトル:
n配列,q回クエリ,l,rをクエリするたびに,lからrまでのすべてのサブ区間のgcdと出力
解析:
まずモウ隊で、並べ替えて問い合わせました.次の質問は質問区間を維持する問題です.現在のクエリが
l~r-1
であると仮定し、l~r
に拡張する必要があります.では,a[r]のl~r
という区間への寄与,すなわちgcd(l~r)+gcd(l+1~r)+gcd(l+2~r)...gcd(r~r)
を算出する.これは
O(logn)
で処理する必要がありますこのような複数の区間のgcd値はlogn種の可能性のみであり,区間が長くなるにつれて減少することは明らかである.では、
i
を右端とする区間のgcdの可能性を前処理して位置を記録するだけで、lognはクエリー区間を維持することができます.詳細手順:
push_back {a[i],i}
second
(位置)が変化し、異なるとpush_back {gcd,pos}
#include
using namespace std;
#define LL long long
int Len;
struct node{
int l,r,id;
bool operator<(const node &a)const{
return l/Len<a.l/Len||l/Len==a.l/Len&&r<a.r;
}
}e[10009];
int a[10009];
int l,r;LL now;
typedef pair<int,int> pill;
vector<pill>vl[10009],vr[10009];
void init(int n){
for(int i=0;i<=n;i++)vl[i].clear(),vr[i].clear();
for(int i=1;i<=n;i++){
int gcd=a[i];
vr[i].push_back({a[i],i});//gcd pos
vector<pill>&pre=vr[i-1];
for(int j=0;j<pre.size();j++){
int v=pre[j].first,pos=pre[j].second;
gcd=__gcd(gcd,v);
if(gcd==vr[i].back().first){
vr[i].back().second=pos;
}
else{
vr[i].push_back({gcd,pos});
}
}
}
//for(int i=1;i<=n;i++){printf("%d : ",i); for(int j=0;j
//,vr[i][j].first,vr[i][j].second);}printf("
"); }printf("
");
for(int i=n;i>=1;i--){
int gcd=a[i];
vl[i].push_back({a[i],i});//gcd pos
vector<pill>&pre=vl[i+1];
for(int j=0;j<pre.size();j++){
int v=pre[j].first,pos=pre[j].second;
gcd=__gcd(gcd,v);
if(gcd==vl[i].back().first){
vl[i].back().second=pos;
}
else{
vl[i].push_back({gcd,pos});
}
}
}
//for(int i=1;i<=n;i++){printf("%d : ",i);for(int j=0;j
//,vl[i][j].first,vl[i][j].second); }printf("
");}printf("
");
}
void upl(int x,int f){//l to r
LL sum=0;
vector<pill>&V=vl[l];
for(int i=0;i<V.size();i++){
int v=V[i].first,p=V[i].second,pp=l-1;
if(i)pp=V[i-1].second;
if(p<=r){
sum+=(LL)(p-pp)*v;
}
else{
sum+=(LL)(r-pp)*v;
break;
}
}
now+=sum*f;
}
void upr(int x,int f){//r to l
LL sum=0;
vector<pill>&V=vr[r];
for(int i=0;i<V.size();i++){
int v=V[i].first,p=V[i].second,pp=r+1;
if(i)pp=V[i-1].second;
if(p>=l){
sum+=(LL)(pp-p)*v;
}
else{
sum+=(LL)(pp-l)*v;
break;
}
}
now+=sum*f;
}
LL ans[10009];
int main(){
int t;scanf("%d",&t);
while(t--){
int n,q;
scanf("%d",&n);
Len=int(sqrt(n)+0.5);
for(int i=1;i<=n;i++)scanf("%d",a+i);
init(n);
scanf("%d",&q);
for(int i=1;i<=q;i++){
e[i].id=i;
scanf("%d%d",&e[i].l,&e[i].r);
}
sort(e+1,e+1+q);
l=e[1].l,r=e[1].l-1;
now=0;
for(int i=1;i<=q;i++){
while(r<e[i].r)r++,upr(r,1);
while(l>e[i].l)l--,upl(l,1);
while(r>e[i].r)upr(r,-1),r--;
while(l<e[i].l)upl(l,-1),l++;
ans[e[i].id]=now;
}
for(int i=1;i<=q;i++){
printf("%lld
",ans[i]);
}
}
}