Statistics of Luogu P2590 [ZJOI2008] tree

I've been learning tree dissection recently. When I saw this, I did it

Statistics of [ZJOI2008] tree

thinking

From the question surface, we can know that this question is a tree cutting question (what is required is no different from the template

It is to add a maximum value to the common tree section

So we can know that it is the tree section + special line tree

The line segment tree should be able to find the maximum value and sum of intervals

So it's very good. Basically, it's the tree section template problem

Just add a maximum value to the line tree

Realization

Add a max to the segment tree to record the maximum value of the interval

The line tree structure can be obtained as follows

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

Update max, val every time you change

Since there is only a single point of modification, lazy tag can not be used

For the maximum value, the maximum value of two intervals is taken for each visit

For and, it is the same as the general line tree

The sum code is as follows

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;
}

The maximum value code is as follows

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;
}

In the end, it's combined with tree cutting

Code

#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");//Hand in oj Remember to comment or delete
    return 0;
}

With the evaluation results of Luogu

I don't know why, except for the use of cin for operators, it's all scanf and printf's TLE on a Book of general oj

So it's replaced by a cin cout that cancels synchronization

Tags: C++ iOS

Posted on Sun, 01 Dec 2019 06:47:47 -0800 by threaders