【bzoj2402】陶陶的难题II

Portal -->bzoj2402

Solution

　　这题的话，看到答案的形式想到分数规划（Portal -->【learning】)

　　套路一波，记当前二分的\(mid\)为\(\lambda'\)，那么其实就是要快速判断：

\[\begin{aligned}
&(y_i+q_j)-\lambda'(x_i+p_j)\\
=&(y_i-\lambda' x_i)+(q_j-\lambda' p_j)
\end{aligned}
\]

　　的最大值与\(0\)的大小关系

　　上面的这个式子虽然说与\(i\)和\(j\)有关，但是两个部分的形式是完全一样并且相互不影响的，可以看成一个函数\(g\)，那么对于每次询问我们只要求出\(x\)到\(y\)路径上的\(g\)然后找最大值和次大值加起来就好了

　　求\(x\)到\(y\)路径上的信息我们可以考虑用树链剖分，接下来的问题就是怎么求一条重链中所有点的\(g\)的最大值

　　观察\(g\)的形式：

\[\begin{aligned}
g(i)&=y_i-\lambda'x_i\\
y_i&=\lambda'x_i+g(i)
\end{aligned}
\]

　　那其实可以转化成一个这样的问题：求斜率为\(\lambda'\)且过\((x_i,y_i)\)的直线的截距的最大值

　　容易得出结论最优的\((x_i,y_i)\)一定是在上凸壳上的

　　那所以我们考虑对于树剖中的线段树的每一个区间，分别维护这个区间中的点对应的\((x_i,y_i)\)和\((q_i,p_i)\)的上凸壳，查询的话直接在上凸壳上二分就好了

　　

　　一些需要注意的地方：

1、在查询二分的时候，由于题目没有保证任意两个点的\(x，y，p，q\)不相同，所以不能直接用除法，而是应该移下项用乘法判断

2、额如果是用vector存凸包的话。。在求凸包的时候。。要注意下标是从\(0\)开始的！\(0\)开始的！\(0\)开始的！嗯。。

3、然后我的叉积好像写的有点丑了不过！不管了qwq

　　代码大概长这样

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

#define Pr pair<double,double>

#define mp make_pair

using namespace std;

const int N=1e5+10,SEG=N*4,inf=2147483647;

const double eps=1e-5;

struct xxx{

    int y,nxt;

}a[N*2];

double val[N][4];

int h[N],top[N],son[N],sz[N],pre[N],dep[N];

int lis[N],dfn[N];

int n,m,tot,dfn_t;

void update(Pr &ret,Pr data);

void add(int x,int y);

void dfs1(int fa,int x,int d);

void dfs2(int fa,int x);

bool check(int x,int y,double k);

void solve(int x,int y);

struct Hull{/*{{{*/

    vector<Pr> a;

    void insert(double x,double y){a.push_back(mp(x,y));}

    double chaji(Pr x,Pr y){return x.first*y.second-x.second*y.first;}

    void build(){

        sort(a.begin(),a.end());

        vector<Pr> st;

        st.clear();

        int top=0;

        for (int i=0;i<a.size();++i){

            while (top>1&&chaji(mp(a[i].first-st[top-2].first,a[i].second-st[top-2].second),mp(st[top-1].first-st[top-2].first,st[top-1].second-st[top-2].second))<0)

            //!!因为是从0开始的所以st的下标都要-1

                --top,st.pop_back();

            ++top; st.push_back(a[i]);

        }

        a=st;

        a.resize(top);

    }

    double query(double k){

        int l=0,r=a.size()-1,mid;

        while (l<r){

            mid=l+r>>1;

            if (a[mid+1].second-a[mid].second<=k*(a[mid+1].first-a[mid].first)) r=mid;

            else l=mid+1;

        }

        return a[l].second-k*a[l].first;

    }

    void debug(){

        for (int i=0;i<a.size();++i) printf("%.2lf %.2lf\n",a[i].first,a[i].second);

    }

};/*}}}*/

namespace Seg{/*{{{*/

    int ch[SEG][2];

    Hull info[SEG][2];

    int n,tot;

    void _build(int x,int l,int r){

        int tmp;

        for (int i=l;i<=r;++i){

            tmp=lis[i];

            info[x][0].insert(val[tmp][0],val[tmp][1]);

            info[x][1].insert(val[tmp][2],val[tmp][3]);

        }

        info[x][0].build(); info[x][1].build();

        if (l==r) return;

        int mid=l+r>>1;

        ch[x][0]=++tot; _build(ch[x][0],l,mid);

        ch[x][1]=++tot; _build(ch[x][1],mid+1,r);

    }

    void build(int _n){n=_n; tot=1; _build(1,1,n);}

    Pr _query(int x,int l,int r,int lx,int rx,double k){

        if (l<=lx&&rx<=r){

            return mp(info[x][0].query(k),info[x][1].query(k));

        }

        Pr ret=mp(-inf,-inf);

        int mid=lx+rx>>1;

        if (l<=mid) update(ret,_query(ch[x][0],l,r,lx,mid,k));

        if (r>mid) update(ret,_query(ch[x][1],l,r,mid+1,rx,k));

        return ret;

    }

    Pr query(int l,int r,double k){return _query(1,l,r,1,n,k);}

}/*}}}*/

int main(){

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

#endif

    int x,y;

    scanf("%d",&n);

    for (int j=0;j<4;++j)

        for (int i=1;i<=n;++i)

            scanf("%lf",&val[i][j]);

    memset(h,-1,sizeof(h));

    tot=0;

    for (int i=1;i<n;++i){

        scanf("%d%d",&x,&y);

        add(x,y); add(y,x);

    }

    dfs1(0,1,1);

    top[1]=1; dfn_t=0;

    dfs2(0,1);

    Seg::build(n);

    scanf("%d",&m);

    for (int i=1;i<=m;++i){

        scanf("%d%d",&x,&y);

        solve(x,y);

    }

}

void add(int x,int y){

    a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot;

}

void dfs1(int fa,int x,int d){

    int u;

    son[x]=0; sz[x]=1; pre[x]=fa; dep[x]=d;

    for (int i=h[x];i!=-1;i=a[i].nxt){

        u=a[i].y;

        if (u==fa) continue;

        dfs1(x,u,d+1);

        if (sz[son[x]]<sz[u]) son[x]=u;

        sz[x]+=sz[u];

    }

}

void dfs2(int fa,int x){

    int u;

    dfn[x]=++dfn_t; lis[dfn[x]]=x;

    if (son[x]){

        top[son[x]]=top[x];

        dfs2(x,son[x]);

    }

    for (int i=h[x];i!=-1;i=a[i].nxt){

        u=a[i].y;

        if (u==fa||u==son[x]) continue;

        top[u]=u;

        dfs2(x,u);

    }

}

bool check(int x,int y,double k){

    Pr ret=mp(-inf,-inf);

    while (top[x]!=top[y]){

        if (dep[top[x]]<dep[top[y]]) swap(x,y);

        update(ret,Seg::query(dfn[top[x]],dfn[x],k));

        x=pre[top[x]];

    }

    if (dfn[x]>dfn[y]) swap(x,y);

    update(ret,Seg::query(dfn[x],dfn[y],k));

    return ret.first+ret.second>0;

}

void update(Pr &ret,Pr data){

    ret.first=max(ret.first,data.first);

    ret.second=max(ret.second,data.second);

}

void solve(int x,int y){

    double l=0,r=1e5,mid,ans;

    while (r-l>eps){

        mid=(l+r)*0.5;

        if (check(x,y,mid)) l=mid;

        else r=mid;

    }

    printf("%.4lf\n",l);

}

巴特西

【bzoj2402】陶陶的难题II

Solution

最新文章

热门文章