首先,发现 $y,z$ 完全没用,题目的大意就是说每个点有一个集合,集合中的每个元素为 $(x_i,c_i)$ ,然后每一次询问一个点,再给出一个 $X$,需要你求出这个点的集合的所有元素中,$(x_i-X)^2+c_i$ 的最小值,输出这个最小值。

展开一下 $(x_i-X)^2+c_i$ ,会发现其实就等于 $X^2-2x_iX+x_i^2+c_i$ ,后面的那一坨显然就是一个一次函数。

很显然的想法就是每个点一棵线段树维护一下下凸包,这个很简单,就是直接爆炸。

然后会发现一个性质,按照题目来的话,同时拥有 $s$ 星球的节点应该是 $dfn$ 序列上的连续的区间,这样就只需要用线段树以 $dfn$ 序列的位置为下标维护信息。

然后就是将处理出这些区间操作。

void dfs(int u,int fa) {
    size[u]=1,dfn[u]=++dfn[0];
    if(!type[u]) /*新增一个,也就是这里会作为一个区间操作的左端点*/
        Dfn_L[change_id[u]].push_back(dfn[u]);
    else /*删掉一个,也就是上一个访问的节点会作为这个区间操作的右端点*/
        Dfn_R[change_id[u]].push_back(dfn[u]-1);
    for(int i=head[u],v;i;i=G[i].nxt) 
        if((v=G[i].to)!=fa) dfs(v,u),size[u]+=size[v];
    if(!type[u]) /*很显然如果这里新增一个的话,其贡献范围最多就是其子树*/
        Dfn_R[change_id[u]].push_back(dfn[u]+size[u]-1);
    else /*为什么这里可以删除,一定是因为其祖先节点拥有该星球,但是这个操作对
    u 的子树不能有贡献,那么直接跳到下一个访问的节点即可。*/
        Dfn_L[change_id[u]].push_back(dfn[u]+size[u]);
}   

然后具体怎么实现?

好像是标记永久化?每一次在 $l,r$ 区间中新增一个函数 $x$ ,询问的时候将线段树一条链上的所有答案取 $\min$ ,也就是说这个函数不下传。

挺好打的。

Code:

#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define freopen(x) {freopen(x".in","r",stdin),freopen(x".out","w",stdout);}

const int N=5e5+2;
const ll inf=2e17+2;

bool type[N];
ll ans[N];
int n,m,cnt,tot,dfn[N],size[N],change_id[N],head[N];
vector <int> Dfn_L[N],Dfn_R[N];
struct Ball {int x;ll c;} B[N];
struct Edge {int nxt,to;} G[N<<1];
struct Change {int l,r;ll k,b;} C[N];
struct Query {int id,node;ll X;} Q[N];
inline void add(int u,int v) {G[++cnt]=(Edge){head[u],v},head[u]=cnt;}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

void dfs(int u,int fa) {
    size[u]=1,dfn[u]=++dfn[0];
    if(!type[u]) Dfn_L[change_id[u]].push_back(dfn[u]);
    else Dfn_R[change_id[u]].push_back(dfn[u]-1);
    for(int i=head[u],v;i;i=G[i].nxt) 
        if((v=G[i].to)!=fa) dfs(v,u),size[u]+=size[v];
    if(!type[u]) Dfn_R[change_id[u]].push_back(dfn[u]+size[u]-1);
    else Dfn_L[change_id[u]].push_back(dfn[u]+size[u]);
}   

namespace Segment_Tree {
    #define mid ((l+r)>>1)
    int now[N<<2];
    vector <int> t[N<<2];
    inline double slope(int x,int y) {
        if(C[x].k==C[y].k) return C[x].b>C[y].b?-inf:inf;
        else return 1.0*(C[x].b-C[y].b)/(C[x].k-C[y].k);
    }
    void insert(int x,int l,int r,int L,int R,int id) {
        if(L<=l&&r<=R) {
            int I=t[x].size()-1;
            while(I>0&&slope(t[x][I-1],t[x][I])>slope(t[x][I],id)) --I,t[x].pop_back();
            t[x].push_back(id);return;
        }
        if(L<=mid) insert(x<<1,l,mid,L,R,id);
        if(R>mid) insert(x<<1|1,mid+1,r,L,R,id);
    }
    ll query(int x,int l,int r,int pos,ll X) {
        ll res=inf;
        int&I=now[x];int S=t[x].size()-1;
        while(I<S&&slope(t[x][I],t[x][I+1])<X) ++I;
        if(I<=S) res=C[t[x][I]].b-C[t[x][I]].k*X+X*X;
        if(l==r) return res;
        return min(res,pos<=mid?query(x<<1,l,mid,pos,X):query(x<<1|1,mid+1,r,pos,X));
    }
}using namespace Segment_Tree;

inline bool cmp_C_slope(Change a,Change b) {return a.k<b.k;}
inline bool cmp_Q_slope(Query a,Query b) {return a.X<b.X;}

int main() {
    freopen("2987");
    IN(n),IN(m),IN(B[1].c),change_id[1]=1;
    for(int i=2;i<=n;++i) {
        int op,fr,id,x,y,z;ll c;
        IN(op),IN(fr),IN(id),++fr,++id,add(i,fr),add(fr,i);
        change_id[i]=id;
        if(op==0) IN(x),IN(y),IN(z),IN(c),B[id]=(Ball){x,c};
        else type[i]=1;
    }
    dfs(1,0);
    for(int i=1;i<=n;++i)
        for(int j=0;j<Dfn_L[i].size();++j)
            C[++tot]=(Change){Dfn_L[i][j],Dfn_R[i][j],2ll*B[i].x,1ll*B[i].x*B[i].x+B[i].c};
    sort(C+1,C+1+tot,cmp_C_slope);
    for(int i=1;i<=m;++i) IN(Q[i].node),IN(Q[i].X),Q[i].id=i,++Q[i].node;
    sort(Q+1,Q+1+m,cmp_Q_slope);
    for(int i=1;i<=tot;++i) insert(1,1,n,C[i].l,C[i].r,i);
    for(int i=1;i<=m;++i) ans[Q[i].id]=query(1,1,n,dfn[Q[i].node],Q[i].X);
    for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注