[BZOJ4372]烁烁的游戏 动态点分治+线段树


原题链接
跟震波类似,不同在于本题是范围修改单点查询.
动态点分治,对每个节点维护一棵线段树,表示x的点分子树中,到x后还能走k步的权值和,再维护一棵父亲的,容斥统计即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 102333
#define Big 30002333
using namespace std;
const int inf=0x3bbbbbbb;
int n,m;
int head[N],to[N<<1],nxt[N<<1],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;
inline 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);
}
inline int getsum(int x,int l,int r,int p)//求的是后缀和
{
    if(!x)return 0;
    if(p<=l)return a[x].sum;
    int mid=(l+r)>>1;
    if(p<=mid)return getsum(a[x].ls,l,mid,p)+a[a[x].rs].sum;
    return getsum(a[x].rs,mid+1,r,p);
}
int dfn[N],tim,minn[N<<1][20],Log[N<<1],deep[N];
void getdfn(int x,int pre)
{
    dfn[x]=++tim,deep[x]=minn[tim][0]=deep[pre]+1;
    int i,y;
    for(i=head[x];i;i=nxt[i])if((y=to[i])!=pre)
    {
        getdfn(y,x);
        minn[++tim][0]=deep[x];
    }
}
void rmq_init()
{
    getdfn(1,0);
    int i,j;
    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 lg=Log[y-x+1];
    return minn[x][0]+minn[y][0]-2*min(minn[x][lg],minn[y-(1<<lg)+1][lg]);
}
int size[N],maxx[N],rt,nn,vis[N],fa[N];
void getrt(int x,int pre)
{
    size[x]=1,maxx[x]=0;
    int i,y;
    for(i=head[x];i;i=nxt[i])if((y=to[i])!=pre&&!vis[y])
    {
        getrt(y,x);
        size[x]+=size[y],maxx[x]=max(maxx[x],size[y]);
    }
    maxx[x]=max(maxx[x],nn-size[x]);
    if(maxx[x]<maxx[rt])rt=x;
}
void getfa(int x,int pre)
{
    fa[x]=pre,vis[x]=1;
    int i,y;
    for(i=head[x];i;i=nxt[i])if(!vis[y=to[i]])
    {
        nn=size[y],maxx[0]=inf,rt=0;
        getrt(y,x);
        getrt(rt,x);//get real size
        getfa(rt,x);
    }
}
int root1[N],root2[N];
inline void fix(int x,int k,int v)
{
    int y,d;
    for(y=x;y;y=fa[y])if(k-(d=dis(x,y))>=0)
        insert(root1[y],0,n,k-d,v);
    for(y=x;fa[y];y=fa[y])if(k-(d=dis(x,fa[y]))>=0)
        insert(root2[y],0,n,k-d,v);
}
inline int getval(int x)
{
    int y,d,re=0;
    for(y=x;y;y=fa[y])re+=getsum(root1[y],0,n,dis(x,y));
    for(y=x;fa[y];y=fa[y])re-=getsum(root2[y],0,n,dis(x,fa[y]));
    return re;
}
int main()
{
    cin>>n>>m;
    int i,x,y;
    for(i=1;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    rmq_init();
    nn=n,maxx[0]=inf,rt=0;
    getrt(1,0);
    getrt(rt,0);
    getfa(rt,0);
    char opt[10];
    int k,v;
    for(i=1;i<=m;++i)
    {
        scanf("%s",opt);
        if(opt[0]=='M')
        {
            scanf("%d%d%d",&x,&k,&v);
            fix(x,k,v);
        }
        else
        {
            scanf("%d",&x);
            printf("%d\n",getval(x));
        }
    }
    return 0;
}
/*
7 7
1 2
2 3
3 4
4 5
1 6
3 7
M 1 1 9
M 6 2 -4
M 5 2 -5
Q 6
Q 4
Q 2
Q 5
*/

《[BZOJ4372]烁烁的游戏 动态点分治+线段树》上有7条评论

发表评论

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