BZOJ 4003 / Luogu P3261 [JLOI2015]城池攻占 (左偏树)

左偏树裸题,在树上合并儿子传上来的堆,然后小于当前结点防御值的就pop掉,pop的时候统计答案.

修改的话就像平衡树一样打懒标记就行了.

具体见代码

CODE

#include<bits/stdc++.h>
using namespace std;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
    char ch; int flg = 1; for(;!isdigit(ch=getchar());)if(ch=='-')flg=-flg;
    for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;
}
typedef long long LL;
const int MAXN = 300005;
const int MAXM = 300005;
#define lc t[x].ls
#define rc t[x].rs
struct node {
	int ls, rs, d;
	LL v, add_tag, mul_tag;
}t[MAXN];
int n, m, cnt, ans1[MAXN], ans2[MAXM];
int dep[MAXN], fir[MAXN], fa[MAXN], c[MAXM];
LL v[MAXN], a[MAXN], h[MAXN];
struct edge { int to, nxt; }e[MAXN];
inline void add(int u, int v) { e[++cnt] = (edge) { v, fir[u] }, fir[u] = cnt; }
vector<int> here[MAXN];
inline void upd(int x) {
	if(t[lc].d < t[rc].d) swap(lc, rc);
	t[x].d = t[rc].d + 1;
}
inline void mt(int x) {
	if(t[x].mul_tag != 1) { //题目中满足只会乘正数,所以能够用堆维护
		if(lc)
			t[lc].mul_tag *= t[x].mul_tag,
			t[lc].add_tag *= t[x].mul_tag,
			t[lc].v *= t[x].mul_tag;
		if(rc)
			t[rc].mul_tag *= t[x].mul_tag,
			t[rc].add_tag *= t[x].mul_tag,
			t[rc].v *= t[x].mul_tag;
		t[x].mul_tag = 1;
	}
	if(t[x].add_tag) {
		if(lc)
			t[lc].add_tag += t[x].add_tag,
			t[lc].v += t[x].add_tag;
		if(rc)
			t[rc].add_tag += t[x].add_tag,
			t[rc].v += t[x].add_tag;
		t[x].add_tag = 0;
	}
}
int merge(int x, int y){
	if(!x || !y) return x + y;
	mt(x), mt(y);
	if(t[x].v > t[y].v) swap(x, y);
	t[x].rs = merge(t[x].rs, y);
	upd(x);
	return x;
}
int pop(int x) { mt(x);
	int l = t[x].ls, r = t[x].rs;
	t[x].ls = t[x].rs = t[x].add_tag = 0; t[x].mul_tag = 1;
	return merge(l, r);
}
int dfs(int x) {
	int rt = 0;
	while(!here[x].empty())
		rt = merge(rt, here[x].back()), here[x].pop_back();
	for(int i = fir[x]; i; i = e[i].nxt)
		dep[e[i].to] = dep[x] + 1, rt = merge(rt, dfs(e[i].to));
	while(rt && t[rt].v < h[x])
		++ans1[x], ans2[rt] = dep[c[rt]]-dep[x], rt = pop(rt);
	if(rt && x > 1) {
		if(a[x] == 0) t[rt].v += v[x], t[rt].add_tag += v[x];
		else t[rt].v *= v[x], t[rt].add_tag *= v[x], t[rt].mul_tag *= v[x];
 	}
	return rt;
}

int main() {
	read(n), read(m); t[0].d = -1;
	for(int i = 1; i <= n; ++i) read(h[i]);
	for(int i = 2; i <= n; ++i) read(fa[i]), read(a[i]), read(v[i]), add(fa[i], i);
	for(int i = 1; i <= m; ++i) read(t[i].v), read(c[i]), here[c[i]].push_back(i), t[i].mul_tag = 1;
	int root = dfs(1);
	while(root) ans2[root] = dep[c[root]] + 1, root = pop(root); //不要忘了有打通关了的骑士
	for(int i = 1; i <= n; ++i) printf("%d
", ans1[i]);
	for(int i = 1; i <= m; ++i) printf("%d
", ans2[i]);
}