CF1019E Raining season

╰半夏微凉° 2021-11-13 15:36 206阅读 0赞

[CF1019E Raining season][CF1019E_Raining season]

[题解][Link 1]

码农题：边分治+闵可夫斯基和

发现，每一条路径是一个ax+b的一次函数形式

最暴力的想法是：

把所有的路径拿出来，贡献给每个t

发现，其实是这些直线的半平面交（从上往下看能看到的直线）

考虑能不能不n^2

各种取max，合并，覆盖，都可以减少不必要的枚举

本题，考虑边分治

考虑所有经过当前中心边的路径

但是半平面交无法合并，所以用到一个结论：半平面交和凸包对偶：ax+b->(a,b)求上凸壳即可。

因为，凸壳可以合并！

所以，左边求出来，右边求出来，合并即可。恰好ax+b+cx+d=(a+c,b+d)

闵可夫斯基和：

这样，总点数是O(nlogn)的，最后所有可能贡献的点再求一个凸包，

答案，就是用-x去切凸包，最大化斜率

单指针扫一下即可。

注意：

vis数组4倍

闵可夫斯基和是n+m-1步！！！！（调了2h）

代码：

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    #define pii pair<int,int>
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    namespace Modulo{
    const int mod=998244353;
    int ad(int x,int y){
        return (x+y)>=mod?x+y-mod:x+y;}
    void inc(int &x,int y){x=ad(x,y);}
    int mul(int x,int y){
        return (ll)x*y%mod;}
    void inc2(int &x,int y){x=mul(x,y);}
    int qm(int x,int y=mod-2){
        int ret=1;while(y){
        if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}
    }
    //using namespace Modulo;
    namespace Miracle{
    const int N=100000+5;
    const int inf=0x3f3f3f3f;
    int n,m;
    struct node{
        int nxt,to;
        ll a,b;
        node(){}
        node(ll aa,ll bb,int y){
            a=aa;b=bb;to=y;nxt=0;
        }
    }e[4*N];
    vector<node>to[N];
    int hd[2*N],cnt=1;
    void add(int x,int y,int a,int b){
        // cout<<" link "<<x<<" "<<y<<endl;
        e[++cnt].nxt=hd[x];
        e[cnt].a=a;e[cnt].b=b;
        e[cnt].to=y;hd[x]=cnt;
    
        e[++cnt].nxt=hd[y];
        e[cnt].a=a;e[cnt].b=b;
        e[cnt].to=x;hd[y]=cnt;
    }
    int rt;
    int sz[2*N],nowsz;
    
    struct po{
        ll x,y;
        po(){}
        po(ll xx,ll yy){
            x=xx;y=yy;
        }
        po friend operator -(po a,po b){
            return po(a.x-b.x,a.y-b.y);
        }
        po friend operator +(po a,po b){
            return po(a.x+b.x,a.y+b.y);
        }
        bool friend operator <(po a,po b){
            if(a.x!=b.x) return a.x<b.x;
            return a.y<b.y;
        }
        void op(){
            cout<<"("<<x<<","<<y<<") ";
        }
    }p[2][2*N],q[2*N*20],tmp[2*N];
    int num[2],size;
    long double cross(po a,po b){
        return (long double)a.x*b.y-(long double)a.y*b.x;
    }
    void build(po *f,int &n){
        int nc=0;
        sort(f+1,f+n+1);
        for(reg i=1;i<=n;++i){
            if(!nc) tmp[++nc]=f[i];
            else{
                while(nc>1&&cross(f[i]-tmp[nc],f[i]-tmp[nc-1])<=0) --nc;
                tmp[++nc]=f[i];
            }
        }
        for(reg i=1;i<=nc;++i) f[i]=tmp[i];
        n=nc;
    }
    void merge(po *f,int n,po *g,int m){
        //add to q
        //min ke fu si ji sum
        int pf=1,pg=1;
        for(reg i=1;i<=n+m-1;++i){
            q[++size]=(f[pf]+g[pg]);
            if(pf==n) ++pg;
            else if(pg==m) ++pf;
            else{
                long double cha=cross(f[pf]+g[pg+1]-q[size],f[pf+1]+g[pg]-q[size]);
                if(cha<=0) ++pg;
                else ++pf;
            }
        }
    }
    bool vis[4*N];//bian!!!
    int mi;
    void dfs(int x,int fa){
        //warning!! n is 2*n!!!!
        sz[x]=1;
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(y==fa||vis[i]) continue;
            dfs(y,x);
            if(max(sz[y],nowsz-sz[y])<mi){
                mi=max(sz[y],nowsz-sz[y]);
                rt=i;
            }
            sz[x]+=sz[y];
        }
    }
    void dfs2(int x,int fa,ll a,ll b,int tp){
        //warning!! n is 2*n!!!!
        sz[x]=1;
        p[tp][++num[tp]]=po(a,b);
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(y==fa||vis[i]) continue;
            dfs2(y,x,a+e[i].a,b+e[i].b,tp);
            sz[x]+=sz[y];
        }
    }
    void divi(int x){
        //warning!! n is 2*n!!!!
        // cout<<" divi ---------------------- "<<x<<endl;
        if(nowsz==1) return;
        rt=0;mi=inf;
        dfs(x,0);
        num[0]=num[1]=0;
        vis[rt]=vis[rt^1]=1;
        int le=e[rt].to,ri=e[rt^1].to;
    
        // cout<<" after "<<" le "<<le<<" ri "<<ri<<endl;
        dfs2(le,0,0,0,0);
        dfs2(ri,0,e[rt].a,e[rt].b,1);
        // cout<<" before build le "<<endl;
        // for(reg i=1;i<=num[0];++i){
        //     p[0][i].op();
        // }puts("");
        
        build(p[0],num[0]);
        // cout<<" after le "<<endl;
        // for(reg i=1;i<=num[0];++i){
        //     p[0][i].op();
        // }puts("");
    
        // cout<<" before build ri "<<endl;
        // for(reg i=1;i<=num[1];++i){
        //     p[1][i].op();
        // }puts("");
        
        build(p[1],num[1]);
        // cout<<" after ri "<<endl;
        // for(reg i=1;i<=num[1];++i){
        //     p[1][i].op();
        // }puts("");
        merge(p[0],num[0],p[1],num[1]);
    
    
        nowsz=sz[le];
        divi(le);
        nowsz=sz[ri];
        divi(ri);
    }
    void pre(int x,int fa){
        int las=x;
        for(solid i:to[x]){
            int y=i.to;
            if(y==fa) continue;
            ++n;
            add(las,n,0,0);
            add(n,y,i.a,i.b);
            las=n;
            pre(y,x);
        }
    }
    int main(){
        rd(n);rd(m);
        int x,y,a,b;
        for(reg i=1;i<n;++i){
            rd(x);rd(y);rd(a);rd(b);
            to[x].pb(node(a,b,y));
            to[y].pb(node(a,b,x));
        }
        pre(1,0);
        nowsz=n;
        divi(1);
    
        build(q,size);
        int ptr=1;
        for(reg i=0;i<=m-1;++i){
            while(ptr!=size&&(q[ptr+1].x*i+q[ptr+1].y)>(q[ptr].x*i+q[ptr].y)){
                ++ptr;
            }
            ll ans=q[ptr].x*i+q[ptr].y;
            ot(ans);
        }
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

其实挺套路的吧，，

路径太多，考虑覆盖一些东西。

半平面交转凸壳，这个是合并的前提，然后就边分治了。

转载于:https://www.cnblogs.com/Miracevin/p/10987795.html

[CF1019E_Raining season]: https://www.luogu.org/problemnew/show/CF1019E
[Link 1]: https://www.luogu.org/blog/litble-blog/solution-cf1019e