The sum of gcd(モチーム:メンテナンス区間GCD和)

31809 ワード

原題:http://acm.hdu.edu.cn/showproblem.php?pid=5381
タイトル:
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はクエリー区間を維持することができます.
詳細手順:
  • 現在の前処理iを右端とするすべての区間をvr[i]に入れ、pairで保存し、firstをgcd値、secondを最後(最も左)のgcdをこの値のpos
  • とする.
  • まずpush_back {a[i],i}
  • はvr[i-1]を遍歴している.vr[i-1]に格納されているのも同じgcd区間の情報であるため、iが直接接続すれば
  • である.
  • は、gcdが同一であると仮定すると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]); } } }