动态树分治 / 动态分治树 / 动态点分树？？

Problem

https://www.luogu.org/problemnew/show/P3920

Solution

大概就是暴力往点分树里加点
替罪羊树思想什么时候不平衡重构就行
卡常注意

记得点分树的 size 别搞错
记得重构时分治中心不要忘记重新找

// Code by ajcxsu
// Problem: flower love

#include<bits/stdc++.h>
#define MOD (1000000000ll)
using namespace std;
typedef long long ll;
template<typename T> void gn(T &x) {
    T pl=1;
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') pl=(ch=='-'?-1:1), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=pl;
}

const double alpha=0.777666;
const int N=1e5+10, M=2e5+10;
int h[N], to[M], nexp[M], p=1;
ll W[M];
inline void ins(int a, int b, ll w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
int de[N];

const int OP=40;
int gup[N][OP];
ll sum[N][OP];
void ladd(int x, int f, ll w) {
    de[x]=de[f]+1, gup[x][0]=f, sum[x][0]=w;
    for(int i=1;i<OP;i++) gup[x][i]=gup[gup[x][i-1]][i-1], sum[x][i]=sum[x][i-1]+sum[gup[x][i-1]][i-1];
}
ll lca(int s, int t) {
    ll ret=0;
    if(de[s]<de[t]) swap(s,t);
    for(int j=OP-1;j>=0;j--) if(de[gup[s][j]]>=de[t]) ret+=sum[s][j], s=gup[s][j];
    if(s!=t) {
        for(int j=OP-1;j>=0;j--) if(gup[s][j]!=gup[t][j]) ret+=sum[s][j]+sum[t][j], s=gup[s][j], t=gup[t][j];
        ret+=sum[s][0]+sum[t][0];
    }
    return ret;
}

ll R[N];
ll tot[N], ans;


struct Node *nil;
struct Node {
    int s,c;
    ll v;
    Node *ch[2];
    Node(ll v=-(1ll<<62)): v(v) { s=c=1, ch[0]=ch[1]=nil; }
    int cmp(ll val) { return v==val?-1:val>v; }
    void upd() { s=c+ch[0]->s+ch[1]->s; }
    bool bad() { return ch[0]->s>s*alpha || ch[1]->s>s*alpha; }
} *nd[N], *bel[N], **bad;


Node po[N*OP];
Node *adr[N*OP+10];
int tt;
Node* pnew() { return adr[tt--]; }
void pdel(Node *x) { adr[++tt]=x; }

int len[N];
void ini() {
    for(int i=0;i<N*OP;i++) adr[++tt]=&po[i];
    nil=pnew();
    *nil=Node(), nil->ch[0]=nil->ch[1]=nil;
    nil->s=nil->c=0;
    bad=&nil;
    for(int i=0;i<N;i++) nd[i]=bel[i]=nil;
}
void ins(Node *&x, ll v) {
    if(x==nil) x=pnew(), *x=Node(v);
    else {
        int d=x->cmp(v);
        if(d==-1) x->c++;
        else ins(x->ch[d], v);
    }
    x->upd();
    if(x->bad()) bad=&x;
}
void cle(Node *x) {
    if(x==nil) return;
    cle(x->ch[0]), cle(x->ch[1]);
    pdel(x);
}
Node *stk[N];
int t;
Node* re2(int l, int r) {
    if(l==r) { stk[l]->ch[0]=stk[l]->ch[1]=nil, stk[l]->upd(); return stk[l]; }
    else if(l>r) return nil;
    int mid=(l+r)>>1;
    stk[mid]->ch[0]=re2(l, mid-1), stk[mid]->ch[1]=re2(mid+1, r), stk[mid]->upd();
    return stk[mid];
}
void re1(Node *x) {
    if(x==nil) return;
    re1(x->ch[0]), stk[++t]=x, re1(x->ch[1]);
}
void remake() { if(bad!=&nil) re1(*bad), *bad=re2(1, t), t=0, bad=&nil; }
int Rank(Node *x, ll v) {
    if(x==nil) return 0;
    int d=x->cmp(v);
    if(d==-1) return x->ch[0]->s+x->c;
    else if(d==0) return Rank(x->ch[0], v);
    else return Rank(x->ch[1], v) + x->ch[0]->s + x->c;
}

int fa[N], dep[N], siz[N], minn, S, hvy;
int gbad;
void ghvy(int x, int fa) {
    siz[x]=1;
    int ma=0;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fa && !dep[to[u]])
            ghvy(to[u], x), siz[x]+=siz[to[u]], ma=max(ma, siz[to[u]]);
    ma=max(ma, S-ma);
    if(ma<minn) minn=ma, hvy=x;
}

void gdep(int x, ll k, int f, Node *&rt, ll &tot, ll d) {
    ins(rt, k-R[x]), remake();
    tot+=Rank(rt, R[x]-k)*d;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=f && !dep[to[u]])
            gdep(to[u], k+W[u], x, rt, tot, d);
}

void gans(int x, int k) {
    dep[x]=k;
    ins(nd[x], -R[x]), remake();
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) {
            ghvy(to[u], 0);
            S=siz[to[u]], minn=0x3f3f3f3f, ghvy(to[u], 0);
            gdep(to[u], W[u], 0, nd[x], tot[x], 1);
            gdep(to[u], W[u], 0, bel[hvy], tot[x], -1);
            len[x]++;
            fa[hvy]=x, siz[hvy]=siz[to[u]], gans(hvy, k+1);
        }
    ans+=tot[x];
}

void gcle(int x, int fa) {
    for(int u=h[x];u;u=nexp[u])
        if(dep[to[u]]>dep[gbad] && to[u]!=fa) gcle(to[u], x);
    dep[x]=0; // clear tag
    cle(nd[x]), nd[x]=nil;
    if(x!=gbad) cle(bel[x]), bel[x]=nil;
    ans-=tot[x], tot[x]=0;
}

void gadd(int x, int f, ll w) {
    ladd(x, f, w);
    dep[x]=dep[f]+1, fa[x]=f;
    int d=x, ri;
    ll add=0;
    siz[x]=1;

    ins(nd[x], -R[x]), remake();
    while(fa[d]) {
        ri=lca(fa[d],x)-R[x];
        ins(nd[fa[d]], ri), remake(), ins(bel[d], ri), remake();
        add=Rank(nd[fa[d]], -ri) - Rank(bel[d], -ri);
        tot[fa[d]]+=add, ans+=add;
        siz[fa[d]]++;
        if(siz[d]>siz[fa[d]]*alpha) gbad=fa[d];
        d=fa[d];
    }
    if(gbad) {
        gcle(gbad, 0), S=siz[gbad], minn=0x3f3f3f3f, ghvy(gbad, 0);
        swap(fa[hvy], fa[gbad]), swap(bel[hvy], bel[gbad]), siz[hvy]=siz[gbad];
        gans(hvy, dep[fa[hvy]]+1), gbad=0;
    }
}

int main() {
    ini();
    int n;
    ll lastans=0, a, b, c;
    gn(n), gn(n);
    for(int i=1;i<=n;i++) {
        gn(a), gn(b), gn(c), a^=lastans;
        R[i]=c;
        if(a) ins(a, i, b), ins(i, a, b);
        gadd(i, a, b);
        printf("%lld\n", lastans=ans);
        lastans%=MOD;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3920.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆