题目1 BZOJ1455 罗马游戏
可并堆 + 并查集维护，是个可并堆的裸题。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 const int N = 1000000 + 5;11 typedef long long ll;12 13 char ss[5];14 int n, m, val[N], fa[N];15 bool sile[N];16 17 inline int read() {18 int x = 0;19 char c = getchar();20 21 while(!isdigit(c)) c = getchar();22 while(isdigit(c)) {23 x = x * 10 + c - '0';24 c = getchar();25 }26 return x;27 }28 29 struct Node {30 int v, dis, l, r;31 32 bool operator < (const Node &a) const {33 return v < a.v;34 }35 }t[N];36 37 int merge(int A, int B) {38 if(A == 0 || B == 0) return A + B;39 if(t[A].v > t[B].v) swap(A, B);40 t[A].r = merge(t[A].r, B);41 if(t[A].r) {42 if(t[t[A].r].dis > t[t[A].l].dis) {43 swap(t[A].r, t[A].l);44 }45 }46 t[A].dis = t[A].r ? t[t[A].r].dis + 1 : 0;47 return A;48 }49 50 int find(int x) {51 return fa[x] == x ? x : (fa[x] = find(fa[x]));52 }53 54 int main() {55 int x, y, fx, fy, p;56 57 n = read();58 for(int i = 1; i <= n; ++ i) t[i].v = read();59 for(int i = 1; i <= n; ++ i) fa[i] = i;60 m = read();61 for(int i = 1; i <= m; ++ i) {62 scanf("%s", ss);63 if(ss[0] == 'M') {64 scanf("%d%d", &x, &y);65 if(sile[x] || sile[y]) continue;66 fx = find(x); fy = find(y);67 if(fx != fy) {68 p = merge(fx, fy);69 fa[fx] = fa[fy] = p;70 }71 }72 else if(ss[0] == 'K') {73 scanf("%d", &x);74 if(sile[x]) {75 puts("0"); continue;76 }77 p = find(x); sile[p] = true;78 printf("%d\n", t[p].v);79 fa[p] = merge(t[p].l, t[p].r);80 fa[fa[p]] = fa[p];81 }82 }83 return 0;84 }
题目2 BZOJ 4003 [JLOI2015]攻占城池
带标记的可并堆，注意的一个问题就是在KILL完根结点之后，把没有KILL掉的点再PUSHDOWN一下。否则你会WA死的。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 const int N = 300000 + 5; 11 typedef long long ll; 12 13 int n, m, cnt; 14 int fa[N], a[N], root[N], head[N]; 15 int tmp[N], city[N], c[N]; 16 int lz[N], gz[N], ans[N]; 17 ll h[N], vv[N], s[N]; 18 19 struct Edge { 20 int from, to, next; 21 }edges[N << 1]; 22 23 struct Node { 24 ll v, mu, ad; 25 int dis, l, r, id; 26 Node() { mu = 1;} 27 bool operator < (const Node &k) const { 28 return v < k.v; 29 } 30 }t[N]; 31 32 void pushdown(int x) { 33 if(!x) return; 34 35 int l = t[x].l, r = t[x].r; 36 37 if(t[x].mu != 1) { 38 if(l) { t[l].v *= t[x].mu; t[l].mu *= t[x].mu; t[l].ad *= t[x].mu;} 39 if(r) { t[r].v *= t[x].mu; t[r].mu *= t[x].mu; t[r].ad *= t[x].mu;} 40 t[x].mu = 1; 41 } 42 if(t[x].ad) { 43 if(l) { t[l].v += t[x].ad; t[l].ad += t[x].ad;} 44 if(r) { t[r].v += t[x].ad; t[r].ad += t[x].ad;} 45 t[x].ad = 0; 46 } 47 if(lz[x]) { 48 if(l) { lz[l] += lz[x]; gz[l] += lz[x];} 49 if(r) { lz[r] += lz[x]; gz[r] += lz[x];} 50 lz[x] = 0; 51 } 52 } 53 54 int merge(int s1, int s2) { 55 if(!s1 || !s2) return s1 + s2; 56 pushdown(s1); pushdown(s2); 57 if(t[s1].v > t[s2].v) swap(s1, s2); 58 t[s1].r = merge(t[s1].r, s2); 59 if(t[s1].r) 60 if(t[t[s1].r].dis > t[t[s1].l].dis) 61 swap(t[s1].r, t[s1].l); 62 t[s1].dis = t[s1].r ? t[t[s1].r].dis + 1 : 0; 63 return s1; 64 } 65 66 void insert(int from, int to) { 67 ++ cnt; 68 edges[cnt].from = from; 69 edges[cnt].to = to; 70 edges[cnt].next = head[from]; 71 head[from] = cnt; 72 } 73 74 void dfs(int x) { 75 for(int i = head[x]; i; i = edges[i].next) { 76 int v = edges[i].to; 77 78 if(v != fa[x]) dfs(v); 79 } 80 while(root[x] && t[root[x]].v < h[x]) { 81 city[x] ++; 82 pushdown(root[x]); 83 ans[t[root[x]].id] = gz[root[x]]; 84 root[x] = merge(t[root[x]].l, t[root[x]].r); 85 } 86 if(root[x]) { 87 if(a[x] == 0) { t[root[x]].v += vv[x]; t[root[x]].ad += vv[x];} 88 else if(a[x] == 1) { t[root[x]].v *= vv[x]; t[root[x]].mu *= vv[x]; t[root[x]].ad *= vv[x];} 89 lz[root[x]] ++; gz[root[x]] ++; 90 root[fa[x]] = merge(root[fa[x]], root[x]); 91 } 92 } 93 94 int main() { 95 scanf("%d%d", &n, &m); 96 for(int i = 1; i <= n; ++ i) scanf("%lld", &h[i]); 97 a[1] = -1; 98 for(int i = 1; i < n; ++ i) { 99 scanf("%d%d%lld", &fa[i + 1], &a[i + 1], &vv[i + 1]);100 insert(i + 1, fa[i + 1]); insert(fa[i + 1], i + 1);101 }102 for(int i = 1; i <= m; ++ i) {103 scanf("%lld%d", &s[i], &c[i]);104 t[i].v = s[i]; t[i].id = i;105 root[c[i]] = merge(root[c[i]], i);106 }107 dfs(1);108 while(root[1]) {109 pushdown(root[1]);110 ans[t[root[1]].id] = gz[root[1]];111 root[1] = merge(t[root[1]].l, t[root[1]].r);112 }113 for(int i = 1; i <= n; ++ i) printf("%d\n", city[i]);114 for(int i = 1; i <= m; ++ i) printf("%d\n", ans[i]);115 return 0;116 }
题目3 BZOJ 2809 APIO dispatching
要注意的一个地方就是在合并堆的时候，由于我们要维护的是一个大根，所以关键字的比较要以两个节点的cost值，而我用的是v值，
所以导致WA了许多遍。题目的思路就是DFS过程中每次把当前点与儿子们合并，然后如果sum值大于lim值就把最大的去掉。一直搞到
最后就可以了。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 typedef long long ll;11 const int N = 100000 + 5;12 13 inline int read() {14 int x = 0;15 char c = getchar();16 17 while(!isdigit(c)) c = getchar();18 while(isdigit(c)) {19 x = x * 10 + c - '0';20 c = getchar();21 }22 return x;23 }24 25 int n, fa[N], head[N], master, cnt, root[N];26 ll cost[N], ship[N], lim, ans;27 28 struct Edge {29 int from, to, next;30 }edges[N << 1];31 32 struct Node {33 ll v; int l, r, sz, dis;34 }t[N];35 36 void insert(int u, int v) {37 ++ cnt;38 edges[cnt].from = u; edges[cnt].to = v;39 edges[cnt].next = head[u]; head[u] = cnt;40 }41 42 int merge(int a, int b) {43 if(!a || !b) return a + b;44 if(cost[a] < cost[b]) swap(a, b);45 t[a].r = merge(t[a].r, b);46 if(t[a].r)47 if(t[t[a].l].dis < t[t[a].r].dis)48 swap(t[a].r, t[a].l);49 t[a].dis = t[a].r ? t[t[a].r].dis + 1 : 0;50 return a;51 }52 53 void dfs(int u) {54 t[u].v = cost[u]; t[u].sz = 1; root[u] = u;55 for(int i = head[u]; i; i = edges[i].next) {56 int v = edges[i].to;57 if(v != fa[u]) {58 dfs(v);59 t[u].v += t[v].v;60 t[u].sz += t[v].sz;61 root[u] = merge(root[u], root[v]);62 }63 }64 while(t[u].v > lim) {65 t[u].v -= cost[root[u]];66 t[u].sz --;67 root[u] = merge(t[root[u]].l, t[root[u]].r);68 }69 ans = max(ans, 1LL * t[u].sz * ship[u]);70 }71 72 int main() {73 n = read(); lim = read();74 for(int i = 1; i <= n; ++ i) {75 fa[i] = read(); cost[i] = read(); ship[i] = read();76 insert(fa[i], i); insert(i, fa[i]);77 if(!fa[i]) master = i;78 }79 dfs(master);80 printf("%lld\n", ans);81 return 0;82 }