BZOJ3435 [Wc2014]紫荆花之恋

想起去年在考场上完全没有思路不想写数据结构于是骗了30分。现在想想当初还是naive。

这题看上去就是点分治。因为要动态加点所以要动态。然后利用替罪羊树的方法重构树上的一团东西（不能叫团，否则命名重复了）。

本来以为要写很久，结果也没写多久。奇怪的是，把maintain展开到insert里面之后就跑得飞快了，否则过不到而且根本跑不下来9和10。又丑了郁闷。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;

const int buf_len = 4000;
const size_t buf_size = buf_len * sizeof(char);
char buf[buf_len], *bufb(buf), *bufe(buf + 1);
#define readBuf() { \
	if (++ bufb == bufe) \
		bufe = (bufb = buf) + fread(buf, 1, buf_size, stdin); \
}
#define readInt(_x_) { \
	register int _s_(0); \
	do { \
		readBuf(); \
	} while (!isdigit(*bufb)); \
	do { \
		_s_ = _s_ * 10 + *bufb - 48; \
		readBuf(); \
	} while (isdigit(*bufb)); \
	_x_ = _s_; \
}

struct edge {
	int t, v;
	edge *next;
};
struct sbt_node {
	int vl, sz;
	sbt_node *ls, *rs;
};

typedef long long dint;

#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define _l (long long int)

const int maxn = 100009;
const int fmod = 1e9;
const int maxl = 19;
const int maxnd = maxn * maxl * 2;
const int balc = 3;
const double ublim = 0.9;
const int inf = 0x3f3f3f3f;

dint lans;
int n;
int ath[maxn][maxl], drt[maxn], dep[maxn];
int bd[maxn], bsz[maxn], bfa[maxn], br[maxn], r[maxn];
int stsz[maxn], vis[maxn], vist;
sbt_node slst[maxnd], *sstc[maxnd], **sp, *brt[maxn], *prt[maxn];
edge *head[maxn], elst[maxn << 1], *ep(elst);

void pre() {
	for (int i = 0; i < maxnd; ++ i) {
		sstc[i] = slst + i;
		slst[i]. ls = slst[i]. rs = 0;
	}
	sp = sstc;
	vist = 0;
	memset(vis, 0, sizeof(vis));
}

inline void addEdge(int u, int v, int w) {
	ep-> t = v;
	ep-> v = w;
	ep-> next = head[u];
	head[u] = ep ++;
}

#define szof(_p_) ((_p_)?(_p_->sz):0)
inline sbt_node* allocNode() {
	static sbt_node* ret;
	ret = *(sp ++);
	if (ret-> ls)
		*(-- sp) = ret-> ls;
	if (ret-> rs)
		*(-- sp) = ret-> rs;
	return ret;
}
inline void lRot(sbt_node* &p) {
	register sbt_node* q(p-> ls);
	p-> ls = q-> rs;
	q-> rs = p;
	q-> sz = p-> sz;
	p-> sz = szof(p-> ls) + szof(p-> rs) + 1;
	p = q;
}
inline void rRot(sbt_node* &p) {
	register sbt_node* q(p-> rs);
	p-> rs = q-> ls;
	q-> ls = p;
	q-> sz = p-> sz;
	p-> sz = szof(p-> ls) + szof(p-> rs) + 1;
	p = q;
}
inline void sbtIns(sbt_node* &p, int v0) {
	if (!p) {
		p = allocNode();
		p-> ls = p-> rs = 0;
		p-> sz = 1;
		p-> vl = v0;
	}
	else {
		++ p-> sz;
		if (v0 < p-> vl) {
			sbtIns(p-> ls, v0);
			if (szof(p-> ls) > szof(p-> rs) + balc)
				lRot(p);
		}
		else {
			sbtIns(p-> rs, v0);
			if (szof(p-> ls) + balc < szof(p-> rs))
				rRot(p);
		}
	}
}
int sbtCntLower(sbt_node* p, int v0) {
	int s(0);
	while (p)
		if (v0 < p-> vl)
			p = p-> ls;
		else
			s += szof(p-> ls) + 1, p = p-> rs;
	return s;
}

int LCA(int u, int v) {
	if (dep[u] < dep[v])
		swap(u, v);
	for (int i = maxl - 1; i >= 0; -- i)
		if (dep[ath[u][i]] >= dep[v])
			u = ath[u][i];
	if (u == v)
		return u;
	for (int i = maxl - 1; i >= 0; -- i)
		if (ath[u][i] ^ ath[v][i]) {
			u = ath[u][i];
			v = ath[v][i];
		}
	return ath[u][0];
}
inline int dist(int u, int v) {
	int a(LCA(u, v));
	return drt[u] + drt[v] - drt[a] * 2;
}

void insEach(sbt_node* q, sbt_node* &x, int mn) {
	static sbt_node* stc[maxn];
	int tst(1);
	stc[1] = q;
	while (tst) {
		sbt_node* p(stc[tst --]);
		sbtIns(x, p-> vl + mn);
				if (p-> ls)
			stc[++ tst] = p-> ls;
		if (p-> rs)
			stc[++ tst] = p-> rs;
	}
}
int build(int pbd, int pbr, int pbf) {
	static int q[maxn], fr[maxn], dst[maxn];
	int hd(0), tl(1), ct(0), cs(inf);
	q[0] = pbr;
	fr[pbr] = 0;
	dst[pbr] = 0;
	while (hd < tl) {
		int p(q[hd ++]);
		for (edge* e = head[p]; e; e = e-> next)
			if (bd[e-> t] == inf && e-> t != fr[p]) {
				fr[e-> t] = p;
				dst[e-> t] = dst[p] + e-> v;
				q[tl ++] = e-> t;
			}
	}
	for (int ti = tl - 1, p; ti >= 0; -- ti) {
		int ms(1);
		p = q[ti];
		stsz[p] = 1;
		for (edge* e = head[p]; e; e = e-> next)
			if (bd[e-> t] == inf && e-> t != fr[p]) {
				stsz[p] += stsz[e-> t];
				if (ms < stsz[e-> t])
					ms = stsz[e-> t];
			}
		if (ms < tl - stsz[p])
			ms = tl - stsz[p];
		if (ms < cs) {
			cs = ms;
			ct = p;
		}
	}
	for (int ti = 0, p; ti < tl; ++ ti) {
		p = q[ti];
		sbtIns(prt[ct], dst[p] - r[p]);
			}
	bd[ct] = pbd;
	bsz[ct] = tl;
	bfa[ct] = pbf;
	br[ct] = pbr;
	sbtIns(brt[ct], -r[ct]);
		for (edge* e = head[ct]; e; e = e-> next)
		if (bd[e-> t] == inf) {
			int nr(build(pbd + 1, e-> t, ct));
			insEach(prt[nr], brt[ct], e-> v);
		}
	return ct;
}

void rebuild(int p0, int pbd, int pbr, int pbf) {
	static int q[maxn];
	int hd(0), tl(1);
	++ vist;
	vis[p0] = vist;
	q[0] = p0;
	while (hd < tl) {
		int p(q[hd ++]);
		*(-- sp) = brt[p];
		*(-- sp) = prt[p];
		brt[p] = 0;
		prt[p] = 0;
		for (edge* e = head[p]; e; e = e-> next)
			if (bd[e-> t] > pbd && vis[e-> t] < vist) {
				vis[e-> t] = vist;
				q[tl ++] = e-> t;
			}
	}
	for (int i = 0; i < tl; ++ i)
		bd[q[i]] = inf;
	build(pbd, pbr, pbf);
}

void addNode(int p) {
	brt[p] = 0;
	sbtIns(brt[p], -r[p]);
		prt[p] = 0;
	sbtIns(prt[p], -r[p]);
		if (p == 1) {
		bd[p] = 1;
		bsz[p] = 1;
		bfa[p] = 0;
		br[p] = 1;
	}
	else {
		register int fa(ath[p][0]);
		bd[p] = bd[fa] + 1;
		bsz[p] = 1;
		bfa[p] = fa;
		br[p] = p;
		int q(fa), l(p), ubp, dt(0);
		double ubv(0);
		while (q) {
			++ bsz[q];
			if ((double)bsz[l] / bsz[q] > ubv) {
				ubv = (double)bsz[l] / bsz[q];
				ubp = q;
			}
			int d0(dist(p, q));
			sbtIns(brt[q], d0 - r[p]);
			sbtIns(prt[q], dist(br[q], p) - r[p]);
			dt += sbtCntLower(brt[q], r[p] - d0) - sbtCntLower(prt[l], r[p] - d0 - dist(br[l], q));
			l = q;
			q = bfa[q];
		}
		lans += dt;
		if (ubv > ublim)
			rebuild(ubp, bd[ubp], br[ubp], bfa[ubp]);
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	pre();
	readInt(n);
	readInt(n);
	lans = 0;
	for (int i = 1; i <= n; ++ i) {
		int fa;
		readInt(fa);
		readInt(drt[i]);
		readInt(r[i]);
		if (i > 1) {
			fa ^= lans % fmod;
			dep[i] = dep[fa] + 1;
			addEdge(fa, i, drt[i]);
			addEdge(i, fa, drt[i]);
			drt[i] += drt[fa];
			ath[i][0] = fa;
			for (int j = 1; j < maxl; ++ j)
				ath[i][j] = ath[ath[i][j - 1]][j - 1];
		}
		else {
			dep[i] = 1;
		}
		addNode(i);
		printf(lld "\n", lans);
	}
}