Test 6.29 T4 简单数据结构练习

问题描述

费了一番功夫,神犇 CJK 终于完成了前三道题目。“不错,不愧是新一代神犇啊!” JesseLiu 满意地说道,“不过,你在算法方面的功底固然不错。对于数据结构的运用,你又掌握地如何呢?”

听到“数据结构”这四个字,就连身为神犇的 CJK 也不禁吓出一身冷汗。“年轻人,现在,对于我给定一棵树,你需要完成以下操作:

1.修改某个点的权值;

2.查询某两点间路径上所有点的权值和;

3.查询某点子树的权值和。”

CJK 脸上闪过一丝不屑:不就是道链剖裸题吗?

“这只是第一问。”JesseLiu 似乎也觉得这道题太水了,于是补充道:“完成以上所有操作后,我还会有以下几种询问:

询问某个点子树上有多少个点的权值小于等于 k;
询问某两点之间的路径上有多少点的权值小于等于 k;”

尽管 CJK 是神犇,但遇到这种题,也不禁感到一丝恐惧。还好,通过自己的玄学力量,他联系到了他的同学——你。现在,就请你 A 掉这最后一道水题。

输入格式

第一行一个数 n,表示点的总数。接下来 n-1 行,一行两个整数 x 和 y,表示x 和 y 之间有边相连。接下来一个整数 m1,表示第一问中操作的数量。接下来m1 行表示操作,格式如下:

“1 x y”将点 x 的权值修改为 y;

“2 x y”询问 x 到 y 路径上的点权之和(包括 x 和 y);

“3 x”询问 x 的子树上的点权和(包括 x);

接下来一行 m2,表示第二问中操作的数量。接下来 m2 行描述操作,格式如下:

“1 x y z”询问 x 到 y 的路径上有多少个点的权值小于等于 z;

“2 x y”询问 x 的子树上有多少个点的权值小于等于 y;

每个点的初始权值为 0。

输出格式

对于每一次询问,输出一个整数表示询问的答案。

样例输入输出

样例输入1

3

1 2

1 3

3

1 1 3

1 3 1

3 1

2

2 1 2

1 1 3 1

样例输出1

4

2

1

样例输入2

5

1 2

1 3

3 4

3 5

5

3 1

1 3 1

2 4 5

1 4 -1

3 3

2

1 1 5 0

2 3 -1

解析

对于第一问，显然是一道树链剖分单点修改加区间查询和的裸题，直接做即可。

对于第二问，一个点要产生贡献，当且仅当这个点在查询的范围内(子树or路径)，产生的贡献为1。为了满足限制，我们需要保证在询问时，除了小于等于询问值的节点的值为1以外其余节点都为0。我们可以想到，将询问与节点一起记在一个操作数组中，按照第一问的权值或者询问的值从小到大排序。每一个节点视为一个将节点对应的值变为1的操作，询问同第一问。

代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define N 500002

using namespace std;

struct opt{

    int op,id,x,y,val;

}a[N];

int head[N],ver[N*2],nxt[N*2],l;

int n,m1,m2,i,dfn[N],end[N],tim,ans[N];

int fa[N],size[N],top[N],son[N],dep[N],pos[N],tree[N],cnt;

void insert(int x,int y)

{

    l++;

    ver[l]=y;

    nxt[l]=head[x];

    head[x]=l;

}

void dfs1(int x)

{

    size[x]=1;

    for(int i=head[x];i;i=nxt[i]){

        int y=ver[i];

        if(y!=fa[x]){

            fa[y]=x;

            dep[y]=dep[x]+1;

            dfs1(y);

            if(size[son[x]]<size[y]) son[x]=y;

            size[x]+=size[y];

        }

    }

}

void dfs2(int x,int tp)

{

    dfn[x]=++tim;

    pos[x]=++cnt;top[x]=tp;

    if(son[x]) dfs2(son[x],top[x]);

    for(int i=head[x];i;i=nxt[i]){

        int y=ver[i];

        if(y!=son[x]&&y!=fa[x]) dfs2(y,y);

    }

    end[x]=tim;

}

void update(int p,int l,int r,int x,int val)

{

    if(x<l||r<x) return;

    if(l==r){

        tree[p]=val;

        return;

    }

    int mid=(l+r)/2;

    update(p*2,l,mid,x,val);

    update(p*2+1,mid+1,r,x,val);

    tree[p]=tree[p*2]+tree[p*2+1];

}

int ask(int p,int l,int r,int ql,int qr)

{

    if(r<ql||l>qr) return 0;

    if(l>=ql&&r<=qr) return tree[p];

    int mid=(l+r)/2;

    return ask(p*2,l,mid,ql,qr)+ask(p*2+1,mid+1,r,ql,qr);

}

int find(int u,int v)

{

    int f1=top[u],f2=top[v],ans=0;

    while(f1!=f2){

        if(dep[f1]<dep[f2]) swap(f1,f2),swap(u,v);

        ans+=ask(1,1,n,pos[f1],pos[u]);

        u=fa[f1];f1=top[u];

    }

    if(dep[u]>dep[v]) swap(u,v);

    return ans+ask(1,1,n,pos[u],pos[v]);

}

int my_comp(const opt &a,const opt &b)

{

    if(a.val==b.val) return a.op<b.op;

    return a.val<b.val;

}

int main()

{

    freopen("tree.in","r",stdin);

    freopen("tree.out","w",stdout);

    cin>>n;

    for(i=1;i<n;i++){

        int u,v;

        cin>>u>>v;

        insert(u,v);

        insert(v,u);

    }

    dfs1(1);

    dfs2(1,1);

    cin>>m1;

    for(i=1;i<=m1;i++){

        int op,x,y;

        cin>>op;

        if(op==1){

            cin>>x>>y;

            update(1,1,n,pos[x],y);

        }

        else if(op==2){

            cin>>x>>y;

            cout<<find(x,y)<<endl;

        }

        else{

            cin>>x;

            cout<<ask(1,1,n,dfn[x],end[x])<<endl;

        }

    }

    cin>>m2;

    int tmp=m2;

    for(i=1;i<=m2;i++){

        int op,x,y,z;

        cin>>op;

        if(op==1){

            cin>>x>>y>>z;

            a[i]=(opt){op,i,x,y,z};

        }

        else{

            cin>>x>>y;

            a[i]=(opt){op,i,x,0,y};

        }

    }

    for(i=1;i<=n;i++) a[++m2]=(opt){0,m2,i,0,ask(1,1,n,pos[i],pos[i])};

    memset(tree,0,sizeof(tree));

    sort(a+1,a+m2+1,my_comp);

    for(i=1;i<=m2;i++){

        if(a[i].op==0) update(1,1,n,pos[a[i].x],1);

        else if(a[i].op==1) ans[a[i].id]=find(a[i].x,a[i].y);

        else ans[a[i].id]=ask(1,1,n,dfn[a[i].x],end[a[i].x]);

    }

    for(i=1;i<=tmp;i++) cout<<ans[i]<<endl;

    fclose(stdin);

    fclose(stdout);

    return 0;

}

总结

一个思路：为了消去影响，可以使一个影响产生在询问以后，通过排序以及适当的转化实现。

巴特西