首页 > 代码库 > hdu 4366 Successor - CDQ分治 - 线段树 - 树分块
hdu 4366 Successor - CDQ分治 - 线段树 - 树分块
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.
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.
Sample Input
13 20 100 991 101 10012
Sample Output
2-1
题目大意 给定一棵树，每个点有两个权值，忠诚度和能力值，每次询问点x的子树中能力值大于它，忠诚度最高的一位的编号。
Solution 1 树分块
因为查询的时候，查询一个节点的子树实际上是等于查询一段区间内的数据，所以考虑对dfs序进行分块。
按照dfs序进行分块，块内按忠诚度进行排序，再记录后缀忠诚度最大值。
根据常用套路，每次查询，对于块两端部分，暴力for。中间每个块lower_bound upper_bound一下查询合法的一段，然后用后缀忠诚度最大值进行更新答案就好了。
（这是我比较笨的分块方法）
设块的大小为s，块的数量为c,则总时间复杂度为
Code
1 /** 2 * hdu 3 * Problem#4366 4 * Accepted 5 * Time: 748ms 6 * Memory: 8468k 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 typedef bool boolean; 11 12 typedef class Staff { 13 public: 14 int loy; 15 int abi; 16 int id; 17 18 boolean operator < (Staff b) const { 19 if(abi != b.abi) return abi < b.abi; 20 return loy < b.loy; 21 } 22 }Staff; 23 24 boolean operator < (const int& x, const Staff& s) { 25 return x < s.abi; 26 } 27 28 const int maxcsize = 300; 29 typedef class Chunk { 30 public: 31 int len; 32 Staff sta[maxcsize]; 33 int maxv[maxcsize]; 34 int ans[maxcsize]; 35 36 void init(Staff* lis, int from, int end) { 37 len = end - from; 38 for(int i = from; i < end; i++) 39 sta[i - from] = lis[i]; 40 sort(sta, sta + len); 41 maxv[len] = -1; 42 ans[len] = -1; 43 for(int i = len - 1; i >= 0; i--) { 44 if(sta[i].loy > maxv[i + 1]) 45 maxv[i] = sta[i].loy, ans[i] = sta[i].id; 46 else 47 maxv[i] = maxv[i + 1], ans[i] = ans[i + 1]; 48 } 49 } 50 51 void getAns(int limit, int& rmaxv, int& rans) { 52 int pos = upper_bound(sta, sta + len, limit) - sta; 53 if(maxv[pos] > rmaxv) 54 rmaxv = maxv[pos], rans = ans[pos]; 55 } 56 }Chunk; 57 58 int n, m; 59 int cs, cc; 60 vector<int> *g; 61 Staff lis[50005]; 62 Staff *nlis; 63 Chunk chs[300]; 64 65 inline void init() { 66 scanf("%d%d", &n, &m); 67 g = new vector<int>[(n + 1)]; 68 nlis = new Staff[(n + 1)]; 69 for(int i = 1, x; i < n; i++) { 70 scanf("%d%d%d", &x, &lis[i].loy, &lis[i].abi); 71 lis[i].id = i; 72 g[x].push_back(i); 73 } 74 lis[0].loy = lis[0].abi = 23333333; 75 lis[0].id = 0; 76 cs = sqrt(n + 0.5); 77 } 78 79 int cnt; 80 int visitID[50005], exitID[50005]; 81 int visit[50005]; 82 inline void dfs(int node) { 83 visitID[node] = ++cnt; 84 visit[cnt] = node; 85 for(int i = 0; i < (signed)g[node].size(); i++) 86 dfs(g[node][i]); 87 exitID[node] = cnt; 88 } 89 90 inline void init_chunks() { 91 for(int i = 1; i <= n; i++) 92 nlis[i] = lis[visit[i]], nlis[i].id = i; 93 for(cc = 0; cc * cs < n; cc++) 94 chs[cc + 1].init(nlis, cc * cs + 1, min((cc + 1) * cs, n) + 1); 95 } 96 97 inline void solve() { 98 int l, r, x, maxv, ans, lim; 99 while(m--) {100 scanf("%d", &x);101 maxv = -1, ans = -1;102 l = visitID[x], r = exitID[x], lim = lis[x].abi;103 int lid = l / cs + 1, rid = r / cs + 1;104 if(lid == rid) {105 for(int i = l; i <= r; i++)106 if(nlis[i].abi > lim && nlis[i].loy > maxv)107 maxv = nlis[i].loy, ans = i;108 } else {109 // if(x == 992)110 // putchar(‘a‘);111 for(int i = l; i <= lid * cs; i++)112 if(nlis[i].abi > lim && nlis[i].loy > maxv)113 maxv = nlis[i].loy, ans = i;114 for(int i = (rid - 1) * cs + 1; i <= r; i++)115 if(nlis[i].abi > lim && nlis[i].loy > maxv)116 maxv = nlis[i].loy, ans = i;117 for(int i = lid + 1; i < rid; i++)118 chs[i].getAns(lim, maxv, ans);119 }120 printf("%d\n", (ans == -1) ? (-1) : (visit[ans]));121 }122 }123 124 inline void clear() {125 delete[] g;126 delete[] nlis;127 }128 129 int T;130 int main() {131 // freopen("a.in", "r", stdin);132 // freopen("a.out", "w", stdout); 133 scanf("%d", &T);134 while(T--) {135 init();136 cnt = 0;137 dfs(0);138 init_chunks();139 solve();140 clear();141 }142 // fprintf(stderr, "Time: %dms\n", clock());143 return 0;144 }
Solution 2 CDQ分治
每次查询相当于查询满足能力大于某个值，深度优先时间戳在某一段区间内的最大的忠诚度，感觉有那么一点像偏序的问题，所以上CDQ分治乱搞..
分治能力，然后对于能力大于等于mid的节点可能会对能力小于mid的节点做出贡献，所以就用一个线段树维护区间最值，对于能力值大于等于mid的节点就在线段树内将它的深度优先时间戳那一位改为它的忠诚度。对于能力值小于mid的节点x就查询[visitID[x], exitID[x]]的最值就好了。
每次询问O(1)解决。
总时间复杂度
.
由于自己巨懒无比，CDQ分治从来都不手写队列，直接用vector。又因为线段树和STL中的vector常数巨大无比(当然还有我的代码自带某个比较大的常熟)，所以直接上就TLE了。把vector全都改成手写vector才过的。
Code
1 /** 2 * hdu 3 * Problem#4366 4 * Accepted 5 * Time: 842ms 6 * Memory: 18776k 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 const signed int inf = (signed)((1u << 31) - 1); 11 12 typedef class SegTreeNode { 13 public: 14 int val; 15 int maxid; 16 SegTreeNode *l, *r; 17 SegTreeNode():val(-1), maxid(0), l(NULL), r(NULL) { } 18 19 inline void pushUp() { 20 if(l->val > r->val) 21 val = l->val, maxid = l->maxid; 22 else 23 val = r->val, maxid = r->maxid; 24 } 25 }SegTreeNode; 26 27 SegTreeNode pool[200000]; 28 SegTreeNode *top; 29 30 inline SegTreeNode* newnode() { 31 top->val = -1; 32 return top++; 33 } 34 35 typedef class SegTree { 36 public: 37 SegTreeNode* root; 38 39 SegTree():root(NULL) { } 40 SegTree(int n) { 41 build(root, 1, n); 42 } 43 44 void build(SegTreeNode*& node, int l, int r) { 45 node = newnode(); 46 if(l == r) return; 47 int mid = (l + r) >> 1; 48 build(node->l, l, mid); 49 build(node->r, mid + 1, r); 50 } 51 52 void update(SegTreeNode*& node, int l, int r, int idx, int val) { 53 if(l == r) { 54 node->val = val, node->maxid = l; 55 return; 56 } 57 int mid = (l + r) >> 1; 58 if(idx <= mid) update(node->l, l, mid, idx, val); 59 else update(node->r, mid + 1, r, idx, val); 60 node->pushUp(); 61 } 62 63 int query(SegTreeNode*& node, int l, int r, int ql, int qr, int& maxid) { 64 if(l == ql && qr == r) { 65 maxid = node->maxid; 66 return node->val; 67 } 68 int mid = (l + r) >> 1; 69 if(qr <= mid) return query(node->l, l, mid, ql, qr, maxid); 70 if(ql > mid) return query(node->r, mid + 1, r, ql, qr, maxid); 71 int a, b, c; 72 a = query(node->l, l, mid, ql, mid, c); 73 b = query(node->r, mid + 1, r, mid + 1, qr, maxid); 74 if(a > b) maxid = c; 75 return max(a, b); 76 } 77 }SegTree; 78 79 template<typename T> 80 class Vector { 81 protected: 82 int cap; 83 int siz; 84 T* l; 85 public: 86 Vector():l(NULL), cap(0), siz(0) { } 87 88 inline void push_back(T x) { 89 if(l == NULL) { 90 l = new T[4]; 91 cap = 4, siz = 0; 92 } 93 if(siz == cap) { 94 l = (T*)realloc(l, sizeof(T) * cap * 2); //重新申请内存，并拷贝数组 95 cap = cap << 1; 96 } 97 l[siz++] = x; 98 } 99 100 T& operator [] (int pos) {101 return l[pos];102 }103 104 inline int size() {105 return siz;106 }107 108 inline int capt() {109 return cap;110 }111 112 inline void clear() {113 delete[] l;114 l = NULL;115 }116 };117 118 int n, m;119 int valmax;120 Vector<int> *g;121 Vector<int> a233;122 int* loys, *abis;123 SegTree st;124 125 inline void init() {126 scanf("%d%d", &n, &m);127 top = pool;128 g = new Vector<int>[(n + 1)];129 loys = new int[(n + 1)];130 abis = new int[(n + 1)];131 st = SegTree(n);132 loys[0] = inf, abis[0] = inf;133 a233.clear();134 for(int i = 1, x; i < n; i++) {135 scanf("%d%d%d", &x, loys + i, abis + i);136 g[x].push_back(i);137 a233.push_back(i);138 }139 }140 141 int buf[50005];142 void discrete() {143 memcpy(buf, abis, sizeof(int) * n);144 sort(buf, buf + n);145 valmax = unique(buf, buf + n) - buf;146 for(int i = 0; i < n; i++)147 abis[i] = lower_bound(buf, buf + valmax, abis[i]) - buf + 1;148 }149 150 int cnt;151 int visitID[50005], exitID[50005];152 int visit[50005];153 inline void dfs(int node) {154 visitID[node] = ++cnt;155 visit[cnt] = node;156 for(int i = 0; i < (signed)g[node].size(); i++)157 dfs(g[node][i]);158 exitID[node] = cnt;159 }160 161 int maxvals[50005];162 int ans[50005];163 void CDQDividing(int l, int r, Vector<int>& q) {164 if(q.size() <= 1) return;165 if(l == r) return;166 167 int mid = (l + r) >> 1, a, b;168 169 Vector<int> ql, qr;170 for(int i = 0; i < (signed)q.size(); i++)171 if(abis[q[i]] > mid)172 qr.push_back(q[i]), st.update(st.root, 1, n, visitID[q[i]], loys[q[i]]);173 else174 ql.push_back(q[i]);175 176 for(int i = 0; i < (signed)ql.size(); i++) {177 a = st.query(st.root, 1, n, visitID[ql[i]], exitID[ql[i]], b);178 if(a > maxvals[ql[i]])179 maxvals[ql[i]] = a, ans[ql[i]] = b;180 }181 182 for(int i = 0; i < (signed)qr.size(); i++)183 st.update(st.root, 1, n, visitID[qr[i]], -1);184 185 q.clear();186 CDQDividing(l, mid, ql);187 CDQDividing(mid + 1, r, qr);188 }189 190 inline void solve() {191 cnt = 0;192 dfs(0);193 memset(maxvals, -1, sizeof(int) * (n + 1));194 memset(ans, -1, sizeof(int) * (n + 1));195 CDQDividing(1, valmax, a233);196 int x;197 while(m--) {198 scanf("%d", &x);199 printf("%d\n", (ans[x] == -1) ? (-1) : (visit[ans[x]]));200 }201 }202 203 inline void clear() {204 delete[] g;205 delete[] loys;206 delete[] abis;207 }208 209 int T;210 int main() {211 scanf("%d", &T);212 while(T--) {213 init();214 discrete();215 solve();216 clear();217 }218 return 0;219 }
Sulution 3 线段树合并
对于上一种做法，为了满足子树的关系多带了个log，考虑直接dfs，每一个点先访问它的子树，再把子树信息合并起来，就可以满足子树关系了。
现在考虑如何维护子树信息。对能力值开一个值域线段树，记录当前值域内最大的忠诚度。
于是就成功把总时间复杂度优化成
.
然而常熟更大了，所以没有快多少。
Code
1 /** 2 * hdu 3 * Problem#4366 4 * Accepted 5 * Time: 436ms 6 * Memory: 39124k 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 const signed int inf = (signed)((1u << 31) - 1); 11 12 typedef class SegTreeNode { 13 public: 14 int val; 15 int maxid; 16 SegTreeNode *l, *r; 17 SegTreeNode():val(-1), maxid(-1), l(NULL), r(NULL) { } 18 SegTreeNode(SegTreeNode *p):val(-1), maxid(-1), l(p), r(p) { } 19 20 inline void pushUp() { 21 if(l->val > r->val) 22 val = l->val, maxid = l->maxid; 23 else 24 val = r->val, maxid = r->maxid; 25 } 26 }SegTreeNode; 27 28 SegTreeNode pool[1000000]; 29 SegTreeNode null = SegTreeNode(&null); 30 SegTreeNode *top; 31 32 inline SegTreeNode* newnode() { 33 top->val = -1; 34 top->maxid = -1; 35 top->l = top->r = &null; 36 return top++; 37 } 38 39 void merge(SegTreeNode*& a, SegTreeNode* b) { 40 if(b == &null) return; 41 if(a == &null) { 42 a = b; 43 return; 44 } 45 if(b->val > a->val) 46 a->val = b->val, a->maxid = b->maxid; 47 merge(a->l, b->l); 48 merge(a->r, b->r); 49 // a->pushUp(); 50 } 51 52 typedef class SegTree { 53 public: 54 SegTreeNode* root; 55 56 SegTree():root(&null) { } 57 58 void update(SegTreeNode*& node, int l, int r, int idx, int val, int id) { 59 if(node == &null) 60 node = newnode(); 61 if(l == r) { 62 if(val > node->val) 63 node->val = val, node->maxid = id; 64 return; 65 } 66 int mid = (l + r) >> 1; 67 if(idx <= mid) update(node->l, l, mid, idx, val, id); 68 else update(node->r, mid + 1, r, idx, val, id); 69 node->pushUp(); 70 } 71 72 int query(SegTreeNode*& node, int l, int r, int ql, int qr, int& maxid) { 73 if(l == ql && qr == r) { 74 maxid = node->maxid; 75 return node->val; 76 } 77 int mid = (l + r) >> 1; 78 if(qr <= mid) return query(node->l, l, mid, ql, qr, maxid); 79 if(ql > mid) return query(node->r, mid + 1, r, ql, qr, maxid); 80 int a, b, c; 81 a = query(node->l, l, mid, ql, mid, c); 82 b = query(node->r, mid + 1, r, mid + 1, qr, maxid); 83 if(a > b) maxid = c; 84 return max(a, b); 85 } 86 }SegTree; 87 88 const int limval = 1000000; 89 90 int n, m; 91 int valmax; 92 vector<int> *g; 93 int* loys, *abis; 94 95 inline void init() { 96 scanf("%d%d", &n, &m); 97 top = pool; 98 g = new vector<int>[(n + 1)]; 99 loys = new int[(n + 1)];100 abis = new int[(n + 1)];101 loys[0] = inf, abis[0] = inf;102 for(int i = 1, x; i < n; i++) {103 scanf("%d%d%d", &x, loys + i, abis + i);104 g[x].push_back(i);105 }106 }107 108 int buf[50005];109 void discrete() {110 memcpy(buf, abis, sizeof(int) * n);111 sort(buf, buf + n);112 valmax = unique(buf, buf + n) - buf;113 for(int i = 0; i < n; i++)114 abis[i] = lower_bound(buf, buf + valmax, abis[i]) - buf + 1;115 }116 117 int ans[50005];118 int maxv[50005];119 SegTreeNode* dfs(int node) {120 SegTree st;121 // if(node == 10)122 // fprintf(stderr, "gg");123 for(int i = 0; i < (signed)g[node].size(); i++) {124 SegTreeNode* buf = dfs(g[node][i]);125 merge(st.root, buf);126 }127 if(node) {128 maxv[node] = st.query(st.root, 1, n, abis[node] + 1, n, ans[node]);129 st.update(st.root, 1, n, abis[node], loys[node], node);130 } else ans[node] = -1;131 return st.root;132 }133 134 inline void solve() {135 dfs(0);136 int x;137 while(m--) {138 scanf("%d", &x);139 printf("%d\n", (ans[x]));140 }141 }142 143 inline void clear() {144 delete[] g;145 delete[] loys;146 delete[] abis;147 }148 149 int T;150 int main() {151 // freopen("a.in", "r", stdin);152 // freopen("a.out", "w", stdout);153 scanf("%d", &T);154 while(T--) {155 init();156 discrete();157 solve();158 clear();159 }160 return 0;161 }
hdu 4366 Successor - CDQ分治 - 线段树 - 树分块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。