hdu4366 Successor-白红宇

hdu4366 Successor

阅读量：7222 次

发布时间：2019-06-29

本文共 3682 字，大约阅读时间需要 12 分钟。

好题。可是感觉题目描写叙述不是非常清楚

这题仅仅是询问开除某人后，他的下属中谁会替代他的位置。不会更新这个位置

要求一个子树中忠诚度最高的人。

能够想到dfs树。保留时间戳。每一个节点便表示一个区间

那么便能够建树维护最高忠诚度。。。仅仅是要保证能力值也要比被开除者高

那么依据能力值从大到小对员工排序，依次更新。那么能够保证之前更新的节点的能力值都大于当前要查询的节点

这里要注意一点，能力值同样的员工要同一时候查询和更新

最后一点是。。

。按理说更新时应该更新这个员工表示的区间可是这样会超时

事实上仅仅用更新此员工区间的第一个值就能够了，由于查询的时候是员工表示的区间。那么必定能够查询到更新的这个值

记得数组开大一点。。。非常easyRE

//#pragma comment(linker, "/STACK:102400000,102400000")//HEAD#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 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 
                 
                   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
                  
                    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;}/**/

转载地址：http://qoqym.baihongyu.com/

你可能感兴趣的文章