题解：P9704 「TFOI R1」Tree Home

· · 题解

怎么没有分块的题解啊，我来补一篇。

前排提醒：本题分块代码极长，但速度奇快，跑出了当前最优解（我也不知道为什么）。

题目传送门

算法分析

这个式子乍眼一看非常复杂，然而我们本着明知山有虎偏向虎山行的精神去面对他：

\begin{aligned} f(a,b,c)&=(a-b)\times[a^2+b^2+ab+3c(a+b+c)]\\ f(d_i-d_r,d_j-d_r,d_r)&=(d_i-d_j)\times[d_i^2+d_j^2-2d_id_r-2d_jd_r+2d_r^2+d_id_j\\ &-d_id_r-d_jd_r+d_r^2+3d_r(d_i+d_j-d_r)]\\ &=(d_i-d_j)[d_i^2+d_j^2+d_id_j]\\ &=d_i^3-d_j^3\\ |f(d_i-d_r,d_j-d_r,d_r)|+|v_i-v_j|&=|d_i^3-d_j^3|+|v_i-v_j| \end{aligned}

原来就是纸老虎罢了。所以我们要求上面那个东西的最大值。然而我不会曼哈顿距离所以直接暴力枚举。

|d_i^3-d_j^3|+|v_i-v_j|=\begin{cases} (d_i^3+v_i)-(d_j^3+v_j)&d_i\ge d_j,v_i\ge v_j\\ (d_i^3-v_i)-(d_j^3-v_j)&d_i\ge d_j,v_i<v_j\\ (d_j^3-v_j)-(d_i^3-v_i)&d_i<d_j,v_i\ge v_j\\ (d_j^3+v_j)-(d_i^3+v_i)&d_i<d_j,v_i<v_j \end{cases}

上四式均在前一项最大，后一项最小时取最大值，答案即为其中最大的那一个。
所以我们要预处理 (d_i^3+v_i) 和 (d_i^3-v_i) 的区间最值，问题转化为 RMQ 问题。
这里使用动态数组建树和常规分块，共 \sqrt{n} 块，预处理 O(\sqrt{n}^2)，期望查询 m 次为 O(m)，最坏退化到 O(m\sqrt{n})，可以 AC 本题。

Code

由于要处理四个数据，本题的分块代码很长（虽然大部分都是复制粘贴罢了）。建议有能力的优先使用 ST 表或线段树。

#include<bits/stdc++.h>
#define ll long long
#define mp(a,b) make_pair(a,b)
#define _1 first
#define _2 second
#define ppp pair<pair<ll,ll>,pair<ll,ll> >
using namespace std;
int n,T,v[200005],d[200005],Z,U,V,W,l,r,L,R;
//n，T，v[i]，d[i]：如题；Z：分块数量；U，V，W：建树用；l，r，L，R：询问用 
ll q[4][450][450],h[4][450][450],z[4][450][450],an[2][200005];
//q[0/1/2/3][i][j]分别预处理第i块前j个数的和最大/和最小/差最大/差最小四种情况；h，z分别为后缀与整块；an[0/1]存第i个和/差 
pair<int,int> id[200005];//存每个数在第几块第几个 
vector<pair<int,int> > tree[200005];//动态数组建树 
void build(int x,int fa){//建树 
    for(int i=0;i<tree[x].size();i++){
        int Q=tree[x][i]._1;
        if(Q==fa) continue;
        d[Q]=d[x]+tree[x][i]._2;
        build(Q,x);
    }
}
void init(){//分块预处理 
    for(int i=1;i<=n;i++)
        id[i]=mp((i-1)/Z+1,(i-1)%Z+1);
    for(int i=1;i<=n;i++)
        an[0][i]=(ll)(d[i]*d[i]*d[i]+v[i]),an[1][i]=(ll)(d[i]*d[i]*d[i]-v[i]);
    for(int o=0;o<4;o++)
        for(int i=1;i<=Z;i++)
            q[o][i][1]=an[o/2][(i-1)*Z+1],h[o][i][Z]=an[o/2][i*Z];
    for(int i=1;i<=Z;i++){
        for(int j=2;j<=Z;j++){
            q[0][i][j]=max(q[0][i][j-1],an[0][(i-1)*Z+(j-1)%Z+1]);
            q[1][i][j]=min(q[1][i][j-1],an[0][(i-1)*Z+(j-1)%Z+1]);
            q[2][i][j]=max(q[2][i][j-1],an[1][(i-1)*Z+(j-1)%Z+1]);
            q[3][i][j]=min(q[3][i][j-1],an[1][(i-1)*Z+(j-1)%Z+1]);
        }
        for(int j=Z-1;j>0;j--){
            h[0][i][j]=max(h[0][i][j+1],an[0][(i-1)*Z+(j-1)%Z+1]);
            h[1][i][j]=min(h[1][i][j+1],an[0][(i-1)*Z+(j-1)%Z+1]);
            h[2][i][j]=max(h[2][i][j+1],an[1][(i-1)*Z+(j-1)%Z+1]);
            h[3][i][j]=min(h[3][i][j+1],an[1][(i-1)*Z+(j-1)%Z+1]);
        }
        for(int o=0;o<4;o++)
            z[o][i][i]=q[o][i][Z];
    }
    for(int i=1;i<Z;i++)
        for(int j=i+1;j<=Z;j++){
            z[0][i][j]=max(z[0][i][j-1],z[0][j][j]);
            z[1][i][j]=min(z[1][i][j-1],z[1][j][j]);
            z[2][i][j]=max(z[2][i][j-1],z[2][j][j]);
            z[3][i][j]=min(z[3][i][j-1],z[3][j][j]);
        }
}
ppp ask(int G,int H){//询问 
    ll A=-114514191981000,B=114514191981000,C=-114514191981000,D=114514191981000;
    if(id[G]._1==id[H]._1)//同一块 
         for(int i=G;i<=H;i++){
            A=max(A,an[0][i]);
            B=min(B,an[0][i]);
            C=max(C,an[1][i]);
            D=min(D,an[1][i]);
        }
    else if(id[G]._1+1==id[H]._1){//邻块 
        A=max(h[0][id[G]._1][id[G]._2],q[0][id[H]._1][id[H]._2]);
        B=min(h[1][id[G]._1][id[G]._2],q[1][id[H]._1][id[H]._2]);
        C=max(h[2][id[G]._1][id[G]._2],q[2][id[H]._1][id[H]._2]);
        D=min(h[3][id[G]._1][id[G]._2],q[3][id[H]._1][id[H]._2]);
    }else{//不邻块 
        A=max(max(h[0][id[G]._1][id[G]._2],q[0][id[H]._1][id[H]._2]),z[0][id[G]._1+1][id[H]._1-1]);
        B=min(min(h[1][id[G]._1][id[G]._2],q[1][id[H]._1][id[H]._2]),z[1][id[G]._1+1][id[H]._1-1]);
        C=max(max(h[2][id[G]._1][id[G]._2],q[2][id[H]._1][id[H]._2]),z[2][id[G]._1+1][id[H]._1-1]);
        D=min(min(h[3][id[G]._1][id[G]._2],q[3][id[H]._1][id[H]._2]),z[3][id[G]._1+1][id[H]._1-1]);
    }
    return mp(mp(A,B),mp(C,D));
}
inline int read(){//快读 
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    n=read(),T=read();
    Z=ceil(sqrt(n));
    for(int i=1;i<=n;i++) v[i]=read();
    for(int i=1;i<n;i++){
        U=read(),V=read(),W=read();
        tree[U].push_back(mp(V,W));
        tree[V].push_back(mp(U,W));
    }
    build(1,1);
    init();
    while(T--){
        l=read(),r=read(),L=read(),R=read();
        ppp ans=ask(l,r),ANS=ask(L,R);
        printf("%lld\n",max(max(ans._1._1-ANS._1._2,ans._2._1-ANS._2._2),max(ANS._1._1-ans._1._2,ANS._2._1-ans._2._2)));
    }//上面这个有点长，其实就是我们推出的四个式子求最大值 
    return 0;
}

（分块代码好长作者调了好久，同时也是本蒟蒻的第一篇题解，求求点个赞吧 qwq ）