P4216

Aryper · 2021-08-13 13:20:26 · 个人记录

[SCOI2015]情报传递

路径上的人数可以通过 LCA 直接求，这里的 LCA 用了树剖，其实用倍增同样可以解决，不作赘述。

主要看第二个问题，如何统计构成威胁的点。

首先了解一个思想，我们所求的构成威胁的点，满足这样一个条件：i-T> C。其中 i 为当前时刻，T 为该点开始收集情报的时刻，C 为 i 时刻传递情报的风险控制值。那么上式变换即为 T<i-C。找到路径上满足条件的点的个数即可。

因为上式的变化，这道题变得能够离线，我们就可以把点权赋值为 T，没有传递情报的点赋值为 q（即题目中描述的），然后针对每个询问统计即可。

这题的统计核心在于树上主席树。

我们知道，主席树一般能够维护值域类型的计数信息。

这里我们同样建立主席树，其中 rt_i 维护的是从根节点到节点 i 的路径上的计数。那么很自然的想到，我们的 i 是在其父节点 fa_i 的版本上进行修改的。同样很自然的，我们可以通过 i 的版本与 lca(i,j) 的版本得到 i 到 lca(i,j) 之间满足条件的点的个数，j 也是同理。

然后因为这种找法会导致 lca(i,j) 被重复寻找，因此要再判断一下以去重。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=2e6;

struct sgt{
    ll l,r,dat;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define dat(x) tree[x].dat
}tree[N*4+5];

struct node{
    ll x,y,c,id;
}a[N+5];

ll n,q,op,t,qt,root,cnt,tot;

ll ver[N*2+5],nxt[N*2+5],head[N+5];

ll dt[N+5],top[N+5],hs[N+5],siz[N+5],fa[N+5],rt[N+5],w[N+5];

ll getlca(ll x,ll y) {
    while(top[x]!=top[y]) {
        if(dt[top[x]]<dt[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return dt[x]<dt[y]?x:y;
}

void dfs(ll p,ll fath) {
    dt[p]=dt[fath]+1;siz[p]=1;
    for(ll i=head[p];i;i=nxt[i]) {
        dfs(ver[i],p);siz[p]+=siz[ver[i]];
        if(siz[ver[i]]>siz[hs[p]]) hs[p]=ver[i];
    }
}

void dfs_(ll p,ll topf) {
    top[p]=topf;
    if(!hs[p]) return;
    dfs_(hs[p],topf);
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==hs[p]) continue;
        dfs_(ver[i],ver[i]);
    }
}

ll query(ll p,ll q,ll l,ll r,ll k) {
    if(l==r) return dat(q)-dat(p);
    ll mid=(l+r)>>1;
    if(k<=mid) return query(l(p),l(q),l,mid,k);
    return dat(l(q))-dat(l(p))+query(r(p),r(q),mid+1,r,k);
}

void ins(ll &p,ll q,ll l,ll r,ll k) {
    dat(p=++cnt)=dat(q)+1;
    l(p)=l(q);r(p)=r(q);
    if(l==r) return;
    ll mid=(l+r)>>1;
    if(k<=mid) ins(l(p),l(q),l,mid,k);
    else ins(r(p),r(q),mid+1,r,k);
}

void build(ll p) {
    ins(rt[p],rt[fa[p]],1,q,w[p]);
    for(ll i=head[p];i;i=nxt[i]) build(ver[i]);
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        fa[i]=read();
        if(!fa[i]) root=i;
        else add(fa[i],i);
    }

    q=read();

    for(ll i=1;i<=n;i++) w[i]=q;

    for(ll i=1;i<=q;i++) {
        op=read();
        if(op==1) {
            a[++qt].x=read();a[qt].y=read();
            a[qt].c=read();a[qt].id=i;
        }
        if(op==2) {
            t=read();w[t]=i;
        }
    }

    dfs(root,0);dfs_(root,root);
    build(root);

    for(ll i=1;i<=qt;i++) {
        ll lca=getlca(a[i].x,a[i].y);
        write(dt[a[i].x]+dt[a[i].y]-2*dt[lca]+1);putchar(' ');
        ll ans=0;
        if(a[i].id-a[i].c-1<=0) {
            write(0);putchar('\n');continue;
        }
        ans+=query(rt[lca],rt[a[i].x],1,q,a[i].id-a[i].c-1);
        ans+=query(rt[lca],rt[a[i].y],1,q,a[i].id-a[i].c-1);
        ans+=(w[lca]<a[i].id-a[i].c);
        write(ans);putchar('\n');
    }

    return 0;
}

附另一代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=2e6;

struct sgt{
    ll l,r,dat;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define dat(x) tree[x].dat
}tree[N*4+5];

struct node{
    ll x,y,c,id;
}a[N+5];

ll n,q,op,t,qt,root,cnt,tot;

ll ver[N*2+5],nxt[N*2+5],head[N+5];

ll dt[N+5],fa[N+5][30],rt[N+5],w[N+5],lg[N+5];

ll getlca(ll x,ll y) {
    if(dt[x]<dt[y]) swap(x,y);
    while(dt[x]>dt[y]) x=fa[x][lg[dt[x]-dt[y]]-1];
    if(x==y) return x;
    for(ll k=lg[dt[x]]-1;k>=0;k--) {
        if(fa[x][k]!=fa[y][k]) {
            x=fa[x][k];y=fa[y][k];
        }
    }
    return fa[x][0];
}

void dfs(ll p,ll fath) {
    dt[p]=dt[fath]+1;
    for(ll i=1;i<=lg[dt[p]];i++) {
        fa[p][i]=fa[fa[p][i-1]][i-1];
    }
    for(ll i=head[p];i;i=nxt[i]) {
        dfs(ver[i],p);
    }
}

ll query(ll p,ll q,ll l,ll r,ll k) {
    if(l==r) return dat(q)-dat(p);
    ll mid=(l+r)>>1;
    ll ldat=dat(l(q))-dat(l(p));
    if(k<=mid) return query(l(p),l(q),l,mid,k);
    return ldat+query(r(p),r(q),mid+1,r,k);
}

ll ins(ll cur,ll l,ll r,ll k) {
    ll p=++cnt;
    tree[p]=tree[cur];
    if(l==r) {
        dat(p)++;return p;
    }
    ll mid=(l+r)>>1;
    if(k<=mid) l(p)=ins(l(cur),l,mid,k);
    else r(p)=ins(r(cur),mid+1,r,k);
    dat(p)=dat(l(p))+dat(r(p));
    return p;
}

void build(ll p) {
    rt[p]=ins(rt[fa[p][0]],1,q,w[p]);
    for(ll i=head[p];i;i=nxt[i]) build(ver[i]);
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }

    for(ll i=1;i<=n;i++) {
        fa[i][0]=read();
        if(!fa[i][0]) root=i;
        else add(fa[i][0],i);
    }

    q=read();

    for(ll i=1;i<=n;i++) w[i]=q;

    for(ll i=1;i<=q;i++) {
        op=read();
        if(op==1) {
            a[++qt].x=read();a[qt].y=read();
            a[qt].c=read();a[qt].id=i;
        }
        if(op==2) {
            t=read();w[t]=i;
        }
    }

    dfs(root,0);build(root);

    for(ll i=1;i<=qt;i++) {
        ll lca=getlca(a[i].x,a[i].y);
        write(dt[a[i].x]+dt[a[i].y]-2*dt[lca]+1);putchar(' ');
        ll ans=0;
        if(a[i].id-a[i].c-1<=0) {
            write(0);putchar('\n');continue;
        }
        ans+=query(rt[lca],rt[a[i].x],1,q,a[i].id-a[i].c-1);
        ans+=query(rt[lca],rt[a[i].y],1,q,a[i].id-a[i].c-1);
        ans+=(w[lca]<a[i].id-a[i].c);
        write(ans);putchar('\n');
    }

    return 0;
}