[BZOJ3730]震波 动态点分治+线段树+RMQLCA+卡常


原题链接
给定一棵树,支持单点修改,以及查询距离x不超过k的节点的权值和.

我试图以这道题更加透彻地理解动态点分治.
动态点分治跟静态点分治的相似之处,不仅在于找重心得到分治树,更在于其思想.
普通点分治:求满足xxx条件的路径数量,那我们将这些路径分为经过重心不经过重心两类.
动态点分治:求跟询问点有关的xxx值,那么我们将产生贡献的点分为在询问点点分子树中在询问点点分子树外两类.
因此容斥原理是一个常用的思路,用总和减去算重复的.

以本题为例,我们建立点分树,给每个点挂两棵线段树,一棵维护子树中到点x距离为k的总权值,一棵维护到点fa[x]距离为k的总权值.查询时,考虑到一个点对询问点产生贡献,要么在其子树内,要么要经过其某个祖先节点,因此暴力往上跳,每层计算出从这过来的总权值,再减去算重复的.

然而本题卡时限,我写了两遍都TTTTTTT....
加IO优化,手写MinMax,线段树使用结构体存储等都没能让我跑过去,不得已用了一个trick:对每个点分子树求最大深度,拿这个深度当做线段树的上界,log会小一点,就能过了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100010
#define Big 20000010
using namespace std;
const int inf=0x3bbbbbbb;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
    x=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))x=x*10+c-'0',c=nc();
}
int n,m,head[N],to[N<<1],nxt[N<<1],val[N],etot;
inline void add(int x,int y)
{
    to[++etot]=y;
    nxt[etot]=head[x];
    head[x]=etot;
}
struct Node
{
    int ls,rs,sum;
}a[Big];
int tot;
void insert(int &x,int l,int r,int p,int v)
{
    if(!x)x=++tot;
    a[x].sum+=v;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(p<=mid)insert(a[x].ls,l,mid,p,v);
    else insert(a[x].rs,mid+1,r,p,v);
}
int getsum(int x,int l,int r,int p)
{
    if(!x)return 0;
    if(p>=r)return a[x].sum;
    int mid=(l+r)>>1;
    if(p<=mid)return getsum(a[x].ls,l,mid,p);
    else return a[a[x].ls].sum+getsum(a[x].rs,mid+1,r,p);
}
int dfn[N],deep[N],minn[N<<1][20],tim;
void getdfn(int x,int pre)
{
    deep[x]=deep[pre]+1,dfn[x]=++tim;
    minn[tim][0]=deep[x];
    int i,y;
    for(i=head[x];i;i=nxt[i])if((y=to[i])!=pre)
    {
        getdfn(y,x);
        minn[++tim][0]=deep[x];
    }
}
int Log[N<<1];
void rmqinit()
{
    int i,j,x;
    for(i=2;i<=tim;++i)Log[i]=Log[i>>1]+1;
    for(j=1;(1<<j)<=tim;++j)
        for(i=1;i+(1<<j)-1<=tim;++i)
            minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
}
inline int dis(int x,int y)
{
    x=dfn[x],y=dfn[y];
    if(x>y)swap(x,y);
    int l1=Log[y-x+1],l2=1<<l1;
    return minn[x][0]+minn[y][0]-2*min(minn[x][l1],minn[y-l2+1][l1]);
}
/*
树上的动态点分治实际上相当于序列上的线段树
受到静态点分治中使用的容斥的启发
一层一层考虑影响,到上一层时再消除本层的影
本题要求计算到x距离k以内的点的权值和
考虑到:点y到点x的路径要么是在x的点分子树里面,要么就是经过了x点分树上的某些祖先
因此从x暴力网上跳,每跳到一层就查询sum[0,k-dis(x,fa)],再减去在x那个儿子中的部分
*/
int size[N],maxx[N],rt,nn,vis[N],maxdp;
void getroot(int x,int pre,int dp)
{
    maxdp=max(maxdp,dp);
    size[x]=1,maxx[x]=0;
    for(int i=head[x];i;i=nxt[i])if(!vis[to[i]]&&to[i]!=pre)
    {
        getroot(to[i],x,dp+1);
        size[x]+=size[to[i]],maxx[x]=max(maxx[x],size[to[i]]);
    }
    maxx[x]=max(maxx[x],nn-size[x]);
    if(maxx[x]<=maxx[rt])rt=x;
}
int fa[N],R[N];
void getfa(int x,int pre)
{
    vis[x]=1,fa[x]=pre;
    int i,y;
    for(i=head[x];i;i=nxt[i])if((y=to[i])!=pre&&!vis[y])
    {
        nn=size[y],maxx[0]=inf,rt=0;
        getroot(y,x,0);
        maxdp=0;
        getroot(rt,0,0);
        R[rt]=maxdp;
        getfa(rt,x);
    }
}
int root1[N],root2[N];
void build()
{
    int x,y;
    for(x=1;x<=n;++x)
    {
        for(y=x;y;y=fa[y])insert(root1[y],0,R[y],dis(x,y),val[x]);
        for(y=x;fa[y];y=fa[y])insert(root2[y],0,R[fa[y]],dis(x,fa[y]),val[x]);
    }
}
inline void fix(int x,int v)
{
    int y;
    for(y=x;y;y=fa[y])insert(root1[y],0,R[y],dis(x,y),v-val[x]);
    for(y=x;fa[y];y=fa[y])insert(root2[y],0,R[fa[y]],dis(x,fa[y]),v-val[x]);
    val[x]=v;
}
inline int getans(int x,int k)
{
    int re=0,y,d,tmp;
    for(y=x;y;y=fa[y])
    {
        if(k>=(d=dis(x,y)))re+=(tmp=getsum(root1[y],0,R[y],k-d));
        if(fa[y]&&k>=(d=dis(x,fa[y])))re-=(tmp=getsum(root2[y],0,R[fa[y]],k-d));
    }
    return re;
}
int ans;
int main()
{
    read(n),read(m);
    int i,x,y;
    for(i=1;i<=n;++i)read(val[i]);
    for(i=1;i<n;++i)
    {
        read(x),read(y);
        add(x,y),add(y,x);
    }
    getdfn(1,0);
    rmqinit();
    nn=n,maxx[0]=inf;
    getroot(1,0,0);
    getroot(rt,0,0);
    R[rt]=maxdp;
    getfa(rt,0);
    build();
    int opt;
    for(i=1;i<=m;++i)
    {
        read(opt),read(x),read(y);
        x^=ans,y^=ans;
        if(!opt)printf("%d\n",ans=getans(x,y));
        else fix(x,y);
    }
    return 0;
}

发表评论

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