洛谷 P3348 【[ZJOI2016]大森林】题解
对于操作0，我们可以发现其实完全可以对于每个树都进行操作，因为所有的这样只会使树多长出一些节点，显然我们询问的节点不可能由这些节点拓展而来，因此其路径上必然不存在这些节点，因此这些节点并不会影响询问的答案
对于操作1，我们不可能对区间内每个树都进行操作，因此考虑差分的思想，只对左右端点处进行操作。我们可以将操作2看为：在统计第l棵树上的答案时，将此操作1后加入的节点全部移动到x节点的子树中，再在统计第r+1棵树上的答案时移回来
对于移动全部的节点，我们直接通过建立一个虚点然后整体移动就行
这里注意必须要保证l,r中的树上有x这个节点才行，因此我们需要和操作0中加入了这个节点的树的区间取交
对于询问，我们只需要在完成这棵子树上所有的操作后，统计两点之间的实点个数即可。
由于这个lct是有根的，因此不能makeroot，所以我们采用差分，分别统计u，v，lca到根上的实点个数即可
code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
namespace lct
{
struct tree
{
int l;
int r;
int fa;
int tag;
int siz;
int num;
} tr[400005];
int st[400005], sum = 0;
void newnode(int u)
{
++sum;
tr[sum].siz = u;
tr[sum].num = u;
return;
}
bool notroot(int u)
{
return tr[tr[u].fa].l == u || tr[tr[u].fa].r == u;
}
bool which(int u)
{
return tr[tr[u].fa].r == u;
}
void pushup(int u)
{
tr[u].num = tr[tr[u].l].num + tr[tr[u].r].num + tr[u].siz;
return;
}
void reverse(int u)
{
swap(tr[u].l, tr[u].r);
tr[u].tag ^= 1;
return;
}
void pushdown(int u)
{
if (tr[u].tag)
{
if (tr[u].l)
reverse(tr[u].l);
if (tr[u].r)
reverse(tr[u].r);
tr[u].tag = 0;
}
return;
}
void rotate(int u)
{
int v = tr[u].fa;
int w = tr[v].fa;
int b = (tr[v].l == u ? tr[u].r : tr[u].l);
if (notroot(v))
(tr[w].l == v ? tr[w].l : tr[w].r) = u;
if (tr[v].l == u)
{
tr[u].r = v;
tr[v].l = b;
}
else
{
tr[u].l = v;
tr[v].r = b;
}
tr[u].fa = w;
tr[v].fa = u;
if (b)
tr[b].fa = v;
pushup(v);
return;
}
void splay(int u)
{
int top = 0, id = u;
st[++top] = id;
while (notroot(id))
{
id = tr[id].fa;
st[++top] = id;
}
for (int i = top; i >= 1; --i)
pushdown(st[i]);
while (notroot(u))
{
if (notroot(tr[u].fa))
{
if (which(u) == which(tr[u].fa))
rotate(tr[u].fa);
else
rotate(u);
}
rotate(u);
}
pushup(u);
return;
}
int access(int u)
{
int v = 0;
while (u)
{
splay(u);
tr[u].r = v;
pushup(u);
v = u;
u = tr[u].fa;
}
return v;
}
void link(int u, int v)
{
splay(u);
tr[u].fa = v;
return;
}
void cut(int u)
{
access(u);
splay(u);
tr[tr[u].l].fa = 0;
tr[u].l = 0;
pushup(u);
return;
}
} // namespace lct
using namespace lct;
int n, m, cnt = 1, num, now;
int l[200005], r[200005], b[200005], ans[200005], vis[200005];
struct node
{
node(int aa = 0, int bb = 0, int cc = 0, int dd = 0)
{
id = aa;
x = bb;
y = cc;
pos = dd;
}
int id;
int x;
int y;
int pos;
} q[400005];
bool cmp(node aa, node bb)
{
if (aa.pos != bb.pos)
return aa.pos < bb.pos;
return aa.id < bb.id;
}
int main()
{
scanf("%d%d", &n, &m);
newnode(1);
newnode(0);
link(2, 1);
l[1] = 1;
r[1] = n;
b[1] = 1;
now = 2;
for (int i = 1; i <= m; ++i)
{
int type;
scanf("%d", &type);
if (type == 0)
{
newnode(1);
++cnt;
b[cnt] = sum;
link(sum, now);
scanf("%d%d", &l[cnt], &r[cnt]);
}
else if (type == 1)
{
int L, R, x;
scanf("%d%d%d", &L, &R, &x);
if (x > cnt)
continue;
L = max(L, l[x]);
R = min(R, r[x]);
if (L > R)
continue;
newnode(0);
link(sum, now);
q[++num] = node(i - m, sum, b[x], L);
q[++num] = node(i - m, sum, now, R + 1);
now = sum;
}
else if (type == 2)
{
int x, u, v;
scanf("%d%d%d", &x, &u, &v);
vis[i] = 1;
q[++num] = node(i, b[u], b[v], x);
}
}
sort(q + 1, q + num + 1, cmp);
int j = 1;
for (int i = 1; i <= n; ++i)
while (j <= num && q[j].pos == i)
{
if (q[j].id <= 0)
{
cut(q[j].x);
link(q[j].x, q[j].y);
}
else
{
access(q[j].x);
splay(q[j].x);
ans[q[j].id] += tr[q[j].x].num;
int lca = access(q[j].y);
splay(q[j].y);
ans[q[j].id] += tr[q[j].y].num;
access(lca);
splay(lca);
ans[q[j].id] -= tr[lca].num * 2;
}
++j;
}
for (int i = 1; i <= m; ++i)
if (vis[i])
printf("%d\n", ans[i]);
return 0;
}
评论
发表评论