Codechef 14.5 ANUDTQ Splay+DFS序
题目大意：
给定一棵$n$个点的有根树，有$m$次询问，每次可以以某个树中的点为父亲新加一个叶子节点，也可以删除以某个点为根的子树中的所有点，也可以将以某个点为根的子树中的所有节点的权值全部加上一个数，也可以询问某个子树内所有节点的权值和。
算法讨论：
我们维护树的DFS序，这样每棵子树中的所有节点在DFS序中都是连续一段。
但这道题目中还能加点和删除子树，我们使用Splay树动态维护DFS入栈出栈序，不难发现删除子树就是将序列中的连续一段删除，加点就是将一个节点的入栈出栈序插入他的父亲的入栈序之后。
修改和询问利用延迟标记实现即可。
时空复杂度：
时间复杂度$O(m\log n)$，空间复杂度$O(n+m)$。
代码：
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int getc() {
static const int L = 1 << 15;
static char buf[L], *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, L, stdin);
if (S == T)
return EOF;
}
return *S++;
}
int getint() {
static int c, x, sign;
while (!isdigit(c = getc()) && c != '-');
sign = c == '-' ? -1 : 1;
x = c == '-' ? 0 : c - '0';
while (isdigit(c = getc()))
x = (x << 1) + (x << 3) + c - '0';
return x * sign;
}
#define N 100010
#define ls ch[0]
#define rs ch[1]
struct Node {
Node *ch[2], *pa;
int c, v, sumd, d, siz;
ll ans;
Node() : sumd(0), d(0), siz(0), ans(0) {}
bool sd() {
return this == pa->rs;
}
void up() {
sumd = ls->sumd + d + rs->sumd;
ans = ls->ans + rs->ans + v * d;
siz = ls->siz + 1 + rs->siz;
}
void addit(int _c) {
c += _c;
v += _c;
ans += _c * sumd;
}
void sc(Node *p, bool d) {
ch[d] = p;
p->pa = this;
}
void down();
}mem[N << 1], *G = mem, Tnull, *null = &Tnull, *lnode[N], *rnode[N], *Root;
Node *newnode(int _v, int _d) {
G->ls = G->rs = G->pa = null;
G->c = 0;
G->v = _v;
G->sumd = G->d = _d;
G->ans = _v * _d;
G->siz = 1;
return G++;
}
void Node::down() {
if (c != 0) {
if (ls != null)
ls->addit(c);
if (rs != null)
rs->addit(c);
c = 0;
}
}
void Rot(Node *p) {
Node *fa = p->pa;
bool d = p->sd();
fa->pa->sc(p, fa->sd());
fa->sc(p->ch[!d], d);
fa->up();
p->sc(fa, !d);
if (fa == Root)
Root = p;
}
void downpath(Node *p) {
static Node *stack[N];
static int top;
top = 0;
while (p != null) {
stack[top++] = p;
p = p->pa;
}
while (top--)
stack[top]->down();
}
void Splay(Node *p, Node *anc) {
downpath(p);
while (p->pa != anc) {
if (p->pa->pa == anc)
Rot(p);
else
Rot(p->sd() == p->pa->sd() ? p->pa : p), Rot(p);
}
p->up();
}
Node *kth(Node *p, int k) {
while (1) {
//p->down();
if (k <= p->ls->siz)
p = p->ls;
else if (k > p->ls->siz + 1)
k -= p->ls->siz + 1, p = p->rs;
else
return p;
}
}
int calRank(Node *p) {
Splay(p, null);
return p->ls->siz + 1;
}
void get(int tl, int tr) {
static Node *p, *q;
p = kth(Root, tl);
Splay(p, null);
q = kth(Root, tr);
Splay(q, p);
}
void add(int x, int c) {
get(calRank(lnode[x]) - 1, calRank(rnode[x]) + 1);
Root->rs->ls->addit(c);
Root->rs->up();
Root->up();
}
void del(int x) {
get(calRank(lnode[x]) - 1, calRank(rnode[x]) + 1);
Root->rs->ls = null;
Root->rs->up();
Root->up();
}
ll query(int x) {
get(calRank(lnode[x]) - 1, calRank(rnode[x]) + 1);
return Root->rs->ls->ans;
}
void insertAfter(Node *p, Node *q) {
static int rank;
rank = calRank(p);
get(rank, rank + 1);
Root->rs->sc(q, 0);
Root->rs->up();
Root->up();
}
void insert(int x, int v, int fa) {
lnode[x] = newnode(v, 1);
rnode[x] = newnode(0, 0);
insertAfter(lnode[fa], lnode[x]);
insertAfter(lnode[x], rnode[x]);
}
void init() {
Root = newnode(0, 0);
Root->sc(newnode(0, 0), 1);
Root->up();
}
int w[N];
int head[N], nxt[N << 1], to[N << 1];
void addedge(int a, int b) {
static int q = 1;
to[q] = b;
nxt[q] = head[a];
head[a] = q++;
}
void make(int a, int b) {
addedge(a, b);
addedge(b, a);
}
Node *last;
void dfs(int x, int fa) {
insertAfter(last, lnode[x] = newnode(w[x], 1));
last = lnode[x];
for (int j = head[x]; j; j = nxt[j])
if (to[j] != fa)
dfs(to[j], x);
insertAfter(last, rnode[x] = newnode(0, 0));
last = rnode[x];
}
int main() {
//system("ANUDTQ_gen");
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
int n = getint(), i;
for (i = 0; i < n; ++i)
w[i] = getint();
int u, v;
for (i = 1; i < n; ++i) {
u = getint();
v = getint();
make(u, v);
}
init();
last = Root;
dfs(0, -1);
ll lastans = 0;
int type, key, value, m = getint();
while (m--) {
type = getint();
key = (int)(lastans + getint());
//key = getint();
if (type == 1) {
value = getint();
insert(n, value, key);
++n;
}
else if (type == 2) {
value = getint();
add(key, value);
}
else if (type == 3)
del(key);
else
printf("%I64d\n", lastans = query(key));
}
return 0;
}
评论 (0)