题解 P3920 【[WC2014]紫荆花之恋】

· · 题解

我的博客链接

动态点分治

题目给出的条件是：

dist(i,j) \le r_i+r_j

转换可得：

dist(i,j)-r_j \le r_i

因此可以考虑用动态点分治来解决这道题。

添加新节点x，更新答案时还是动态点分治的套路，由于我们只需要统计新加入节点的答案，因此我们一路跳点分树，利用容斥，设当前跳到点为t，路径长度为d，这里利用了平衡树（替罪羊树，本题只有插入操作，替罪羊树巨好写，常数还小）。

那么满足题意的点y需满足的条件是：

d+dist(t,y) \le r_x+r_y \therefore r_x-d \ge dist(t,y)-r_y

查找其替罪羊树上\le r_x-d的数的个数，容斥计算答案。

计算路径长度d，我想不出O(1)求解的方法，直接暴力写LCT（好像倍增就行了，某指导：倍增已经被时代遗弃）。

新添加节点可以直接连上去当成一个大小为1的连通块，不会改变点分树的性质。

我们利用**替罪羊树**的思想，对不平衡节点暴力重构，直接把我们插入节点的那条链从高到低扫到第一个需要重构的节点（不用就不重构）。 假设要重构$x$子树，这是点分树上的子树，我们如何在原树上找到这棵子树呢？ 我想了一个很逊的方法，记录每个节点在点分树上的深度$dep$，每次访问到$dep_y \le dep_x$的节点（下面称为无效节点）就跳过，其余满足条件的节点（下面称为有效节点）就一定在子树内。 那么会不会有一个节点的连接节点很多，导致遍历复杂度爆炸呢？ ![](https://cdn.luogu.com.cn/upload/image_hosting/754kxglk.png) 答案是不会。 设点分树上$x$节点记录的原树连通块为$T_x

我们考虑点分树的性质，假如x与T_{y}中一点有边，必有x \in T_{y}和T_{y} \subset T_{x}其中一个成立。

因此，如果一条边(u,v)，v是无效节点，u是有效节点，那么v必然为x在点分树上的祖先。

同时，一个无效节点顶多与T_x中一个节点相连，否则必然出现了环。

由于点分树树高为\log级别，我们最多访问到\log级别的无效节点，而我们每次插入点最多重构一次，那么访问无效节点在整道题中消耗的时间复杂度上限为O(n \log n)。

注意，这里计算时不要使用LCT求距离，要建ST表，因为LCT上访问的时间复杂度为O(\log n)，举个例子，假如有大小为4的树需要重构，LCT一次查询的时间复杂度为O(\log n)，显然用ST表就可以O(4 \log 4)预处理，O(1)查询。

同时，重构时，对于x的父节点f_x，x对它的容斥贡献可以直接继承。

Code: 
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100005
#define M 8000005
#define S 1000000000
#define INF 1000000007
#define il inline
#define rint register int
#define D double
#define ll long long
#define lc(x) lct[x].ch[0]
#define rc(x) lct[x].ch[1]
#define sr(x) lct[x].sz
#define fa(x) lct[x].ft
#define rev(x) lct[x].tag
#define ls(x) a[x].ch[0]
#define rs(x) a[x].ch[1]
#define val(x) a[x].value
#define cnt(x) a[x].cct
#define s(x) a[x].siz
using namespace std;
const D alpha=0.7;
int ty,n,ai,ci,ri;
int w[N],q[N],lcq[N << 1],cq[N];
int tot,f[N],dep[N],fr[N],nxt[N << 1],d1[N << 1],d2[N << 1];
int lsz,rrf,rtsz,rt,tsz[N],sz[N];
int dfnt,cdp[N],bg[N],lg2[N << 1],st[N << 1][22];
int pool[M+25],ct;
bool vis[N];
ll ans=0;
struct Link_Cut_Tree
{
    int ch[2],sz,ft;
    bool tag;
}lct[N << 1];
int lctct,vd[N << 1];
il void connect(int x,int y,int son)
{
    fa(x)=y;
    lct[y].ch[son]=x;
}
il int id(int x)
{
    return lc(fa(x))==x?0:1;
}
il bool isrt(int x)
{
    return lc(fa(x))!=x && rc(fa(x))!=x;
}
il void update(int x)
{
    sr(x)=sr(lc(x))+sr(rc(x))+vd[x];
}
il void rot(int x)
{
    int y=fa(x),r=fa(y);
    int yson=id(x),rson=id(y);
    if (isrt(y))
        fa(x)=r; else
        connect(x,r,rson);
    connect(lct[x].ch[yson^1],y,yson);
    connect(y,x,yson^1);
    update(y),update(x);
}
il void push_rev(int x)
{
    if (!x)
        return;
    swap(lc(x),rc(x));
    rev(x)^=1;
}
il void push_down(int x)
{
    if (rev(x))
    {
        push_rev(lc(x));
        push_rev(rc(x));
        rev(x)=false;
    }
}
il void splay(int x)
{
    int g=x,k=0;
    lcq[++k]=g;
    while (!isrt(g))
        g=fa(g),lcq[++k]=g;
    while (k)
        push_down(lcq[k--]);
    while (!isrt(x))
    {
        int y=fa(x);
        if (isrt(y))
            rot(x); else
        if (id(x)==id(y))
            rot(y),rot(x); else
            rot(x),rot(x);
    }
}
il void access(int x)
{
    for (rint y=0;x;y=x,x=fa(x))
    {
        splay(x);
        rc(x)=y;
        update(x);
    }
}
il void makeroot(int x)
{
    access(x);
    splay(x);
    push_rev(x);
}
il void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}
il void link(int x,int y)
{
    makeroot(x);
    fa(x)=y;
}
il void link_v(int x,int y,int z)
{
    ++lctct;
    vd[lctct]=z;
    link(x,lctct),link(y,lctct);
}
il int dis(int x,int y)
{
    split(x,y);
    return sr(y);
}
struct node
{
    int ch[2],value,cct,siz;
}a[M+25];
int rp,rq,rg,tr1[N],tr2[N];
il void add_pool()
{
    for (rint i=1;i<=M;++i)
        pool[i]=M-i+1;
    ct=M;
}
il int newnode(int x)
{
    int z=pool[ct--];
    ls(z)=rs(z)=0,val(z)=x,s(z)=cnt(z)=1;
    return z;
}
il int build(int l,int r)
{
    if (l>r)
        return 0;
    if (l==r)
    {
        s(cq[l])=cnt(cq[l]),ls(cq[l])=rs(cq[l])=0;
        return cq[l];
    }
    int mid=(l+r) >> 1;
    ls(cq[mid])=build(l,mid-1);
    rs(cq[mid])=build(mid+1,r);
    s(cq[mid])=s(ls(cq[mid]))+s(rs(cq[mid]))+cnt(cq[mid]);
    return cq[mid];
}
il void dfs(int x)
{
    if (!x)
        return;
    dfs(ls(x));
    cq[++cq[0]]=x;
    dfs(rs(x));
}
il int reb(int x)
{
    cq[0]=0;
    dfs(x);
    int tt=build(1,cq[0]);
    return tt;
}
il bool bad(int x,int y)
{
    return alpha*s(x)<=s(y);
}
il void insr(int &x,int y)
{
    if (!x)
    {
        x=newnode(y);
        return;
    }
    s(x)++;
    if (val(x)==y)
    {
        cnt(x)++;
        return;
    }
    int nxt=(val(x)>y)?0:1;
    insr(a[x].ch[nxt],y);
    if (bad(x,a[x].ch[nxt]))
        rp=x,rq=rg=0; else
    if (rp && !rq)
        rq=x,rg=nxt;
}
il void ins(int &x,int y)
{
    rp=rq=rg=0;
    insr(x,y);
    if (rp)
    {
        if (rq)
            a[rq].ch[rg]=reb(rp); else
            x=reb(rp);
    }
}
il int calc(int x,int y)
{
    int ans=0;
    while (x)
    {
        if (val(x)==y)
        {
            ans+=s(ls(x))+cnt(x);
            break;
        }
        if (val(x)<y)
            ans+=s(ls(x))+cnt(x),x=rs(x); else
            x=ls(x);
    }
    return ans;
}
il int read()
{
    int s=0;
    char c=getchar();
    while (c<'0' || c>'9')
        c=getchar();
    while ('0'<=c && c<='9')
        s=(s << 3)+(s << 1)+(c^48),c=getchar();
    return s;
}
il void write(ll x)
{
    if (x>9)
        write(x/10);
    putchar(x%10+48);
}
il void add(int x,int y,int z)
{
    ++tot;
    d1[tot]=y,d2[tot]=z;
    nxt[tot]=fr[x];
    fr[x]=tot;
}
il void clear_sgt(int u)
{
    if (!u)
        return;
    pool[++ct]=u;
    clear_sgt(ls(u)),clear_sgt(rs(u));
}
il void clear_vis_sgt_getst(int u,int F,int mxd)
{
    clear_sgt(tr1[u]),tr1[u]=0;
    if (f[u]!=rrf)
        clear_sgt(tr2[u]),tr2[u]=0;
    vis[u]=false;
    st[++dfnt][0]=u;
    bg[u]=dfnt;
    for (rint i=fr[u];i;i=nxt[i])
    {
        int v=d1[i];
        if (dep[v]<=mxd || v==F)
            continue;
        cdp[v]=cdp[u]+d2[i];
        clear_vis_sgt_getst(v,u,mxd);
        st[++dfnt][0]=u;
    }
}
il int lca(int x,int y)
{
    x=bg[x],y=bg[y];
    if (x>y)
        swap(x,y);
    int k=lg2[y-x+1];
    return (cdp[st[x][k]]<cdp[st[y-(1 << k)+1][k]])?st[x][k]:st[y-(1 << k)+1][k];
}
il int st_dis(int x,int y)
{
    return cdp[x]+cdp[y]-(cdp[lca(x,y)] << 1);
}
il void findrt(int u,int F,int rn)
{
    int mx=-1;
    sz[u]=1;
    for (rint i=fr[u];i;i=nxt[i])
    {
        int v=d1[i];
        if (v==F || vis[v])
            continue;
        findrt(v,u,rn);
        sz[u]+=sz[v];
        if (sz[v]>mx)
            mx=sz[v];
    }
    mx=max(mx,rn-sz[u]);
    if (mx<rtsz)
        rtsz=mx,rt=u;
}
il void getrt(int u,int rn)
{
    rtsz=INF;
    findrt(u,0,rn);
}
il void update_dis(int u,int F,int rt)
{
    ins(tr1[rt],st_dis(rt,u)-w[u]);
    if (f[rt] && f[rt]!=rrf)
        ins(tr2[rt],st_dis(f[rt],u)-w[u]);
    for (int i=fr[u];i;i=nxt[i])
    {
        int v=d1[i];
        if (v==F || vis[v])
            continue;
        update_dis(v,u,rt);
    }
}
il void solve(int u)
{
    int csz=lsz;
    vis[u]=true,tsz[u]=1;
    update_dis(u,0,u);
    for (rint i=fr[u];i;i=nxt[i])
    {
        int v=d1[i];
        if (vis[v])
            continue;
        lsz=(sz[v]<sz[u])?sz[v]:csz-sz[u];
        getrt(v,lsz);
        f[rt]=u,dep[rt]=dep[u]+1;
        int qt=rt;
        solve(rt);
        tsz[u]+=tsz[qt];
    }
}
il void rebuild(int x)
{
    rrf=f[x];
    lsz=tsz[x];
    dfnt=0,cdp[x]=0;
    clear_vis_sgt_getst(x,0,dep[x]);
    for (rint j=1;j<=lg2[dfnt];++j)
        for (rint i=1;i<=dfnt-(1 << j)+1;++i)
            st[i][j]=(cdp[st[i][j-1]]<cdp[st[i+(1 << j-1)][j-1]])?st[i][j-1]:st[i+(1 << j-1)][j-1];
    getrt(x,lsz);
    f[rt]=rrf,dep[rt]=dep[x],tr2[rt]=tr2[x],tr2[x]=0;
    solve(rt);
}
il void isr(int x,int y)
{
    vis[x]=true;
    f[x]=y,dep[x]=dep[y]+1;
    int t=y;
    q[0]=0;
    while (t)
        q[++q[0]]=t,tsz[t]++,t=f[t];
    for (rint i=1;i<=q[0];++i)
    {
        int o=dis(q[i],x);
        ans+=calc(tr1[q[i]],w[x]-o),ins(tr1[q[i]],o-w[x]);
        if (i!=1)
            ans-=calc(tr2[q[i-1]],w[x]-o),ins(tr2[q[i-1]],o-w[x]); else
            ins(tr2[x],o-w[x]);
    }
    for (rint i=q[0];i>1;--i)
        if (alpha*tsz[q[i]]<=tsz[q[i-1]])
        {
            rebuild(q[i]);
            break;
        }
}
int main()
{
    ty=read(),n=read();
    add_pool();
    lg2[0]=-1;
    for (rint i=1;i<=(n << 1);++i)
        lg2[i]=lg2[i >> 1]+1;
    lctct=n;
    for (rint i=1;i<=n;++i)
    {
        ai=read(),ci=read(),w[i]=read();
        ai=(ans%S)^ai;
        ins(tr1[i],-w[i]);
        tsz[i]=1;
        if (!ai && !ci)
        {
            vis[1]=true;
            write(ans),putchar('\n');
            continue;
        }
        link_v(i,ai,ci);
        add(ai,i,ci),add(i,ai,ci);
        isr(i,ai);
        write(ans),putchar('\n');
    }
    return 0;
}