HDu 5930 GCD(区間gcdの種類線分樹)

7502 ワード

題名リンク参考解答1009
テーマの大意
n個の数,q回のクエリを与え,そのうちの1つの数を修正するたびに,このn個の数からなるすべてのサブ区間のgcdの種類を尋ねた.
に答える
gcdの種類は最大nlogC(Cは数の最大値)個を超えず、私たちはすべて保存することができ、各gcdがどれだけのサブ区間で構成できるかを併存することができます.区間左端点を列挙し,logC個のgcdが変化する右端点を探して種類と個数を計算し,結果をmapで保存する.
単点修正のたびに,修正されるのはxを含む区間のみであり,それぞれxを区間左端点と区間右端点とし,logCを超えない2つのgcdおよび対応する区間集合を求めることができ,暴力合併するとO((logC)2),mapを修正する時間複雑度を加えるとO((logC)2である.×log(n*logC)).
gcdのlogC個の変化の位置を求めることについて、私のやり方は線分の木を使います.xを左端点として、線分木は[x,N]のgcd変化位置を検索し、まず最初の変化位置はxそのものであり、gcd値はA[x]自身であり、gcd値を再帰関数(gcdvと記す)に伝達し、[le,ri]再帰が必要だ.主なコードは次のとおりです.

int query_right(int w,int le,int ri,int &x,int &y,int v[],int pos[],int &cnt,int gcdv)
{                                       // gcdv    [x,le-1]   gcd ，      gcd 
    int mid=(le+ri)>>1;
    if (x<=le && ri<=y)
    {
        if (Tree[w] % gcdv==0) return gcdv;  //  Tree[w] gcdv  ，gcd   
        if (le==ri)                          //       ，      
        {
            gcdv=gcd(gcdv,Tree[w]);
            cnt++;
            v[cnt]=gcdv;
            pos[cnt]=le;
            return gcdv;
        }
        if (Tree[w<<1]%gcdv!=0)
            gcdv=query_right(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
        if (Tree[w<<1|1]%gcdv!=0)
            gcdv=query_right(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
        return gcdv;
    }
    if (mid>=x) 
        gcdv=query_right(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
    if (mid+1<=y) 
        gcdv=query_right(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
    return gcdv;
}

上はxを左端に固定するコードで、xを右端に固定するコードは似ています.変化点を求めても線分の木を二分することができますが、TLEができるかもしれません.
このようにして変化点を求める時間の複雑さはO(logn)である.×logC+logC×logC). 暴力合併左と右の区間の時間複雑度はO((logC)×logC×log(n*logC)).しかし、データがlogC個の変化点に達するのは難しいため、3個のlogの時間が複雑でこの問題を乗り越える効率も非常に高い.2つのlogの効率を追求するには、左と右の区間を統合し、統合後の異なるgcdも同様にlogC個であり、mapの値を更新することができます.(合併してmapを新しく開くことはできますが、必要ない感じがします)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define bll long long
#define dou double
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define rep(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define rek(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define Mem(a,b) memset(a,b,sizeof(a))
#define Cpy(a,b) memcpy(a,b,sizeof(b))
//__builtin_popcountll

using std::sort;
using std::max;
using std::min;
using std::swap;

const int maxn=50000+10;
int N,Q,A[maxn],Tree[maxn*4];
std::map  Map;         //        gcd，      gcd     

int gcd(int a,int b)
{
    while(b)
    {
        int c=a%b;
        a=b,b=c;
    }
    return a;
}

void maketree(int w,int le,int ri)      //      
{
    if (le==ri)
    {
        Tree[w]=A[le];
        return ;
    }
    int mid=(le+ri)>>1;
    maketree(w<<1,le,mid);
    maketree(w<<1|1,mid+1,ri);
    Tree[w]=gcd(Tree[w<<1],Tree[w<<1|1]);
}

void modify(int w,int le,int ri,int &x,int &v)    //     
{
    if (le>x || ri>1;
    modify(w<<1,le,mid,x,v);
    modify(w<<1|1,mid+1,ri,x,v);
    Tree[w]=gcd(Tree[w<<1],Tree[w<<1|1]);
}

int query_right(int w,int le,int ri,int &x,int &y,int v[],int pos[],int &cnt,int gcdv)
{                                       // gcdv    [x,le-1]   gcd ，      gcd 
    int mid=(le+ri)>>1;
    if (x<=le && ri<=y)
    {
        if (Tree[w] % gcdv==0) return gcdv;  //  Tree[w] gcdv  ，gcd   
        if (le==ri)                          //       ，      
        {
            gcdv=gcd(gcdv,Tree[w]);
            cnt++;
            v[cnt]=gcdv;
            pos[cnt]=le;
            return gcdv;
        }
        if (Tree[w<<1]%gcdv!=0)
            gcdv=query_right(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
        if (Tree[w<<1|1]%gcdv!=0)
            gcdv=query_right(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
        return gcdv;
    }
    if (mid>=x) 
        gcdv=query_right(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
    if (mid+1<=y) 
        gcdv=query_right(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
    return gcdv;
}

int query_left(int w,int le,int ri,int &x,int &y,int v[],int pos[],int &cnt,int gcdv)
{                                   //    gcd，      gcd        (  )
    int mid=(le+ri)>>1;
    if (x<=le && ri<=y)
    {
        if (Tree[w] % gcdv==0) return gcdv;
        if (le==ri)
        {
            gcdv=gcd(gcdv,Tree[w]);
            cnt++;
            v[cnt]=gcdv;
            pos[cnt]=le;
            return gcdv;
        }
        if (Tree[w<<1|1]%gcdv!=0)
            gcdv=query_left(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
        if (Tree[w<<1]%gcdv!=0)
            gcdv=query_left(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
        return gcdv;
    }
    if (mid+1<=y) 
        gcdv=query_left(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
    if (mid>=x) 
        gcdv=query_left(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
    return gcdv;
}

void get_right(int w,int v[],int pos[],int &cnt) //       w，    w-N gcd    
{
    v[cnt=1]=A[w];
    pos[cnt]=w;
    int gcdv=A[w];
    query_right(1,1,N,w,N,v,pos,cnt,gcdv);
    pos[cnt+1]=N+1;
}

void get_left(int w,int v[],int pos[],int &cnt) //      w，    1-w gcd    
{
    v[cnt=1]=A[w];
    pos[cnt]=w;
    int gcdv=A[w];
    int x=1;
    query_left(1,1,N,x,w,v,pos,cnt,gcdv);
    pos[cnt+1]=0;
}

void add(int gcdv,bll gcdnum)       //   Map
{
    Map[gcdv]+=gcdnum;
    if (Map[gcdv]==0) Map.erase(gcdv);
}

void Prepare()                      //    
{
    static int cnt,v[50],pos[50];
    maketree(1,1,N);
    Map.clear();
    For(i,1,N)
    {
        get_right(i,v,pos,cnt);
        For(j,1,cnt)
            add(v[j],pos[j+1]-pos[j]);
    }
}

void solve(int v[2][50],int p[2][50],int cnt[2],int d)  //        gcd，   
{
    For(i,1,cnt[0])
        For(j,1,cnt[1])
        {
            int gcdv=gcd(v[0][i],v[1][j]);
            long long g=(bll)abs(p[0][i]-p[0][i+1])*abs(p[1][j]-p[1][j+1]);
            add(gcdv,g*d);
        }
}

void printt()                  //     ，    
{
    std::map :: iterator it;
    for (it=Map.begin(); it!=Map.end(); it++)
        printf("%d %lld
",it->first,it->second);
    printf("---
");
}

int Done(int x,int rr)          //       
{
    static int cnt[2],v[2][50],p[2][50];
    get_left(x,v[0],p[0],cnt[0]);
    get_right(x,v[1],p[1],cnt[1]);
    solve(v,p,cnt,-1);
    A[x]=rr;
    modify(1,1,N,x,rr);
    get_left(x,v[0],p[0],cnt[0]);
    get_right(x,v[1],p[1],cnt[1]);
    solve(v,p,cnt,1);
    return (int)Map.size();     // Map     gcd     
}

int main(int argc, char* argv[])
{
    int zz=0;
    scanf("%d",&zz);
    For(test,1,zz)
    {
        printf("Case #%d:
",test);
        scanf("%d%d",&N,&Q);
        For(i,1,N) scanf("%d",&A[i]);
        Prepare();
        For(i,1,Q)
        {
            int x,p; scanf("%d%d",&x,&p);
            int ans=Done(x,p);
            printf("%d
",ans);
        }
    }
    return 0;
}

Google Apps Script 現在の日付を取得（スプレッドシート）

homestead php拡張子のインストール