HDU 5398 GCD Tree

桃扇骨 2022-08-04 05:26 156阅读 0赞

这题可以基本说是LCT的模板题目，几乎没什么多余的考虑。不像HDU 5333，那题除了用LCT维护最大生成树之外还有一些复杂的公式推算。  
对于多组数据，从1枚举到n，然后加入他向因子连的所有边，使用LCT维护最大生成树即可。  
因子连边不知道随机顺序地连边能不能过，但是可以证明的是，如果现在枚举到i，那么往i最大的约数连边一定没有环，所以可以直接连边。然后也可以觉得（这个是我YY的），往小的约数连边是一定成环的，所以要维护最大生成树。

时间复杂度O(nlog2n)。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define root 1,1,n
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=100010;
    const int MAXE=2000005;
    
    struct Edge
    {
        int to, from;
        Edge () {}
        Edge ( int to , int from) : to (to) , from (from) {}
    } ;
    
    struct Node* null ;
    
    struct Node
    {
        Node* c[2] ;
        Node* f ;
        bool flip ;
        int minv , val ;
        int eidx , idx ;
        void newnode ( int v , int i )
        {
            c[0] = c[1] = f = null ;
            minv = val = v ;
            eidx = idx = i ;
            flip = 0 ;
        }
        void rev ()
        {
            if ( this == null ) return ;
            swap ( c[0] , c[1] ) ;
            flip ^= 1 ;
        }
        void up ()
        {
            if ( this == null ) return ;
            if ( val <= c[0]->minv && val <= c[1]->minv )
            {
                minv = val ;
                eidx = idx ;
            }
            else if ( c[0]->minv <= c[1]->minv && c[0]->minv <= val )
            {
                minv = c[0]->minv ;
                eidx = c[0]->eidx ;
            }
            else
            {
                minv = c[1]->minv ;
                eidx = c[1]->eidx ;
            }
        }
        void down ()
        {
            if ( this == null ) return ;
            if ( flip )
            {
                c[0]->rev () ;
                c[1]->rev () ;
                flip = 0 ;
            }
        }
        bool is_root ()
        {
            return f == null || f->c[0] != this && f->c[1] != this ;
        }
        void sign_down ()
        {
            if ( !is_root () ) f->sign_down () ;
            down () ;
        }
        void setc ( Node* o , int d )
        {
            c[d] = o ;
            o->f = this ;
        }
        void rot ( int d )
        {
            Node* p = f ;
            Node* g = f->f ;
            p->setc ( c[d] , !d ) ;
            if ( !p->is_root () ) g->setc ( this , f == g->c[1] ) ;
            else f = g ;
            setc ( p , d ) ;
            p->up () ;
        }
        void splay ()
        {
            sign_down () ;
            while ( !is_root () )
            {
                if ( f->is_root () ) rot ( this == f->c[0] ) ;
                else
                {
                    if ( f == f->f->c[0] )
                    {
                        if ( this == f->c[0] ) f->rot ( 1 ) , rot ( 1 ) ;
                        else rot ( 0 ) , rot ( 1 ) ;
                    }
                    else
                    {
                        if ( this == f->c[1] ) f->rot ( 0 ) , rot ( 0 ) ;
                        else rot ( 1 ) , rot ( 0 ) ;
                    }
                }
            }
            up () ;
        }
        void access ()
        {
            Node* o = this ;
            for ( Node* x = null ; o != null ; x = o , o = o->f )
            {
                o->splay () ;
                o->setc ( x , 1 ) ;
                o->up () ;
            }
            splay () ;
        }
        void make_root ()
        {
            access () ;
            rev () ;
        }
        void link ( Node* o )
        {
            make_root () ;
            f = o ;
        }
        void cut ()
        {
            access () ;
            c[0] = c[0]->f = null ;
            up () ;
        }
        void cut ( Node* o )
        {
            make_root () ;
            o->cut () ;
        }
        int get_min ( Node* o )
        {
            make_root () ;
            o->access () ;
            return o->eidx ;
        }
    } ;
    
    Node pool[MAXN+MAXE];
    Node* cur;
    Node* node[MAXN];
    Node* edge[MAXE];
    
    Edge E[MAXE+MAXN];
    
    int U[MAXE],V[MAXE];
    int n,idx;
    ll ans;
    ll dp[MAXN];
    
    vector<int> g[MAXN];
    
    void init(int n)
    {
        idx=0,ans=0;
        cur=pool;
        cur->newnode(INF,-1);
        null=cur++;
        for(int i=1;i<=n;i++)
        {
            cur->newnode(INF,-1);
            node[i]=cur++;
        }
    }
    
    void addedge(int u,int v)
    {
        int eidx=node[u]->get_min(node[v]);
        if(E[eidx].from >= u) return;
        U[idx]=u;
        V[idx]=v;
        cur->newnode(u,idx);
        edge[idx]=cur;
        E[idx]=Edge(v,u);
        edge[eidx]->cut(node[U[eidx]]);
        edge[eidx]->cut(node[V[eidx]]);
        edge[idx]->link(node[u]);
        edge[idx]->link(node[v]);
        ans+=u-E[eidx].from;
        idx++;cur++;
    }
    
    void init()
    {
        init(100000);
        for(int i=2;i<=100000;i++)
        {
            g[i].pb(1); 
            for(int j=i+i;j<=100000;j+=i)
                g[j].pb(i);
        }
    
        int sz;
        for(int i=2;i<=100000;i++)
        {
            sz=g[i].size();
            U[idx]=g[i][sz-1];
            V[idx]=i;
            cur->newnode(g[i][sz-1],idx);
            edge[idx]=cur;
            E[idx]=Edge(i,g[i][sz-1]);
            edge[idx]->link(node[g[i][sz-1]]);
            edge[idx]->link(node[i]);
            ans+=g[i][sz-1];
            idx++;cur++;
            for(int j=sz-2;j>=0;j--)
                addedge(g[i][j],i);
            dp[i]=ans;
        }
    }
    
    int main()
    {
        init();
        int m;
        while(~scanf("%d",&m))
            printf("%lld\n",dp[m]);
        return 0;
    }

贴上杜教的标程，简直比我短到不知道哪里去了  
杜教的写法似乎是枚举到i，先向1连边，这样i就在生成树上了，之后无论怎么连边都有环，就可以用LCT维护最大生成树了。

#include <cstdlib>
    #include <cctype>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <iostream>
    #include <sstream>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <fstream>
    #include <numeric>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stdexcept>
    #include <functional>
    #include <utility>
    #include <ctime>
    #include <cassert>
    #include <complex>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define ACCU accumulate
    #define TWO(x) (1<<(x))
    #define TWOL(x) (1ll<<(x))
    #define clr(a) memset(a,0,sizeof(a))
    #define POSIN(x,y) (0<=(x)&&(x)<n&&0<=(y)&&(y)<m)
    #define PRINTC(x) cout<<"Case #"<<++__<<": "<<x<<endl 
    #define POP(x) (__builtin_popcount(x))
    #define POPL(x) (__builtin_popcountll(x))
    typedef vector<int> VI;
    typedef vector<string> VS;
    typedef vector<double> VD;
    typedef long long ll;
    typedef long double LD;
    typedef pair<int,int> PII;
    typedef pair<ll,ll> PLL;
    typedef vector<ll> VL;
    typedef vector<PII> VPII;
    typedef complex<double> CD;
    const int inf=0x20202020;
    const ll mod=1000000007;
    const double eps=1e-9;
    const double pi=3.1415926535897932384626;
    const int DX[]={
       1,0,-1,0},DY[]={
       0,1,0,-1};
    ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){
       if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;for(;b;b>>=1){
       if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    // head
    
    const int N=101000;
    
    struct node {
        node *s[2],*f;
        int val,d;
        bool rev;
        bool isr() { return !f||(f->s[0]!=this && f->s[1]!=this);}
        bool dir() { return f->s[1]==this;}
        void setc(node *c,int d) { s[d]=c;if (c) c->f=this;}
        void push() {
            if (rev) { swap(s[0],s[1]); rep(i,0,2) if (s[i]) s[i]->rev^=1;} rev=0;
        }
        void upd() {
            val=d;
            rep(i,0,2) if (s[i]&&s[i]->val<val) val=s[i]->val;
        }
    }pool[N],*cur;
    stack<node*> sta;
    void rot(node *x) {
        node *p=x->f;bool d=x->dir();
        if (!p->isr()) p->f->setc(x,p->dir()); else x->f=p->f;
        p->setc(x->s[!d],d);x->setc(p,!d);
        p->upd();
    }
    void splay(node *x) {
        node *q=x;
        while (1) { sta.push(q);if (q->isr()) break; q=q->f; }
        while (!sta.empty()) sta.top()->push(),sta.pop();
        while (!x->isr()) {
            if (x->f->isr()) rot(x);
            else if (x->isr()==x->f->isr()) rot(x->f),rot(x);
            else rot(x),rot(x);
        }
        x->upd();
    }
    node *expose(node *x) {
        node *q=NULL;
        for (;x;x=x->f) splay(x),x->s[1]=q,(q=x)->upd();
        return q;
    }
    void evert(node *x) { expose(x); splay(x); x->rev^=1; x->push();}
    void expose(node *x,node *y) { evert(x); expose(y); splay(x);}
    void link(node *x,node *y) { evert(x); evert(y); x->setc(y,1);}
    void cut(node *x,node *y) { expose(x,y); x->s[1]=y->f=NULL;}
    
    const int R=100000;
    int ans,ret[N],n;
    VI d[N];
    int main() {
        for (int i=2;i<=R;i++) for (int j=i+i;j<=R;j+=i) d[j].pb(i);
        for (int i=1;i<=R;i++) {
            pool[i].d=pool[i].val=i;
        }
        for (int i=2;i<=R;i++) {
            link(pool+i,pool+1); ans+=1;
            per(j,0,SZ(d[i])) {
                int v=d[i][j];
                expose(pool+i,pool+v);
                int u=pool[i].val;
                if (u>=v) continue;
                ans=ans-u+v;
                splay(pool+u);
                if (pool[u].s[0]) pool[u].s[0]->f=NULL,pool[u].s[0]=NULL;
                else if (pool[u].s[1]) pool[u].s[1]->f=NULL,pool[u].s[1]=NULL;
                else assert(0);
                link(pool+i,pool+v);
            }
            ret[i]=ans;
        }
        while (scanf("%d",&n)!=EOF) {
            printf("%d\n",ret[n]);
        }
    }