首页 > 代码库 > hdu4366 Successor
hdu4366 Successor
好题! 但是感觉题目描述不是很清楚
这题只是询问开除某人后,他的下属中谁会替代他的位置,不会更新这个位置
要求一个子树中忠诚度最高的人。可以想到dfs树,保留时间戳,每个节点便表示一个区间
那么便可以建树维护最高忠诚度。。。只是要保证能力值也要比被开除者高
那么根据能力值从大到小对员工排序,依次更新。那么可以保证之前更新的节点的能力值都大于当前要查询的节点
这里要注意一点,能力值相同的员工要同时查询和更新
最后一点是。。。按理说更新时应该更新这个员工表示的区间 但是这样会超时
其实只用更新此员工区间的第一个值就可以了,因为查询的时候是员工表示的区间,那么必然可以查询到更新的这个值
记得数组开大一点。。。很容易RE
//#pragma comment(linker, "/STACK:102400000,102400000") //HEAD #include <cstdio> #include <cstring> #include <vector> #include <iostream> #include <algorithm> #include <queue> #include <string> #include <set> #include <stack> #include <map> #include <cmath> #include <cstdlib> using namespace std; //LOOP #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FED(i, b, a) for(int i = (b); i>= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) //STL #define PB push_back //INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) #define RS(s) scanf("%s", s) #define FF(i, a, b) for(int i = (a); i < (b); ++i) #define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i) #define CPY(a, b) memcpy(a, b, sizeof(a)) #define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++) #define EQ(a, b) (fabs((a) - (b)) <= 1e-10) #define ALL(c) (c).begin(), (c).end() #define SZ(V) (int)V.size() #define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p) #define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q) #define WI(n) printf("%d\n", n) #define WS(s) printf("%s\n", s) #define sqr(x) x * x #define LL(x) ((x) << 1) #define RR(x) ((x) << 1 | 1) typedef vector <int> VI; typedef unsigned long long ULL; typedef long long LL; const int INF = 0x3f3f3f3f; const int maxn = 50010; const double eps = 1e-10; const LL MOD = 1e9 + 9; int n, m, dfs_c; int s[maxn], e[maxn]; int ans[maxn]; map<int, int> mm; struct Node{ int id, loy, ab; bool operator<(const Node& x) const{ if (ab != x.ab) return ab > x.ab; return id < x.id; } }a[maxn]; struct Seg{ int l, r, num; }seg[maxn * 5]; VI t[maxn]; void dfs(int u, int fa) { s[u] = ++dfs_c; REP(i, t[u].size()) { int v = t[u][i]; if (v != fa) dfs(v, u); } e[u] = ++dfs_c; } void build(int l, int r, int rt ) { seg[rt].num = -1; seg[rt].l = l, seg[rt].r = r; if (l == r) return; int mid = (l + r) >> 1; build(l, mid, LL(rt)); build(mid + 1, r, RR(rt)); } void update(int pos, int val, int rt) { if (seg[rt].l == seg[rt].r && seg[rt].l == pos) { // cout << "pos " << pos << ' ' << val<< endl; seg[rt].num = val; return; } int mid = (seg[rt].l + seg[rt].r) >> 1; if (pos <= mid) update(pos, val, LL(rt)); else update(pos, val, RR(rt)); seg[rt].num = max(seg[LL(rt)].num, seg[RR(rt)].num); } int query(int l, int r, int rt) { if (seg[rt].l == l && seg[rt].r == r) return seg[rt].num; int mid = (seg[rt].l + seg[rt].r) >> 1; if (r <= mid) return query(l, r, LL(rt)); else if (l > mid) return query(l, r, RR(rt)); return max(query(l, mid, LL(rt)), query(mid + 1, r, RR(rt))); } int main() { int T; RI(T); while (T--) { RII(n, m); REP(i, n + 1) t[i].clear(); dfs_c = 0; mm.clear(); int x, y, z; a[0].id = 0, a[0].loy = -1, a[0].ab = -1; FE(i, 1, n - 1) { RIII(x, y, z); t[x].PB(i); a[i].loy = y, a[i].ab = z, a[i].id = i; mm[y] = i; } dfs(0, -1); // cout << "dfs Done" << endl; build(1, dfs_c, 1); // cout << "build Done" << endl; sort(a, a + n); CLR(ans, -1); for (int i = 0, j; i < n; i = j) { j = i; while (j < n && a[j].ab == a[i].ab) { int tmp = query(s[a[j].id], e[a[j].id], 1); if (mm.count(tmp)) ans[a[j].id] = mm[tmp]; // cout << tmp << endl; j++; } for (int k = i; k < j; k++) update(s[a[k].id], a[k].loy, 1); // for (int k = 1; k < 3 * dfs_c; k++) // printf(" L: %d R:%d num:%d\n", seg[k].l, seg[k].r , seg[k].num); } while (m--) { RI(x); WI(ans[x]); } } return 0; } /* */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。