洛谷P4556 [Vani有約會]雨天的尾巴(線段樹合并)

題目背景

深繪裡一直很讨厭雨天。

灼熱的天氣穿透了前半個夏天，後來一場大雨和随之而來的洪水，澆滅了一切。

雖然深繪裡家鄉的小村落對洪水有着頑固的抵抗力，但也倒了幾座老房子，幾棵老樹被連根拔起，以及田地裡的糧食被弄得一片狼藉。

無奈的深繪裡和村民們隻好等待救濟糧來維生。

不過救濟糧的發放方式很特别。

題目描述

首先村落裡的一共有n座房屋，并形成一個樹狀結構。然後救濟糧分m次發放，每次選擇兩個房屋(x,y)，然後對于x到y的路徑上（含x和y)每座房子裡發放一袋z類型的救濟糧。

然後深繪裡想知道，當所有的救濟糧發放完畢後，每座房子裡存放的最多的是哪種救濟糧。

輸入輸出格式

輸入格式：

第一行兩個正整數n,m，含義如題目所示。

接下來n-1行，每行兩個數(a,b)，表示(a,b)間有一條邊。

再接下來m行，每行三個數(x,y,z)，含義如題目所示。

輸出格式：

n行，第i行一個整數，表示第i座房屋裡存放的最多的是哪種救濟糧，如果有多種救濟糧存放次數一樣，輸出編号最小的。

如果某座房屋裡沒有救濟糧，則對應一行輸出0。

輸入輸出樣例

輸入樣例#1：

複制

5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3      

輸出樣例#1： 複制

2
3
3
0
2      

說明

對于20%的資料，1 <= n, m <= 100

對于50%的資料，1 <= n, m <= 2000

對于100%的資料，1 <= n, m <= 100000, 1 <= a, b, x, y <= n, 1 <= z <= 100000

Vani

題解：這題的話主要是差分的思想，把每條覆寫路徑離線下來，分解成(u,lca(u,v))(u,lca(u,v))(u,lca(u,v)),(v,lca(u,v))(v,lca(u,v))(v,lca(u,v))兩條路徑，在uuu點和vvv點将zzz位置+1+1+1,在lca(u,v)lca(u,v)lca(u,v)和fa(lca(u,v))fa(lca(u,v))fa(lca(u,v))的位置分别−1-1−1就可以了。每個點直接查詢最大值，即為答案。

代碼如下：

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson tr[now].l
#define rson tr[now].r
using namespace std;

struct tree
{
    int l,r,sum,val;
}tr[5000050];

int n,m,deep[100010],a[100010],cnt,rt[100010],fa[100010][18],ans[100010];
vector<int> g[100010];
vector<int> op1[100010],op2[100010];

int dfs(int now,int f,int dep)
{
    fa[now][0]=f;
    deep[now]=dep;
    rt[now]=now;
    cnt++;
    for(int i=1;i<=17;i++)
    {
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    for(int i=0;i<g[now].size();i++)
    {
        if(g[now][i]==f) continue;
        dfs(g[now][i],now,dep+1);
    }
}

int lca(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=17;i>=0;i--) if(deep[fa[x][i]]>=deep[y]) x=fa[x][i];
    if(x==y) return y;
    for(int i=17;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int push_up(int now)
{
    if(tr[rson].sum>tr[lson].sum)
    {
        tr[now].sum=tr[rson].sum;
        tr[now].val=tr[rson].val;
    }
    else
    {
        tr[now].sum=tr[lson].sum;
        tr[now].val=tr[lson].val;
    }
}

int update(int &now,int l,int r,int pos,int v)
{
    if(!now) now=++cnt;
    if(l==r)
    {
        tr[now].sum+=v;
        tr[now].val=l;
        return 0;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(lson,l,mid,pos,v);
    else update(rson,mid+1,r,pos,v);
    push_up(now);
}

int merge(int now,int a,int l,int r)
{
    if(!now) return a;
    if(!a) return now;
    if(l==r)
    {
        tr[now].sum+=tr[a].sum;
        tr[now].val=l;
        return now;
    }
    int mid=(l+r)>>1;
    lson=merge(lson,tr[a].l,l,mid);
    rson=merge(rson,tr[a].r,mid+1,r);
    push_up(now);
    return now;
}

int dfs2(int now,int f)
{
    for(int i=0;i<g[now].size();i++)
    {
        if(g[now][i]==f) continue;
        dfs2(g[now][i],now);
        merge(rt[now],rt[g[now][i]],1,100000);
    }
    for(int i=0;i<op1[now].size();i++)
    {
        update(rt[now],1,100000,op1[now][i],1);
    }
    for(int i=0;i<op2[now].size();i++)
    {
        update(rt[now],1,100000,op2[now][i],-1);
    }
    ans[now]=tr[rt[now]].val;
}

int main()
{
    scanf("%d%d",&n,&m);
    int from,to,cost;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&from,&to);
        g[from].push_back(to);
        g[to].push_back(from);
    }
    dfs(1,0,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&from,&to,&cost);
        int ttt=lca(from,to);
        op1[from].push_back(cost);
        op1[to].push_back(cost);
        op2[ttt].push_back(cost);
        if(fa[ttt][0]) op2[fa[ttt][0]].push_back(cost);
    }
    dfs2(1,0);
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",ans[i]);
    }
}      

這題的話主要是差分的思想，把每條覆寫路徑離線下來，分解成(u,lca(u,v))(u,lca(u,v))(u,lca(u,v)),(v,lca(u,v))(v,lca(u,v))(v,lca(u,v))兩條路徑，在uuu點和vvv點将zzz位置+1+1+1,在lca(u,v)lca(u,v)lca(u,v)和fa(lca(u,v))fa(lca(u,v))fa(lca(u,v))的位置分别−1-1−1就可以了。每個點直接查詢最大值，即為答案。