BZOJ 3672 [NOI2014]购票 (凸优化+树剖/树分治)

题目大意：

略题面传送门

怎么看也是一道$duliu$题= =

先推式子，设$dp[x]$表示到达$x$点到达1节点的最小花费

设$y$是$x$的一个祖先，则$dp[x]=min(dp[y]+(dis[x]-dis[y])*p[x]+q[x])$，且$dis[x]-dis[y] \leq lim[x]$

猜也能猜出来是斜率优化

展开，$dp[y]=p[x]*dis[y]\;+dp[x]-dis[x]*p[x]+q[x]$

此外，$dis$在上述式子中作为一次函数$y=kx+b$的$x$项，且$dis$保证在$1$节点到某点的链上递增，这个性质会很有用

接下来的问题就是如何构造凸包了

方案一：无脑的树剖

把树上的点按照$dis$从小到大排序，依次处理

用树剖+线段树维护可持久化凸包，每次询问都取出能用于转移的那些凸包。

斜率$p$并不单调，那么每次切凸包都要二分

而有了$lim[i]$的限制，我们不能保证所有的祖先节点都能用于转移，倍增跳到最远的合法祖先

树剖，线段树，二分凸包，$O(nlog^{3}n)$，这三个$log$理论上都跑不满，实测跑得确实挺快的。想卡树剖放下述两个方法过也没那么容易

考试的时候还犹豫什么当然是写树剖啦

 #include <map>

 #include <queue>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 201000

 #define ll long long

 #define dd double

 #define inf 23333333333333333ll

 #define it map<node,int>::iterator

 using namespace std;

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int n,T;

 struct Edge{

 int to[N1<<],nxt[N1<<],head[N1],cte;ll val[N1<<];

 void ae(int u,int v,ll w)

 {

     cte++;to[cte]=v,val[cte]=w;

     nxt[cte]=head[u],head[u]=cte;

 }

 }e;

 struct SEG{

 int cvh[][N1];

 int TP[N1<<]; ll *X,*Y;

 void build(int l,int r,int rt,int dep)

 {

     TP[rt]=l-;

     if(l==r) return;

     int mid=(l+r)>>;

     build(l,mid,rt<<,dep+);

     build(mid+,r,rt<<|,dep+);

 }

 void push(int *c,int l,int &tp,int id)

 {

     while(tp>l&&(1.0*Y[id]-1.0*Y[c[tp-]])/(1.0*X[id]-1.0*X[c[tp-]])<=(1.0*Y[c[tp]]-1.0*Y[c[tp-]])/(1.0*X[c[tp]]-1.0*X[c[tp-]]))

         tp--;

     c[++tp]=id;

 }

 ll cut(int *c,int l,int &tp,ll K)

 {

     if(tp<l) return inf;

     if(l==tp) return Y[c[tp]]-K*X[c[tp]];

     int r=tp,ans=l,mid; l++;

     while(l<=r)

     {

         mid=(l+r)>>;

         if((1.0*Y[c[mid]]-1.0*Y[c[mid-]])/(1.0*X[c[mid]]-1.0*X[c[mid-]])<=1.0*K) ans=mid,l=mid+;

         else r=mid-;

     }

     return Y[c[ans]]-K*X[c[ans]];

 }

 void update(int x,int l,int r,int rt,int id,int dep)

 {

     push(cvh[dep],l,TP[rt],id);

     if(l==r) return; int mid=(l+r)>>;

     if(x<=mid) update(x,l,mid,rt<<,id,dep+);

     else update(x,mid+,r,rt<<|,id,dep+);

 }

 ll query(int L,int R,int l,int r,int rt,ll K,int dep)

 {

     if(L<=l&&r<=R) return cut(cvh[dep],l,TP[rt],K);

     int mid=(l+r)>>; ll ans=inf;

     if(L<=mid) ans=min(ans,query(L,R,l,mid,rt<<,K,dep+));

     if(R>mid) ans=min(ans,query(L,R,mid+,r,rt<<|,K,dep+));

     return ans;

 }

 }s;

 ll P[N1],Q[N1],L[N1],f[N1],dis[N1];

 int lg[N1];

 namespace tr{

 int st[N1],ed[N1],id[N1],tot,ff[N1][];

 int dep[N1],fa[N1],tp[N1],son[N1],sz[N1];

 void dfs1(int u,int dad)

 {

     sz[u]=; ff[u][]=u;

     for(int j=e.head[u];j;j=e.nxt[j])

     {

         int v=e.to[j]; if(v==dad) continue;

         dis[v]=dis[u]+e.val[j]; dep[v]=dep[u]+;

         fa[v]=u; ff[v][]=u; dfs1(v,u);

         sz[u]+=sz[v]; if(sz[v]>sz[son[u]]) son[u]=v;

     }

 }

 void dfs2(int u)

 {

     st[u]=++tot; id[tot]=u;

     if(son[u]) tp[son[u]]=tp[u],dfs2(son[u]);

     for(int j=e.head[u];j;j=e.nxt[j])

     {

         int v=e.to[j];

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

         tp[v]=v; dfs2(v);

     }

     ed[u]=tot;

 }

 void init()

 {

     int i,j; s.build(,n,,);

     s.X=dis,s.Y=f; s.update(,,n,,,);

     dfs1(,-); tp[]=; dfs2();

     for(j=;j<=lg[n]+;j++)

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

             ff[i][j]=ff[ ff[i][j-] ][j-];

 }

 void solve(int x)

 {

     int y=x,j,z; f[x]=inf;

     while(dis[x]-dis[tp[y]]<=L[x]&&y)

         f[x]=min(f[x],s.query(st[tp[y]],st[y],,n,,P[x],)),y=fa[tp[y]];

     if(y&&dis[x]-dis[y]<=L[x])

     {

         for(z=y,j=lg[dep[y]]+;j>=;j--)

             if(dis[x]-dis[ff[z][j]]<=L[x]) z=ff[z][j];

         f[x]=min(f[x],s.query(st[z],st[y],,n,,P[x],));

     }

     f[x]+=dis[x]*P[x]+Q[x];

     s.update(st[x],,n,,x,);

 }

 };

 int id[N1];

 int cmp(int x,int y){return dis[x]<dis[y];}

 int main()

 {

     //freopen("t2.in","r",stdin);

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

     int i,x; ll w;

     scanf("%d%d",&n,&T);

     for(lg[]=,i=;i<=n;i++) lg[i]=lg[i>>]+;

     for(id[]=,i=;i<=n;i++)

     {

         scanf("%d%lld%lld%lld%lld",&x,&w,&P[i],&Q[i],&L[i]);

         e.ae(x,i,w); id[i]=i; //e.ae(i,x,w);

     }

     tr::init();

     sort(id+,id+n+,cmp);

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

         tr::solve(id[i]);

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

         printf("%lld\n",f[i]);

     return ;

 }

方案二：有点玄学的点分治

假如把我们这个问题放到序列上会发生什么？

嗯，变成了一道$CDQ$分治题

那$CDQ$上树会发生什么？

它变成了点分治

请忽略上述沙雕分析

$CDQ$的思想是递归左区间，然后处理左区间对右区间的影响，再递归右区间

很好，那么序列上分“左右”的方法是取$mid$，树上的方法变成了找重心

假设我们现在找到了一个重心$x$，它到$1$节点的路径上所有点，都可能对$x$的所有子树(除了包含$1$节点的子树)产生影响

而$1$到$x$的链上还有一些点没有取到最优解

所以需要在包含$1$节点的子树继续递归

而$x$节点的信息也需要用于转移，所以我们要把$x$的其他子树砍掉，然后把$x$节点加入到包含$1$节点的那个子树里去递归

递归求得$1$到$x$链上每个节点的最优解后，处理这个链上每个点对其他子树内节点的影响

其他节点能取到的最小深度是$dis[x]-lim[x]$

我们要避免从凸包内删除节点的尴尬情况

利用一个性质，$dis$在$1$到$x$的链上一定是递增的

所以，把其他节点按照$dis[x]-lim[x]$从大到小排序

每遍历到一个节点$x$，就把链上深度较大的节点$y$依次加入凸包，直到不满足$dis[x]-lim[x]<=dis[y]$

由于点是按$x$轴从右往左加进去的，我们实际想要维护的是一个下凸包，所以要写成维护上凸包的形式

接下来要继续递归其他子树了

我们已经处理过了$1$到$x$这条链对其他子树的影响了

所以只需要处理某子树最靠近$1$节点的节点到某颗子树重心这条链对该子树的影响即可

然后把上述操作中的 $1$节点换成该子树最靠近$1$节点的节点就行了

我写得很恶心，应该是我代码能力太弱的原因qwq

 #include <queue>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 201000

 #define ll long long

 #define dd double

 #define inf 0x3f3f3f3f3f3f3f3fll

 using namespace std;

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int n,T;

 struct Edge{

 int to[N1<<],nxt[N1<<],head[N1],cte;ll val[N1<<];

 void ae(int u,int v,ll w)

 {

     cte++;to[cte]=v,val[cte]=w;

     nxt[cte]=head[u],head[u]=cte;

 }

 }e;

 ll P[N1],Q[N1],lim[N1],f[N1],dis[N1]; ll *X,*Y;

 int tsz,G,sz[N1],use[N1],fa[N1],ms[N1];

 int q[N1],qe,s[N1],se,stk[N1],tp,instk[N1];

 void gsz(int u,int dad)

 {

     sz[u]=;

     for(int j=e.head[u];j;j=e.nxt[j])

     {

         int v=e.to[j]; if(v==dad||use[v]||instk[v]) continue;

         gsz(v,u);

         sz[u]+=sz[v];

     }

 }

 void gra(int u,int dad)

 {

     ms[u]=;

     for(int j=e.head[u];j;j=e.nxt[j])

     {

         int v=e.to[j]; if(v==dad||use[v]||instk[v]) continue;

         gra(v,u);

         ms[u]=max(ms[u],sz[v]);

     }

     ms[u]=max(ms[u],tsz-sz[u]);

     if(ms[u]<ms[G]) G=u;

 }

 int cmp(int x,int y){return dis[x]-lim[x]>dis[y]-lim[y];}

 int que[N1],fr[N1],hd,tl;

 void bfs(int u,int dad)

 {

     int x; hd=tl=; que[]=u; fr[u]=dad;

     while(hd<=tl)

     {

         x=que[hd++]; q[++qe]=x;

         for(int j=e.head[x];j;j=e.nxt[j])

             if(!use[e.to[j]]&&e.to[j]!=fr[x])

                 que[++tl]=e.to[j],fr[e.to[j]]=x;

     }

 }

 void calc(int u,int rt)

 {

     int x=u,y,i,j,v,l,r,ans,mid;

     while(x!=rt) s[++se]=x,x=fa[x]; s[++se]=rt;

     for(j=e.head[u];j;j=e.nxt[j])

     {

         v=e.to[j]; if(use[v]||v==fa[u]) continue;

         bfs(v,u);

     }

     sort(q+,q+qe+,cmp);

     for(i=,j=;j<=qe;j++)

     {

         x=q[j];

         for(;i<=se&&dis[x]-lim[x]<=dis[s[i]];i++)

         {

             y=s[i];

             if(dis[x]-lim[x]<=dis[y])

             {

                 while(tp>&&(1.0*Y[y]-1.0*Y[stk[tp-]])/(1.0*X[y]-1.0*X[stk[tp-]])>=(1.0*Y[stk[tp]]-1.0*Y[stk[tp-]])/(1.0*X[stk[tp]]-1.0*X[stk[tp-]]))

                     tp--;

                 stk[++tp]=y;

             }

         }

         if(!tp) continue;

         l=,r=tp-,ans=tp;

         while(l<=r)

         {

             mid=(l+r)>>;

             if((1.0*Y[stk[mid]]-1.0*Y[stk[mid+]])/(1.0*X[stk[mid]]-1.0*X[stk[mid+]])<=1.0*P[x]) ans=mid,r=mid-;

             else l=mid+;

         }

         f[x]=min(f[x],f[stk[ans]]+(dis[x]-dis[stk[ans]])*P[x]+Q[x]);

     }

     tp=,qe=,se=;

 }

 vector<int>tmp[N1];

 void main_dfs(int u,int rt)

 {

     int j,v; use[u]=; gsz(u,-); instk[u]=;

     if(!use[fa[u]]&&u!=rt)

     {

         for(j=e.head[u];j;j=e.nxt[j])

         {

             v=e.to[j]; if(use[v]||v==fa[u]) continue;

             tmp[u].push_back(v); use[v]=;

         }

         v=fa[u]; tsz=sz[v]; G=; gra(v,-); use[u]=;

         main_dfs(G,rt);

         for(j=;j<tmp[u].size();j++)

         {

             v=tmp[u][j];

             use[v]=;

         }

         tmp[u].clear();

         use[u]=;

     }

     calc(u,rt);

     for(j=e.head[u];j;j=e.nxt[j])

     {

         v=e.to[j]; if(use[v]||instk[v]||v==fa[u]) continue;

         G=; tsz=sz[v]; gra(v,-);

         main_dfs(G,v);

     }

     instk[u]=;

 }

 void pre_dfs(int u)

 {

     for(int j=e.head[u];j;j=e.nxt[j])

     {

         int v=e.to[j]; if(v==fa[u]) continue;

         dis[v]=dis[u]+e.val[j]; pre_dfs(v);

     }

 }

 int main()

 {

     int i,x; ll w;

     scanf("%d%d",&n,&T);

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

     {

         scanf("%d%lld%lld%lld%lld",&fa[i],&w,&P[i],&Q[i],&lim[i]);

         e.ae(fa[i],i,w); e.ae(i,fa[i],w);

     }

     X=dis,Y=f; pre_dfs();

     memset(f,0x3f,sizeof(f)); f[]=;

     tsz=ms[]=n; G=; gsz(,-); gra(,-);

     main_dfs(G,);

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

         printf("%lld\n",f[i]);

     return ;

 }

方案三：二进制分组？？

一会再看

凸包不建议用$vector$维护，开$logn$层数组，线段树内每个位置都记录凸包的开头结尾指针

另外叉积会爆$longlong$，$double$精度足够

巴特西

BZOJ 3672 [NOI2014]购票 (凸优化+树剖/树分治)

方案一：无脑的树剖

方案二：有点玄学的点分治

方案三：二进制分组？？

最新文章

热门文章