BZOJ3786 星系探索
前两天还在YY动态DFS序呢，这就冒了一个出来。
动态DFS序的郁闷之处在于不好维护dfs序上的end。而把反括号建出来正好能解决这个问题。
然后就splay写得飞慢不知道怎么回事。
用两个栈就可以迭代做出括号序列，自己YY出来的给自己赞一个。
然后是目前最长的代码和倒数第二慢的时间。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
int _d_;
#define readInt(_x_) { \
int &_s_ = _x_; \
while (!isdigit(_d_ = getchar())); \
_s_ = 0; \
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \
}
#define readOpt(_x_) { \
while (!isupper(_d_ = getchar())); \
_x_ = _d_; \
}
typedef long long qw;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
struct edge {
int t;
edge *next;
};
struct splay_node {
int ls, rs, pt, sz, x;
qw v, a, s;
};
const int maxn = 200009;
int n, m, w[maxn];
int fa[maxn], dfb[maxn], dfe[maxn], dfo[maxn];
edge *ep, *head[maxn];
void dfsBuild() {
static int sa[maxn], sb[maxn];
int ta = 1, tb = 0, dfn = 0;
sa[ta] = 1;
memset(dfb, 0, sizeof(dfb));
while (ta) {
int p = sa[ta --];
while (tb && sb[tb] != fa[p])
dfe[sb[tb --]] = ++ dfn;
sb[++ tb] = p;
dfb[p] = ++ dfn;
for (edge* e = head[p]; e; e = e-> next)
sa[++ ta] = e-> t;
}
while (tb)
dfe[sb[tb --]] = ++ dfn;
for (int i = 1; i <= n; ++ i)
dfo[dfb[i]] = i, dfo[dfe[i]] = -i;
}
#define lRot(_q_) { \
int _p_ = t[_q_]. pt, _a_ = t[_p_]. pt; \
if (_a_) { \
if (_p_ == t[_a_]. ls) \
t[_a_]. ls = _q_; \
else \
t[_a_]. rs = _q_; \
} \
if (t[_q_]. rs) \
t[t[_q_]. rs]. pt = _p_; \
t[_p_]. ls = t[_q_]. rs; \
t[_q_]. rs = _p_; \
t[_q_]. pt = _a_; \
t[_p_]. pt = _q_; \
update(_p_); \
update(_q_); \
}
#define rRot(_q_) { \
int _p_ = t[_q_]. pt, _a_ = t[_p_]. pt; \
if (_a_) { \
if (_p_ == t[_a_]. ls) \
t[_a_]. ls = _q_; \
else \
t[_a_]. rs = _q_; \
} \
if (t[_q_]. ls) \
t[t[_q_]. ls]. pt = _p_; \
t[_p_]. rs = t[_q_]. ls; \
t[_q_]. ls = _p_; \
t[_q_]. pt = _a_; \
t[_p_]. pt = _q_; \
update(_p_); \
update(_q_); \
}
#define update(_p_) { \
t[_p_]. sz = t[t[_p_]. ls]. sz + t[t[_p_]. rs]. sz + t[_p_]. x; \
t[_p_]. s = t[t[_p_]. ls]. s + t[t[_p_]. rs]. s + t[_p_]. v + t[_p_]. a * t[_p_]. sz; \
}
#define pushDown(_p_) { \
if (t[_p_]. a) { \
if (t[_p_]. ls) { \
t[t[_p_]. ls]. a += t[_p_]. a; \
update(t[_p_]. ls); \
} \
if (t[_p_]. rs) { \
t[t[_p_]. rs]. a += t[_p_]. a; \
update(t[_p_]. rs); \
} \
if (t[_p_]. x > 0) \
t[_p_]. v += t[_p_]. a; \
else \
t[_p_]. v -= t[_p_]. a; \
t[_p_]. a = 0; \
} \
}
struct splay_tree {
splay_node t[maxn];
int cr, n;
splay_tree() {
t[0]. sz = 0;
t[0]. s = 0;
}
void dpath(int p) {
static int stc[maxn];
int tst = 1;
stc[1] = p;
for (; t[stc[tst]]. pt; ++ tst)
stc[tst + 1] = t[stc[tst]]. pt;
for (; tst; -- tst)
pushDown(stc[tst]);
}
void splay(int q) {
dpath(q);
while (t[q]. pt) {
int p = t[q]. pt, a = t[p]. pt;
if (!a || !t[a]. pt) {
if (q == t[p]. ls) {
lRot(q);
}
else {
rRot(q);
}
}
else {
if (p == t[a]. ls) {
if (q == t[p]. ls) {
lRot(p);
lRot(q);
}
else {
rRot(q);
lRot(q);
}
}
else {
if (q == t[p]. rs) {
rRot(p);
rRot(q);
}
else {
lRot(q);
rRot(q);
}
}
}
}
cr = q;
}
inline int build(int l, int r, int pt = 0) {
if (l >= r)
return 0;
int p = (l + r) >> 1;
t[p]. pt = pt;
t[p]. v = ((dfo[p] > 0) ? w[dfo[p]] : -w[-dfo[p]]);
t[p]. x = ((dfo[p] > 0) ? 1 : -1);
t[p]. a = 0;
t[p]. ls = build(l, p, p);
t[p]. rs = build(p + 1, r, p);
update(p);
if (!pt)
cr = p, n = r;
return p;
}
int tmax(int p) {
while (t[p]. rs)
p = t[p]. rs;
return p;
}
int tmin(int p) {
while (t[p]. ls)
p = t[p]. ls;
return p;
}
int getRange(int l, int r) {
if (l == 1 && r == n)
return cr;
else if (l == 1) {
splay(r);
int x = tmin(t[r]. rs);
splay(x);
return t[x]. ls;
}
else if (r == n) {
splay(l);
int x = tmax(t[l]. ls);
splay(x);
return t[x]. rs;
}
else {
splay(l);
int x = tmax(t[l]. ls);
splay(r);
int y = tmin(t[r]. rs);
splay(x);
splay(y);
return t[x]. rs;
}
}
inline qw getSum(int q) {
dpath(q);
return t[q]. s;
}
inline void add(int q, int v) {
t[q]. a += v;
update(q);
splay(q);
}
void cut(int q) {
int p = t[q]. pt;
dpath(q);
if (q == t[p]. ls)
t[p]. ls = 0;
else
t[p]. rs = 0;
t[q]. pt = 0;
update(p);
splay(p);
}
void link(int q, int p) {
splay(p);
if (t[p]. rs) {
int x = tmin(t[p]. rs);
splay(x);
}
dpath(p);
t[p]. rs = q;
t[q]. pt = p;
update(p);
splay(q);
}
};
splay_tree t;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
memset(head, 0, sizeof(head));
ep = new edge[n];
for (int i = 2; i <= n; ++ i) {
readInt(fa[i]);
ep-> t = i;
ep-> next = head[fa[i]];
head[fa[i]] = ep ++;
}
for (int i = 1; i <= n; ++ i)
readInt(w[i]);
dfsBuild();
t. build(1, n * 2);
readInt(m);
while (m --) {
char opt;
int x, y;
readOpt(opt);
if (opt == 'Q') {
readInt(x);
y = t. getRange(1, dfb[x]);
printf(lld "\n", t. getSum(y));
}
else if (opt == 'C') {
readInt(x);
readInt(y);
int a = t. getRange(dfb[x], dfe[x]);
t. cut(a);
t. link(a, dfb[y]);
}
else if (opt == 'F') {
readInt(x);
readInt(y);
int a = t. getRange(dfb[x], dfe[x]);
t. add(a, y);
}
}
}
