Luogu P2590 [ZJOI2008]树的统计

2019-02-20 00:43:34来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

最近在学树剖,看到了这题就做了

[ZJOI2008]树的统计

思路

  从题面可以知道,这题是树剖题(要求的和模板没什么区别呀喂

  就是在普通的树剖上加了一个最大值

  所以可以知道就是树剖+特殊的线段树

  线段树要可以求区间最大值和区间和

  那么就很好做了,基本上就是到树剖模板题

  只需要给线段树加个最大值就行了

实现

  给线段树添加一个max,记录区间最大值

  可以得到线段树结构体如下

struct Tree
{
    int max;
    int l,r;
    int lazy;
    int val;
}t[MAXN<<2];

  每次更改时更新max,val

  由于只有单点修改,因此lazy tag可以不要

  对于最大值,每次访问取两个区间的最大值

  对于和,就和一般线段树一样了

  求和代码如下

int query_sum(int x,int y,int p)
{
    if(x<=t[p].l&&t[p].r<=y)
        return t[p].val;
    int mid=(t[p].l+t[p].r)>>1;
    int ans=0;
    if(x<=mid)
        ans+=query_sum(x,y,p<<1);
    if(y>mid)
        ans+=query_sum(x,y,p<<1|1);
    return ans;
}

  求最大值代码如下

int query_max(int x,int y,int p)
{
    if(x<=t[p].l&&t[p].r<=y)
        return t[p].max;
    int mid=(t[p].l+t[p].r)>>1;
    int ans=-1e9;
    if(x<=mid)
        ans=std::max(ans,query_max(x,y,p<<1));
    if(y>mid)
        ans=std::max(ans,query_max(x,y,p<<1|1));
    return ans;
}

  最后就是结合树剖了

代码

#include<bits/stdc++.h>
#define ll long long

using std::cin;
using std::cout;
using std::endl;

const int MAXN=3e4+5;

struct Edge
{
    int to,next;
}e[MAXN<<1];

struct Tree
{
    int max;
    int l,r;
    int lazy;
    int val;
}t[MAXN<<2];

int son[MAXN],depth[MAXN],id[MAXN],num[MAXN],head[MAXN],pri[MAXN],size[MAXN],fa[MAXN],top[MAXN];
int cnt=0;

void dfs1(int p,int f)
{
    depth[p]=depth[f]+1;
    fa[p]=f;
    size[p]=1;
    int now=head[p];
    while(now!=-1)
    {
        if(e[now].to==f)
        {
            now=e[now].next;
            continue;
        }
        dfs1(e[now].to,p);
        size[p]+=size[e[now].to];
        if(son[p]==-1||size[son[p]]<size[e[now].to])
            son[p]=e[now].to;
        now=e[now].next;
    }
}

void dfs2(int p,int t)
{
    top[p]=t;
    num[++cnt]=p;
    id[p]=cnt;
    if(son[p]==-1)
        return;
    dfs2(son[p],t);
    int now=head[p];
    while(now!=-1)
    {
        if(e[now].to==son[p]||e[now].to==fa[p])
        {
            now=e[now].next;
            continue;
        }
        dfs2(e[now].to,e[now].to);
        now=e[now].next;
    }
}

void build(int x,int y,int p)
{
    t[p].l=x;
    t[p].r=y;
    if(x==y)
    {
        t[p].val=pri[num[x]];
        t[p].max=pri[num[x]];
        return;
    }
    int mid=(x+y)>>1;
    build(x,mid,p<<1);
    build(mid+1,y,p<<1|1);
    t[p].max=std::max(t[p<<1].max,t[p<<1|1].max);
    t[p].val=t[p<<1].val+t[p<<1|1].val;
}

void change(int u,int p,int w)
{
    if(t[p].l==u&&t[p].r==u)
    {
        t[p].val=w;
        t[p].max=w;
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if(u<=mid)
        change(u,p<<1,w);
    else
        change(u,p<<1|1,w);
    t[p].val=t[p<<1].val+t[p<<1|1].val;
    t[p].max=std::max(t[p<<1].max,t[p<<1|1].max);
}

int query_max(int x,int y,int p)
{
    if(x<=t[p].l&&t[p].r<=y)
        return t[p].max;
    int mid=(t[p].l+t[p].r)>>1;
    int ans=-1e9;
    if(x<=mid)
        ans=std::max(ans,query_max(x,y,p<<1));
    if(y>mid)
        ans=std::max(ans,query_max(x,y,p<<1|1));
    return ans;
}

int query_sum(int x,int y,int p)
{
    if(x<=t[p].l&&t[p].r<=y)
        return t[p].val;
    int mid=(t[p].l+t[p].r)>>1;
    int ans=0;
    if(x<=mid)
        ans+=query_sum(x,y,p<<1);
    if(y>mid)
        ans+=query_sum(x,y,p<<1|1);
    return ans;
}

int qmax(int x,int y)
{
    int ans=-1e9;
    while(top[x]!=top[y])
    {
        if(depth[top[x]]<depth[top[y]])
            std::swap(x,y);
        ans=std::max(ans,query_max(id[top[x]],id[x],1));
        x=fa[top[x]];
    }
    if(id[x]>id[y])
        std::swap(x,y);
    ans=std::max(ans,query_max(id[x],id[y],1));
    return ans;
}

int qsum(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(depth[top[x]]<depth[top[y]])
            std::swap(x,y);
        ans+=query_sum(id[top[x]],id[x],1);
        x=fa[top[x]];
    }
    if(id[x]>id[y])
        std::swap(x,y);
    ans+=query_sum(id[x],id[y],1);
    return ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    memset(son,-1,sizeof(son));
    int n;
    cin>>n;
    for(int i=0;i<2*(n-1);i++)
    {
        int a,b;
        cin>>a>>b;
        e[i].to=b;
        e[i].next=head[a];
        head[a]=i++;
        e[i].to=a;
        e[i].next=head[b];
        head[b]=i;
    }
    for(int i=1;i<=n;i++)
        cin>>pri[i];
    int q;
    cin>>q;
    dfs1(1,0);
    cnt=0;
    dfs2(1,1);
    build(1,n,1);
    for(int i=0;i<q;i++)
    {
        std::string op;
        cin>>op;
        if(op=="CHANGE")
        {
            int u,v;
            cin>>u>>v;
            change(id[u],1,v);
        }
        if(op=="QMAX")
        {
            int u,v;
            cin>>u>>v;
            printf("%d\n",qmax(u,v));
        }
        if(op=="QSUM")
        {
            int u,v;
            cin>>u>>v;
            printf("%d\n",qsum(u,v));
        }
    }
    system("pause");//上交oj时记得注释或删除
    return 0;
}

  附带Luogu评测结果

  不知道为什么除了对于操作符使用了cin其他都是scanf和printf的在一本通oj上TLE了……

  于是就换成了取消同步的cin cout


原文链接:https://www.cnblogs.com/Cattttttttt/p/10403509.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:图的存储

下一篇:L1-050 倒数第N个字符串