HDU 4366 Successor（DFS序+線段樹）

題目連結

題意

公司裡的每個員工都有一個忠誠度和能力值。

如果把一個員工開除，需要在他的下屬中，找到一個能力值比他高，且忠誠度最大的員工來替代他。

第一行一個整數，表示測試資料組數。

對于每組資料，第一行兩個整數n和m，表示公司的員工數和查詢數。

接下來n-1行，第i行，3個整數，i的上級，忠誠度，能力值。老總的編号為0，所有員工的忠誠度都不一樣。

接下來m行查詢，每行一個整數，表示要開除某個人，輸出替代他的員工編号。如果無法替代，輸出-1.

思路

用DFS序轉為線性存儲，每個人的下級在倆時間戳内。

将每個人按能力值排序。用線段樹維護單點修改，區間查詢的忠誠度最大值。

按能力從大到小，每次先查詢此人的時間戳内忠誠度最大值，如果不存在即-1，存在即表示可被替代，然後單點修改。

由于每個人忠誠度不一樣，可以用map來維護忠誠度與人的編号關系。

有個問題，如果倆人能力值相同，如果先更新兒子節點，那麼查詢會查到父親的值。

是以要先更新父親節點，排序時使能力值相同的人時間戳小的排前面即可。

代碼

#include<bits/stdc++.h>
using namespace std;

#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r

vector<int> e[50005];
map<int, int> mp;
int tot, ma[200005], ans[50005];
struct Node
{
    int lo, ab, l, r;
}data[50005];

bool cmp(Node a, Node b)
{
    if(a.ab != b.ab) return a.ab > b.ab;
    return a.l < b.l;
}

void init(int n)
{
    tot = 0;
    mp.clear();
    mp[-1] = -1;
    for(int i = 0; i <= n; ++i) e[i].clear();
    memset(ma,-1,sizeof(ma));
}

void dfs(int u)
{
    data[u].l = ++tot;
    for(auto v : e[u]) dfs(v);
    data[u].r = tot;
}

void updata(int rt, int l, int r, int ql, int lo)
{
    if(l == r)
    {
        ma[rt] = lo;
        return;
    }
    int mid = (l+r)>>1;
    if(ql <= mid) updata(lson,ql,lo);
    else updata(rson,ql,lo);
    ma[rt] = max(ma[rt<<1], ma[rt<<1|1]);
}

int query(int rt, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr) return ma[rt];
    int mid = (l+r)>>1, tmp = -1;
    if(ql <= mid) tmp = max(tmp, query(lson,ql,qr));
    if(mid < qr) tmp = max(tmp, query(rson,ql,qr));
    return tmp;
}

int main()
{
    int t;
    for(scanf("%d",&t); t; --t)
    {
        int n, m, u;
        scanf("%d%d",&n,&m);
        init(n);
        for(int i = 1; i < n; ++i)
        {
            scanf("%d%d%d",&u,&data[i].lo,&data[i].ab);
            mp[data[i].lo] = i;
            e[u].push_back(i);
        }
        dfs(0);
        sort(data+1,data+n,cmp);
        for(int i = 1; i < n; ++i)
        {
            ans[mp[data[i].lo]] = mp[query(1,1,tot,data[i].l,data[i].r)];
            updata(1,1,tot,data[i].l,data[i].lo);
        }
        for(; m--; printf("%d\n",ans[u])) scanf("%d",&u);
    }
    return 0;
}