Successor
HDU - 4366
Sean owns a company and he is the BOSS.The other Staff has one Superior.every staff has a loyalty and ability.Some times Sean will fire one staff.Then one of the fired man’s Subordinates will replace him whose ability is higher than him and has the highest loyalty for company.Sean want to know who will replace the fired man.
公司裡的每個員工都有一個忠誠度和能力值。如果把一個員工開除，需要在他的下屬中，找到一個能力值比他高，且忠誠度最大的員工來替代他。
Input
In the first line a number T indicate the number of test cases. Then for each case the first line contain 2 numbers n,m (2<=n,m<=50000),indicate the company has n person include Sean ,m is the times of Sean’s query.Staffs are numbered from 1 to n-1,Sean’s number is 0.Follow n-1 lines,the i-th(1<=i<=n-1) line contains 3 integers a,b,c(0<=a<=n-1,0<=b,c<=1000000),indicate the i-th staff’s superior Serial number,i-th staff’s loyalty and ability.Every staff ‘s Serial number is bigger than his superior,Each staff has different loyalty.then follows m lines of queries.Each line only a number indicate the Serial number of whom should be fired.
第一行一個整數，表示測試資料組數。
對于每組資料，第一行兩個整數n和m，表示公司的員工和詢問次數。
接下來n-1行，第i行，3個整數，i的上級，忠誠度，能力值。老總的編号為0,所有員工的忠誠度都不一樣。
接下來m行，每行一個整數，表示要開除某個人，你需要輸出替代他的員工編号。如果不存在，輸出-1.
Output
For every query print a number:the Serial number of whom would replace the losing job man,If there has no one to replace him,print -1.
對于每個要開除的人，你需要輸出替代他的員工編号。如果不存在，輸出-1.
Sample Input
1
3 2
0 100 99
1 101 100
1
2
Sample Output
2
-1
題意：
公司裡自上而下是一個樹形結構。
每個員工都有一個忠誠度和能力值。如果把一個員工開除，需要在他的下屬中，找到一個能力值比他高，且忠誠度最大的員工來替代他。
m個詢問，每行一個整數，表示要開除某個人，你需要輸出替代他的員工編号。如果不存在，輸出-1.
思路：
一棵樹的子樹中，dfs序是連續的。
是以我們先通過dfs來把樹形問題轉為區間問題。
又因為所有員工的忠誠度都不一樣。 是以我們可以用一個map把員工的編号和忠誠度對應起來。
我們先以員工的能力值為名額，降序排序。
然後預處理出所有答案，輸入直接O(1) 輸出結果。
如何預處理出所有員工節點的答案呢？
我們知道推論①：一個員工對他的上司的答案值有影響，當且僅當這個員工的能力值大于他的那個上司的答案值。
那麼我們可以在排序後，
線上段樹中從大到小依次加入員工，
這樣的話我們對一個員工，詢問線段樹中這個員工的dfs序的時間戳區間中的忠誠度的最大值。（區間查詢）
中橫渡對應下編号就是這個員工的答案。
然後把這位員工的忠誠度加入到員工的dfs序的時間戳位置中。（單點更新）
為什麼這樣對？
因為對上面講到的推論①，對其可能有影響的員工已經全部加入到線段樹中了。
他隻需要詢問在自己的下屬員工中（在時間戳區間中）的忠誠度最大值即可。
細節見代碼
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
// #define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int *p);
const int maxn = 50010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int T;
map<int, int> mp;
std::vector<int> son[maxn];
int tree[maxn << 2];
int ans[maxn];
int n, m;
int tot;
void init()
{
repd(i, 1, n * 4) {
tree[i] = -1;
}
tot = 0;
mp.clear();
repd(i, 0, n) {
son[i].clear();
ans[i] = -1;
}
mp[-1] = -1;
}
struct node {
int ab;
int lo;
int id;
int timel;
int timer;
bool operator <(const node &bb )const
{
if (ab != bb.ab) {
return ab > bb.ab;
} else {
return timel < bb.timel;
}
}
} data[maxn];
void dfs(int x)
{
data[x].timel = ++tot;
for (auto y : son[x]) {
dfs(y);
}
data[x].timer = tot;
}
int ask(int rt, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr) {
return tree[rt];
}
int res = -1;
int mid = (l + r) >> 1;
if (ql <= mid) {
res = max(res, ask(rt << 1, l, mid, ql, qr));
}
if (qr > mid) {
res = max(res, ask(rt << 1 | 1, mid + 1, r, ql, qr));
}
return res;
}
void update(int rt, int l, int r, int pos, int val)
{
if (l == r && l == pos) {
tree[rt] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
update(rt << 1, l, mid, pos, val);
}
if (pos > mid) {
update(rt << 1 | 1, mid + 1, r, pos, val);
}
tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &m);
init();
int x;
repd(i, 1, n - 1) {
scanf("%d %d %d", &x, &data[i].lo, &data[i].ab);
data[i].id = i;
mp[data[i].lo] = i;
son[x].push_back(i);
}
dfs(0);
sort(data + 1, data + n);
for (int i = 1; i < n; ++i) {
ans[data[i].id] = mp[ask(1, 1, tot, data[i].timel, data[i].timer)];
update(1, 1, tot, data[i].timel, data[i].lo);
}
while (m--) {
int x;
scanf("%d", &x);
printf("%d\n", ans[x] );
}
}
return 0;
}
inline void getInt(int *p)
{
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
} else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}
轉載于:https://www.cnblogs.com/qieqiemin/p/11494752.html