2019牛客暑期多校训练营（第八场）I-Inner World DFS序+主席树（扫描线也可）

题意：初始有n棵树，每棵树都只有1个n号节点，现在有m次添加操作，每次操作是将$[l,r]$范围内的树的$u$节点后面添加一个$v$节点。每个v节点只会被添加一次。

　　然后是q次询问，输出$[l,r]$范围内的树$x$节点的子树大小之和。

思路：由于每个节点被当成子节点添加到树上只会被添加一次，所以假设直接将节点连到一棵树上，按照dfs排序之后，x节点的子树dfs序必定是连续的。

　　考虑主席树，我们以dfs序为主席树的版本，每个节点就让$(ql，qr)$之间的树加一，最后只需要将ou[x]和in[x]-1这两个版本之间的主席树相减即可。（代码在最下方）

　　另一个做法：考虑扫描线，我们还是先处理处dfs序，对于节点x的求解，我们可以分解成，减去x之前所有节点(ql,qr)的值，再加上ou[x]的(ql,qr)的值，就得到了我们要的答案。所以我们还是按dfs序处理线段树，将每一个节点的影响加入线段树后，再处理这个节点需要加减的地方即可。我自己没有写过扫描线版本，此处引用一位朋友的代码。

//这是扫描线的关键，此处的线段树就是一个普通的区间求和的线段树。    
scanf("%d", &q);

    for(int i = ; i <= q; i++) {

        int x, l, r;

        scanf("%d%d%d", &x, &l, &r);

        V[in[x] - ].push_back(Qus{-, l, r, i});

        V[ot[x]].push_back(Qus{, l, r, i});

    }

    for(int i = ; i <= idx; i++) {

        Tree.update(L[rk[i]], R[rk[i]], , , n, );

        for(auto t : V[i]) {

            ans[t.id] += t.op * Tree.query(t.l, t.r, , n, );

        }

    }

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define dep(i,b,a) for(int i=b;i>=a;i--)

#define clr(a,b) memset(a,b,sizeof(a))

#define pb push_back

#define pii pair<int,int >

using namespace std;

typedef long long ll;

ll rd()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

const int inf=0x3f3f3f3f;

int n,m,q,tot,root[maxn],l[maxn],r[maxn],in[maxn],ou[maxn],re[maxn],ti;

struct node{

    int l,r;

    ll sum,lazy;

}tr[maxn*];

vector<int >ve[maxn];

void dfs(int u){

    in[u]=++ti;

    re[ti]=u;

    for(auto it:ve[u]){

        dfs(it);

    }

    ou[u]=ti;

}

void update(int &rt,int pre,int l,int r,int ql,int qr,ll val){

    tr[rt=++tot]=tr[pre];

    tr[rt].sum+=(qr-ql+)*val;

    if(ql<=l&&r<=qr){

        tr[rt].lazy+=val;

        return;

    }

    int mid=(l+r)>>;

    if(ql<=mid)update(tr[rt].l,tr[pre].l,l,mid,ql,min(qr,mid),val);

    if(mid<qr)update(tr[rt].r,tr[pre].r,mid+,r,max(mid+,ql),qr,val);

}

ll query(int rt,int pre,int l,int r,int ql,int qr,ll add){

    if(ql<=l&&r<=qr){

        return tr[rt].sum-tr[pre].sum+(r-l+)*add;

    }

    add+=tr[rt].lazy-tr[pre].lazy;

    int mid=(l+r)>>;

    ll res=;

    if(ql<=mid)res+=query(tr[rt].l,tr[pre].l,l,mid,ql,qr,add);

    if(mid<qr)res+=query(tr[rt].r,tr[pre].r,mid+,r,ql,qr,add);

    return res;

}

int main(){

    cin>>n>>m;

    l[]=,r[]=n;

    for(int i=;i<=m;i++){

        int u,v,x,y;

        u=rd(),v=rd(),x=rd(),y=rd();

        ve[u].pb(v);

        l[v]=x,r[v]=y;

    }

    dfs();

    for(int i=;i<=ti;i++){

        int u=re[i];

        update(root[i],root[i-],,n,l[u],r[u],);

    }

    cin>>q;

    rep(i,,q){

        int x,ql,qr;

        x=rd(),ql=rd(),qr=rd();

        printf("%lld\n",query(root[ou[x]],root[in[x]-],,n,ql,qr,));

    }

}

巴特西

2019牛客暑期多校训练营（第八场）I-Inner World DFS序+主席树（扫描线也可）

最新文章

热门文章