首页 > 代码库 > HDU 4366 Successor 分块做法
HDU 4366 Successor 分块做法
http://acm.hdu.edu.cn/showproblem.php?pid=4366
今日重新做了这题的分块,果然是隔太久了,都忘记了。。
首先,用DFS序变成一维的问题
关键是它有两个权值,该如何处理呢?
首先假设我们的DFS序列是List,
那么,对其进行分块。对于每一个块,先按能力排序,用数组tosort[]保存,这样我就可以用O(magic)的时间,就是扫一次这个块,维护出一个数组,mx[i]表示大于等于tosort[i].ablity时,最大的忠诚度。
那么我查询的时候,就可以,如果不在块里的,暴力,否则,因为每一个块已经排好序,那么我可以二分出一个位置,找到第一个能力值大于等于所查询的val,那么mx[pos]是答案,因为mx[pos]就表示大于等于这个位置的能力值,所拥有的最大忠诚度。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 50000 + 20; struct Edge { int u, v, w; int tonext; }e[2 * maxn]; int num; int first[maxn + 20]; int getid[1000000 + 20]; struct node { int loy, abi; bool operator < (const struct node & rhs) const { return abi < rhs.abi; } }a[maxn], List[maxn], tosort[maxn]; void addEgde(int u, int v) { ++num; e[num].u = u; e[num].v = v; e[num].tonext = first[u]; first[u] = num; } int DFN; int L[maxn], R[maxn]; bool vis[maxn]; void dfs(int cur) { L[cur] = DFN; for (int i = first[cur]; i; i = e[i].tonext) { int v = e[i].v; // assert(vis[v] == false); // vis[v] = true; ++DFN; List[DFN] = tosort[DFN] = a[v]; dfs(v); } R[cur] = DFN; } int magic; int mx[maxn]; int tofind(int begin, int end, int val) { // cout << begin << " " << end << " ***" << endl; if (tosort[end].abi <= val) return -1; if (tosort[begin].abi > val) return mx[begin]; while (begin <= end) { int mid = (begin + end) >> 1; if (tosort[mid].abi > val) { end = mid - 1; } else begin = mid + 1; } return mx[begin]; } void work() { int n, m; cin >> n >> m; magic = (int)sqrt(n * 1.0); for (int i = 1; i <= n - 1; ++i) { int fa; cin >> fa >> a[i].loy >> a[i].abi; getid[a[i].loy] = i; addEgde(fa, i); } dfs(0); // for (int i = 0; i <= n - 1; ++i) { // cout << L[i] << " " << R[i] << endl; // } for (int i = 0; i < n; i += magic) { int j = i + magic; if (j > n) break; sort(tosort + i, tosort + j); mx[j - 1] = tosort[j - 1].loy; for (int k = j - 2; k >= i; --k) { if (tosort[k].loy < mx[k + 1]) { mx[k] = mx[k + 1]; } else mx[k] = tosort[k].loy; } // for (int k = i; k < i + magic; ++k) { // cout << mx[k] << endl; // } } while (m--) { int id; cin >> id; int val = a[id].abi; int begin = L[id], end = R[id]; // cout << begin << " " << end << " ***" << endl; int ans = -1; for (int i = begin + 1; i <= end;) { if (i % magic == 0 && i + magic <= end) { ans = max(ans, tofind(i, i + magic - 1, val)); i += magic; } else { if (List[i].abi > val && ans < List[i].loy) { ans = List[i].loy; } ++i; } } if (ans == -1) { cout << -1 << endl; } else cout << getid[ans] << endl; } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif IOS; a[0].abi = a[0].loy = -1; List[0] = tosort[0] = a[0]; int t; cin >> t; while (t--) { DFN = 0; num = 0; memset(mx, -1, sizeof mx); memset(first, 0, sizeof first); work(); } return 0; }
HDU 4366 Successor 分块做法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。