动态仙人掌 系列题解之三——3466: 动态仙人掌 III
程序员文章站
2022-07-16 10:10:45
...
（重发下我这篇原发于 2014-03-24 的网易博客，原博客被网易莫名禁掉了。。*手动搬家，忧伤）
动态仙人掌 III
但是我们想想，图中描述的情况说，从下面绕条道经过非树边到达需要打标的链，可能吗？
绿色和紫色圈住的地方是某条边的prevExMsg和某条边的nextExMsg。
……
能link、cut、查询最短路信息、对最短路进行整体操作。
于是我们当然可以一拍脑袋说道：水题！能查询难道不能打标记么？直接裸上啊。
但是随即就遇到了阻力……
需要注意的事情是，拓展信息可以是互相重叠的，也就是说，一段路径可能被多个结构维护。这是概述里面提到的禁忌。
但是是不是这样的话一定就不能打标记了呢？
我们不妨硬着头皮来试试。
程序读入了一个修改操作，然后对指定的路径进行打标，一定是这样的：
add(x, y)
{
if (findRoot(x) != findRoot(y))
return failed;
makeRoot(x);
access(y);
splay(y);
if (y->msg中记录的信息表明有多条最短路)
return failed;
给以y为根的splay打上修改标记;
return ok;
}
那么如果现在想标记下传了，怎么办？凉拌！（我在这个地方被虐傻了……）
说从前有个最短路信息，它是由左边的一半和右边的一半合并而成的。（更准确地说是lc->msg, x->prevE, x->nextE, rc->msg），那么我们记录下取最小值的是哪条路，然后下传时打标记到对应的子树和边，不就行了。（如果不记得符号的意义可以看之前的日志）
说起来倒轻巧，这里面要讨论的条件的个数已经骇人听闻了。
我只会sb方法，用位运算压位的方式记录取最小值的来源。（你可以翻到后面我的代码里面lct_message::appendL、lct_message::appendR、lct_node::tag_down那里感受一下…… = =）
这样下传的话就不可避免地遇到一个问题：要是在链外的环上走，这标记打给谁？
于是我们一拍脑门道，当然，打在边的拓展信息上！
于是我们走上了一条不归路……
既然打在拓展信息上，就要保证access的时候能及时下传。但是一条链可能活在好多拓展信息中，而且还不全是它的父结构，这该怎么办？如下图是一个例子。
不可能！因为nextExMsg不会经过非树边。
也就是说，这种麻烦情况实际上只有一种类型：有条链在很偏远的地方的最顶端prevExMsg影响了其它链。而这两条链可能没有任何父子这类的关系。这在access的时候怎么能知道呢？
但是我们思考一下，情况何以至如此？
原因就在于我们的拓展信息并没有很明显的层次结构。如果我们能变成“拓展信息永远是向下拓展的”的话，打标也就容易了。
那么何为向下？显然，链之间是有上下关系的。我们将向叶子的方向定为向下。
这样我们发现，其实拓展信息一般来说都是向下的，如图：
这个显然是向下的。
画了几个图好像都是向下的。
这不得不引起我们的反思：对于lct来说，何为向下？
如果忽略一个结点往父亲走的情况，那么若一个结点与另一个结点相邻，但中间的边是虚边，那么就是向下！走虚边就是向下！
而我们的拓展信息永远是往“外”走，那么肯定一出门就是虚边，所以肯定是向下的。
于是我酣畅淋漓地写了一个。然后WA了。
为什么？
我们忽略了一条神奇的边的存在：链顶端的边。
于是也就忽略了一位让人肃然起敬的拓展信息：链顶端的边的prevExMsg。
它就是我们推理中的例外，因为它可以往实边走。
没办法，那我们就不定义链顶端的边的prevExMsg，放弃优美的定义，这总该行了吧。
然后发现我们回到了最初的原点，我们无法access。
来我们再来看那张经典的图。我们不用不定义链顶端的边的prevExMsg，能不能access？
困难是，我们不知道x4->prevE->prevExMsg。所以我们要想办法把它捡回来。
我们不妨再记录x4->prevE->prevExFirstE。表示prevExMsg所代表的路径的第一条边，即往prev方向一往链外走碰到的第一条边。当然，即使有prevExMsg也可能没有prevExFirstE。比如一出家门就碰到非树边的情况。
1. 如果没有prevExFirstE，那么我们也不需折腾那么许多，搞个长度为0的路径给prevExMsg就好了。
1. x4->prevE的环编号如果和x1->prevE的环编号相同，那么反正待会儿要置为空，无视。
2. x4->prevE的环编号如果和x1->nextE的环编号相同，那么从x1往x2的方向走的路径的信息中可以求出x4->prevE->prevExMsg。把headMsg和headExMsg合并起来即可。
3. 如果上面两种情况都未发生，那么prevExFirstE肯定是条虚边。虚边？那么肯定是这样：
所以我们只需要找到prevExFirstE所处的链，取出路径信息中的headMsg和headExMsg然后合并起来就得到prevExMsg了。
看起来这样做了之后就能顺利access。但是我们怎么知道“prevExFirstE所处的链”？
简单，我们对于每条位于链的顶端的边，记录一个指针指向它所在的链的splay的根。
对于那棵splay来说，这条边是它的firstE，每次splay的时候注意把firstE的那个指针改成新的根结点就好了。
在access的时候也要小小地调整一下，不成问题。
那么现在终于有了清晰的层次结构，怎么打标呢？
显然最后打标的任务会落在拓展信息头上。但是我们发现我们其实记录了prevExFirstE和nextExFirstE，还知道它们所处的链的根结点。那么直接打在根结点上就好了！
access的伪代码示例：
void access(x)
{
allFaTagDown(x); // 把x到根的所有标记下传。这里的根说的是树的总根。
for (p = x, q = NULL; p; q = p, p = p->fa)
{
p->splay(); // 这里的splay不执行标记下传
qFirstE = q ? q->msg.firstE : NULL;
// 下面出现的*运算表示信息的合并
// path_message(e) 表示一条边e的原子信息
// 计算出qFirstE->prevExMsg
if (getCirNum(qFirstE) != NULL)
{
if (getCirNum(qFirstE) != getCirNum(p->prevE))
{
if (qFirstE->prevExFirstE != NULL)
{
pr = getCirNum(qFirstE) == getCirNum(p->nextE) ? p->rc : qFirstE->prevExFirstE->whoseFirstE;
qFirstE->prevExMsg = path_message(qFirstE->prevExFirstE) * pr->msg.headMsg * pr->msg.headExMsg;
}
else
qFirstE->prevExMsg.setEmpty();
}
else
{
qFirstE->prevExMsg.setInvalid();
qFirstE->prevExFirstE = NULL;
}
}
// 进行换边操作时拓展信息的调整
if (getCirNum(p->prevE) != NULL)
{
if (getCirNum(p->prevE) == getCirNum(qFirstE))
{
p->prevE->nextEx_setInvalid();
qFirstE->prevEx_setInvalid();
}
if (getCirNum(p->prevE) == getCirNum(p->nextE))
{
p->prevE->nextExMsg = p->rc->msg.headExMsg * p->rc->msg.headMsg * path_message(p->nextE);
p->prevE->nextExFirstE = p->nextE;
// 可以不用管p->nextE->prevExMsg的值
p->nextE->prevExFirstE = p->prevE;
}
}
// 更新一下相关的边是哪条链的第一条边并进行换边操作
if (p->rc != NULL)
{
if (p->rc->msg.firstE)
p->rc->msg.firstE->whoseFirstE = p->rc;
}
p->nextE = qFirstE;
p->rc = q;
if (qFirstE != NULL)
qFirstE->whoseFirstE = NULL;
p->update();
}
}这样我们就顺利解决了动态仙人掌 III。
这样做虽然比较繁琐但是仍然坚挺在O(n log n)。
（如果你不是很喜欢的话没关系！可以试试下一篇日志将要介绍的link-cut cactus）
有什么细节不清楚的可以看代码。（写了我1000行……分类讨论一口血喷出来……）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cassert>
#include <climits>
using namespace std;
const int INF = INT_MAX;
const int MaxN = 100000;
inline int getint()
{
char c;
while (c = getchar(), '0' > c || c > '9');
int res = c - '0';
while (c = getchar(), '0' <= c && c <= '9')
res = res * 10 + c - '0';
return res;
}
template <class T>
class BlockAllocator
{
private:
static const int BlockL = 10000;
union TItem
{
char rt[sizeof(T)];
TItem *next;
};
TItem *pool, *tail;
TItem *unused;
public:
BlockAllocator()
{
pool = NULL;
unused = NULL;
}
T *allocate()
{
TItem *p;
if (unused)
{
p = unused;
unused = unused->next;
}
else
{
if (pool == NULL)
pool = new TItem[BlockL], tail = pool;
p = tail++;
if (tail == pool + BlockL)
pool = NULL;
}
return (T*)p;
}
void deallocate(T *pt)
{
TItem *p = (TItem*)pt;
p->next = unused, unused = p;
}
};
struct edgeWeight;
struct path_message;
struct edge;
struct lct_edge;
struct lct_message;
struct lct_node;
struct edgeWeight
{
int wA, wB;
edgeWeight(){}
edgeWeight(const int &_wA, const int &_wB)
: wA(_wA), wB(_wB){}
friend inline bool operator==(const edgeWeight &lhs, const edgeWeight &rhs)
{
return lhs.wA == rhs.wA && lhs.wB == rhs.wB;
}
friend inline bool operator!=(const edgeWeight &lhs, const edgeWeight &rhs)
{
return lhs.wA != rhs.wA || lhs.wB != rhs.wB;
}
};
struct path_message
{
int minLA;
int minWB;
path_message(){}
path_message(const int &_minLA, const int &_minWB)
: minLA(_minLA), minWB(_minWB){}
void setEmpty()
{
minLA = 0;
minWB = INF;
}
void setInvalid()
{
minLA = -1;
minWB = -1;
}
bool valid() const
{
return minLA != -1;
}
void wB_add(int delta)
{
if (minWB != INF)
minWB += delta;
}
friend inline path_message operator+(const path_message &lhs, const path_message &rhs)
{
if (lhs.minLA < rhs.minLA)
return lhs;
else if (rhs.minLA < lhs.minLA)
return rhs;
else
return path_message(lhs.minLA, -1);
}
friend inline path_message operator*(const path_message &lhs, const path_message &rhs)
{
return path_message(lhs.minLA + rhs.minLA, min(lhs.minWB, rhs.minWB));
}
friend inline path_message operator*(const edgeWeight &lhs, const path_message &rhs)
{
return path_message(lhs.wA + rhs.minLA, min(lhs.wB, rhs.minWB));
}
friend inline path_message operator*(const path_message &lhs, const edgeWeight &rhs)
{
return path_message(lhs.minLA + rhs.wA, min(lhs.minWB, rhs.wB));
}
};
struct edge
{
int v, u;
edgeWeight ew;
};
struct lct_edge
{
edgeWeight ew;
edge *cirE;
lct_node *whoseFirstE;
path_message prevExMsg, nextExMsg;
lct_edge *prevExFirstE, *nextExFirstE;
void rev()
{
swap(prevExMsg, nextExMsg);
swap(prevExFirstE, nextExFirstE);
}
void coverCirE(edge *e)
{
cirE = e;
}
void prevEx_setInvalid()
{
prevExMsg.setInvalid();
if (prevExFirstE)
prevExFirstE->whoseFirstE = NULL;
prevExFirstE = NULL;
}
void nextEx_setInvalid()
{
nextExMsg.setInvalid();
if (nextExFirstE)
nextExFirstE->whoseFirstE = NULL;
nextExFirstE = NULL;
}
inline void tag_prevExWB_add(int delta);
inline void tag_nextExWB_add(int delta);
edge *getCirE()
{
return this ? this->cirE : NULL;
}
};
struct lct_message
{
path_message headExMsg, tailExMsg;
path_message headMsg, midMsg, tailMsg;
int headExFrom, tailExFrom;
int headFrom, midFrom, tailFrom;
static const int FromLcHead = 1 << 0;
static const int FromLcHeadEx = 1 << 1;
static const int FromLcMid = 1 << 2;
static const int FromLcTailEx = 1 << 3;
static const int FromLcTail = 1 << 4;
static const int FromLE = 1 << 5;
static const int FromLCirE = 1 << 6;
static const int FromMeHead = 1 << 7;
static const int FromMeHeadEx = 1 << 8;
static const int FromMeMid = 1 << 9;
static const int FromMeTailEx = 1 << 10;
static const int FromMeTail = 1 << 11;
static const int FromRCirE = 1 << 12;
static const int FromRE = 1 << 13;
static const int FromRcHead = 1 << 14;
static const int FromRcHeadEx = 1 << 15;
static const int FromRcMid = 1 << 16;
static const int FromRcTailEx = 1 << 17;
static const int FromRcTail = 1 << 18;
lct_edge *firstE, *lastE;
bool hasCirE;
static int preRev[1 << 19];
static void rev_from_init()
{
for (int i = 0; i < (1 << 19); i++)
{
int x = i, rx = 0;
for (int j = 0; j < 19; j++)
{
rx = rx << 1 | (x & 1);
x >>= 1;
}
preRev[i] = rx;
}
}
static void rev_from(int &from)
{
from = preRev[from];
}
void rev()
{
swap(firstE, lastE);
swap(headExMsg, tailExMsg), swap(headExFrom, tailExFrom);
swap(headMsg, tailMsg), swap(headFrom, tailFrom);
rev_from(headExFrom), rev_from(tailExFrom);
rev_from(headFrom), rev_from(midFrom), rev_from(tailFrom);
}
void coverCirE(edge *e, bool isSingle)
{
hasCirE = isSingle ? false : e != NULL;
}
void headExWB_add(int delta)
{
assert(headExMsg.valid());
headExMsg.wB_add(delta);
}
void tailExWB_add(int delta)
{
assert(tailExMsg.valid());
tailExMsg.wB_add(delta);
}
void headWB_add(int delta)
{
if (headExMsg.valid())
headMsg.wB_add(delta);
}
void midWB_add(int delta)
{
assert(midMsg.minWB != -1);
midMsg.wB_add(delta);
}
void tailWB_add(int delta)
{
if (tailExMsg.valid())
tailMsg.wB_add(delta);
}
void appendL(const lct_message &lmsg)
{
assert(lmsg.lastE == this->firstE);
lct_edge *e = lmsg.lastE;
this->firstE = lmsg.firstE;
this->hasCirE = lmsg.hasCirE || e->cirE || this->hasCirE;
if (lmsg.tailExMsg.valid() && this->headExMsg.valid())
{
path_message path1 = lmsg.tailMsg * e->ew * this->headMsg ;
path_message path2 = lmsg.tailExMsg * e->cirE->ew * this->headExMsg;
this->midMsg = lmsg.midMsg * (path1 + path2) * this->midMsg;
if (path1.minLA < path2.minLA)
this->midFrom = FromLcMid | FromLcTail | FromLE | this->headFrom | this->midFrom;
else
this->midFrom = FromLcMid | FromLcTailEx | FromLCirE | this->headExFrom | this->midFrom;
this->headExMsg = lmsg.headExMsg;
this->headExFrom = FromLcHeadEx;
this->headMsg = lmsg.headMsg;
this->headFrom = FromLcHead;
}
else if (lmsg.tailExMsg.valid())
{
this->headExMsg = lmsg.headExMsg;
this->headExFrom = FromLcHeadEx;
this->headMsg = lmsg.headMsg;
this->headFrom = FromLcHead;
this->tailExMsg = lmsg.tailExMsg;
this->tailExFrom = FromLcTailEx;
this->tailMsg = lmsg.tailMsg * e->ew * this->midMsg;
this->tailFrom = FromLcTail | FromLE | this->midFrom;
this->midMsg = lmsg.midMsg;
this->midFrom = FromLcMid;
}
else if (this->headExMsg.valid())
{
this->headMsg = lmsg.midMsg * e->ew * this->headMsg;
this->headFrom = FromLcMid | FromLE | this->headFrom;
}
else
{
this->headExMsg = lmsg.headExMsg;
this->headExFrom = FromLcHeadEx;
this->headMsg = lmsg.headMsg;
this->headFrom = FromLcHead;
this->midMsg = lmsg.midMsg * e->ew * this->midMsg;
this->midFrom = FromLcMid | FromLE | this->midFrom;
}
}
void appendR(const lct_message &rmsg)
{
assert(this->lastE == rmsg.firstE);
lct_edge *e = this->lastE;
this->lastE = rmsg.lastE;
this->hasCirE = this->hasCirE || e->cirE || rmsg.hasCirE;
if (this->tailExMsg.valid() && rmsg.headExMsg.valid())
{
path_message path1 = this->tailMsg * e->ew * rmsg.headMsg ;
path_message path2 = this->tailExMsg * e->cirE->ew * rmsg.headExMsg;
this->midMsg = this->midMsg * (path1 + path2) * rmsg.midMsg;
if (path1.minLA < path2.minLA)
this->midFrom = this->midFrom | this->tailFrom | FromRE | FromRcHead | FromRcMid;
else
this->midFrom = this->midFrom | this->tailExFrom | FromRCirE | FromRcHeadEx | FromRcMid;
this->tailExMsg = rmsg.tailExMsg;
this->tailExFrom = FromRcTailEx;
this->tailMsg = rmsg.tailMsg;
this->tailFrom = FromRcTail;
}
else if (this->tailExMsg.valid())
{
this->tailMsg = this->tailMsg * e->ew * rmsg.midMsg;
this->tailFrom = this->tailFrom | FromRE | FromRcMid;
}
else if (rmsg.headExMsg.valid())
{
this->headExMsg = rmsg.headExMsg;
this->headExFrom = FromRcHeadEx;
this->headMsg = this->midMsg * e->ew * rmsg.headMsg;
this->headFrom = this->midFrom | FromRE | FromRcHead;
this->tailExMsg = rmsg.tailExMsg;
this->tailExFrom = FromRcTailEx;
this->tailMsg = rmsg.tailMsg;
this->tailFrom = FromRcTail;
this->midMsg = rmsg.midMsg;
this->midFrom = FromRcMid;
}
else
{
this->tailExMsg = rmsg.tailExMsg;
this->tailExFrom = FromRcTailEx;
this->tailMsg = rmsg.tailMsg;
this->tailFrom = FromRcTail;
this->midMsg = this->midMsg * e->ew * rmsg.midMsg;
this->midFrom = this->midFrom | FromRE | FromRcMid;
}
}
};
int lct_message::preRev[1 << 19];
struct lct_node
{
lct_node *fa, *lc, *rc;
lct_edge *prevE, *nextE;
lct_message msg;
bool hasRev;
bool hasCoveredCirE;
edge *coveredCirE;
int headExWBDelta, tailExWBDelta;
int headWBDelta, midWBDelta, tailWBDelta;
bool isRoot()
{
return !fa || (fa->lc != this && fa->rc != this);
}
void rotate()
{
lct_node *x = this, *y = x->fa, *z = y->fa;
lct_node *b = x == y->lc ? x->rc : x->lc;
x->fa = z, y->fa = x;
if (b)
b->fa = y;
if (z && (z->lc == y || z->rc == y))
(z->lc == y ? z->lc : z->rc) = x;
else
{
if (y->msg.firstE)
{
x->msg.firstE = y->msg.firstE;
y->msg.firstE->whoseFirstE = x;
}
}
if (x == y->lc)
x->rc = y, y->lc = b;
else
x->lc = y, y->rc = b;
y->update();
}
void allFaTagDown()
{
int anc_n = 0;
static lct_node *anc[MaxN];
for (lct_node *x = this; x; x = x->fa)
anc[anc_n++] = x;
for (int i = anc_n - 1; i >= 0; i--)
anc[i]->tag_down();
}
void splay()
{
while (!this->isRoot())
{
if (!fa->isRoot())
{
if ((fa->fa->lc == fa) == (fa->lc == this))
fa->rotate();
else
this->rotate();
}
this->rotate();
}
this->update();
}
void splay_until(lct_node *target)
{
while (this->fa != target)
{
if (fa->fa != target)
{
if ((fa->fa->lc == fa) == (fa->lc == this))
fa->rotate();
else
this->rotate();
}
this->rotate();
}
this->update();
}
void access()
{
this->allFaTagDown();
for (lct_node *p = this, *q = NULL; p; q = p, p = p->fa)
{
p->splay();
lct_edge *qFirstE = q ? q->msg.firstE : NULL;
if (qFirstE->getCirE())
{
if (qFirstE->getCirE() != p->prevE->getCirE())
{
if (qFirstE->prevExFirstE)
{
lct_node *pr = qFirstE->getCirE() == p->nextE->getCirE() ? p->rc : qFirstE->prevExFirstE->whoseFirstE;
qFirstE->prevExMsg = qFirstE->prevExFirstE->ew * pr->msg.headMsg * pr->msg.headExMsg;
}
else
qFirstE->prevExMsg.setEmpty();
}
else
{
qFirstE->prevExMsg.setInvalid();
qFirstE->prevExFirstE = NULL;
}
}
if (p->prevE->getCirE())
{
if (p->prevE->getCirE() == qFirstE->getCirE())
{
p->prevE->nextEx_setInvalid();
qFirstE->prevEx_setInvalid();
}
if (p->prevE->getCirE() == p->nextE->getCirE())
{
p->prevE->nextExMsg = p->rc->msg.headExMsg * p->rc->msg.headMsg * p->nextE->ew;
p->prevE->nextExFirstE = p->nextE;
p->nextE->prevExFirstE = p->prevE;
}
}
if (p->rc)
{
if (p->rc->msg.firstE)
p->rc->msg.firstE->whoseFirstE = p->rc;
}
p->nextE = qFirstE;
p->rc = q;
if (qFirstE)
qFirstE->whoseFirstE = NULL;
}
this->splay();
}
void makeRoot()
{
this->access();
this->tag_rev();
this->tag_down();
}
lct_node *findRoot()
{
this->access();
lct_node *root = this;
while (root->tag_down(), root->lc)
root = root->lc;
root->splay();
return root;
}
void tag_rev()
{
hasRev = !hasRev;
msg.rev();
swap(headExWBDelta, tailExWBDelta);
swap(headWBDelta, tailWBDelta);
}
void tag_coverCirE(edge *e)
{
hasCoveredCirE = true, coveredCirE = e;
msg.coverCirE(e, !lc && !rc);
}
void tag_headExWB_add(int delta)
{
headExWBDelta += delta;
msg.headExWB_add(delta);
}
void tag_tailExWB_add(int delta)
{
tailExWBDelta += delta;
msg.tailExWB_add(delta);
}
void tag_headWB_add(int delta)
{
headWBDelta += delta;
msg.headWB_add(delta);
}
void tag_midWB_add(int delta)
{
midWBDelta += delta;
msg.midWB_add(delta);
}
void tag_tailWB_add(int delta)
{
tailWBDelta += delta;
msg.tailWB_add(delta);
}
void tag_wB_add_all(int all, int delta)
{
for (int cur = all; cur > 0; cur &= cur - 1)
{
const int P = 29;
switch ((cur & -cur) % P)
{
case lct_message::FromLcHead % P:
lc->tag_headWB_add(delta);
break;
case lct_message::FromLcHeadEx % P:
lc->tag_headExWB_add(delta);
break;
case lct_message::FromLcMid % P:
lc->tag_midWB_add(delta);
break;
case lct_message::FromLcTailEx % P:
lc->tag_tailExWB_add(delta);
break;
case lct_message::FromLcTail % P:
lc->tag_tailWB_add(delta);
break;
case lct_message::FromLE % P:
prevE->ew.wB += delta;
break;
case lct_message::FromLCirE % P:
prevE->cirE->ew.wB += delta;
break;
case lct_message::FromMeHead % P:
break;
case lct_message::FromMeHeadEx % P:
prevE->tag_nextExWB_add(delta);
break;
case lct_message::FromMeMid % P:
break;
case lct_message::FromMeTailEx % P:
nextE->tag_prevExWB_add(delta);
break;
case lct_message::FromMeTail % P:
break;
case lct_message::FromRCirE % P:
nextE->cirE->ew.wB += delta;
break;
case lct_message::FromRE % P:
nextE->ew.wB += delta;
break;
case lct_message::FromRcHead % P:
rc->tag_headWB_add(delta);
break;
case lct_message::FromRcHeadEx % P:
rc->tag_headExWB_add(delta);
break;
case lct_message::FromRcMid % P:
rc->tag_midWB_add(delta);
break;
case lct_message::FromRcTailEx % P:
rc->tag_tailExWB_add(delta);
break;
case lct_message::FromRcTail % P:
rc->tag_tailWB_add(delta);
break;
}
}
}
void tag_down()
{
if (hasRev)
{
swap(lc, rc);
swap(prevE, nextE);
if (lc)
{
prevE->rev();
lc->tag_rev();
}
if (rc)
{
nextE->rev();
rc->tag_rev();
}
hasRev = false;
}
if (hasCoveredCirE)
{
if (lc)
{
prevE->coverCirE(coveredCirE);
lc->tag_coverCirE(coveredCirE);
}
if (rc)
{
nextE->coverCirE(coveredCirE);
rc->tag_coverCirE(coveredCirE);
}
hasCoveredCirE = false;
}
if (headExWBDelta != 0)
{
tag_wB_add_all(msg.headExFrom, headExWBDelta);
headExWBDelta = 0;
}
if (tailExWBDelta != 0)
{
tag_wB_add_all(msg.tailExFrom, tailExWBDelta);
tailExWBDelta = 0;
}
if (headWBDelta != 0)
{
tag_wB_add_all(msg.headFrom, headWBDelta);
headWBDelta = 0;
}
if (midWBDelta != 0)
{
tag_wB_add_all(msg.midFrom, midWBDelta);
midWBDelta = 0;
}
if (tailWBDelta != 0)
{
tag_wB_add_all(msg.tailFrom, tailWBDelta);
tailWBDelta = 0;
}
}
void update()
{
if (prevE)
{
msg.headExMsg = prevE->nextExMsg;
msg.headExFrom = lct_message::FromMeHeadEx;
}
else
{
msg.headExMsg.setInvalid();
msg.headExFrom = 0;
}
msg.headMsg.setEmpty();
msg.headFrom = lct_message::FromMeHead;
if (nextE)
{
msg.tailExMsg = nextE->prevExMsg;
msg.tailExFrom = lct_message::FromMeTailEx;
}
else
{
msg.tailExMsg.setInvalid();
msg.tailExFrom = 0;
}
msg.tailMsg.setEmpty();
msg.tailFrom = lct_message::FromMeTail;
msg.midMsg.setEmpty();
msg.midFrom = lct_message::FromMeMid;
msg.hasCirE = false;
msg.firstE = prevE, msg.lastE = nextE;
if (lc)
this->msg.appendL(lc->msg);
if (rc)
this->msg.appendR(rc->msg);
}
};
void lct_edge::tag_prevExWB_add(int delta)
{
if (!prevExMsg.valid())
return;
prevExMsg.wB_add(delta);
if (prevExFirstE)
{
lct_node *p = prevExFirstE->whoseFirstE;
assert(p != NULL);
p->tag_headWB_add(delta);
p->tag_headExWB_add(delta);
prevExFirstE->ew.wB += delta;
}
}
void lct_edge::tag_nextExWB_add(int delta)
{
if (!nextExMsg.valid())
return;
nextExMsg.wB_add(delta);
if (nextExFirstE)
{
lct_node *p = nextExFirstE->whoseFirstE;
assert(p != NULL);
p->tag_headWB_add(delta);
p->tag_headExWB_add(delta);
nextExFirstE->ew.wB += delta;
}
}
lct_node lctVer[MaxN + 1];
BlockAllocator<edge> lctCirEAllocator;
BlockAllocator<lct_edge> lctEAllocator;
int n;
void cactus_init()
{
lct_message::rev_from_init();
for (int v = 1; v <= n; v++)
{
lct_node *p = lctVer + v;
p->fa = p->lc = p->rc = NULL;
p->prevE = p->nextE = NULL;
p->hasRev = false;
p->hasCoveredCirE = false;
p->headExWBDelta = 0, p->tailExWBDelta = 0;
p->headWBDelta = 0, p->midWBDelta = 0, p->tailWBDelta = 0;
p->update();
}
}
bool cactus_link(int v, int u, int wA, int wB)
{
if (v == u)
return false;
if (v > u)
swap(v, u);
edgeWeight ew(wA, wB);
lct_node *x = lctVer + v, *y = lctVer + u;
x->makeRoot();
y->makeRoot();
if (x->fa)
{
x->access();
y->allFaTagDown(), y->splay_until(x);
if (x->msg.hasCirE)
return false;
edge *cirE = lctCirEAllocator.allocate();
cirE->v = v, cirE->u = u, cirE->ew = ew;
y->nextE->cirE = cirE;
y->nextE->prevExMsg.setEmpty();
y->nextE->prevExFirstE = NULL;
x->prevE->cirE = cirE;
x->prevE->nextExMsg.setEmpty();
x->prevE->nextExFirstE = NULL;
if (y->rc)
y->rc->tag_coverCirE(cirE);
y->update(), x->update();
}
else
{
x->fa = y;
lct_edge *e = lctEAllocator.allocate();
e->ew = ew, e->cirE = NULL;
e->prevEx_setInvalid(), e->nextEx_setInvalid();
x->prevE = e;
e->whoseFirstE = x;
x->update();
}
return true;
}
bool cactus_cut(int v, int u, int wA, int wB)
{
if (v == u)
return false;
if (v > u)
swap(v, u);
static int cnt = 0;
cnt++;
edgeWeight ew(wA, wB);
lct_node *x = lctVer + v, *y = lctVer + u;
if (x->findRoot() != y->findRoot())
return false;
y->makeRoot();
x->access();
y->allFaTagDown(), y->splay_until(x);
lct_edge *e = y->nextE;
edge *cirE = e->cirE;
if (cirE && cirE->v == v && cirE->u == u && cirE->ew == ew)
{
y->nextE->cirE = NULL, y->nextE->prevEx_setInvalid();
x->prevE->cirE = NULL, x->prevE->nextEx_setInvalid();
if (y->rc)
y->rc->tag_coverCirE(NULL);
y->update(), x->update();
lctCirEAllocator.deallocate(cirE);
return true;
}
if (!y->rc && e->ew == ew)
{
lct_node *ex, *ey;
if (cirE)
{
ex = lctVer + cirE->v;
ey = lctVer + cirE->u;
ey->makeRoot();
ex->access();
ey->allFaTagDown(), ey->splay_until(ex);
ey->nextE->cirE = NULL, ey->nextE->prevEx_setInvalid();
ex->prevE->cirE = NULL, ex->prevE->nextEx_setInvalid();
if (ey->rc)
ey->rc->tag_coverCirE(NULL);
ey->update(), ex->update();
y->makeRoot();
x->access();
y->allFaTagDown(), y->splay_until(x);
}
lctEAllocator.deallocate(e);
x->prevE = NULL, y->nextE = NULL;
x->lc = NULL, y->fa = NULL;
x->update(), y->update();
if (y->msg.firstE)
y->msg.firstE->whoseFirstE = y;
if (cirE)
{
ex->makeRoot(), ey->makeRoot();
ex->fa = ey;
e = lctEAllocator.allocate();
e->ew = cirE->ew, e->cirE = NULL;
e->prevEx_setInvalid(), e->nextEx_setInvalid();
ex->prevE = e;
e->whoseFirstE = ex;
ex->update();
lctCirEAllocator.deallocate(cirE);
}
return true;
}
return false;
}
bool cactus_add(int qv, int qu, int delta)
{
lct_node *x = lctVer + qv, *y = lctVer + qu;
if (x->findRoot() != y->findRoot())
return false;
x->makeRoot();
y->access();
if (y->msg.midMsg.minWB == -1)
return false;
y->tag_midWB_add(delta);
return true;
}
path_message cactus_query(int qv, int qu)
{
lct_node *x = lctVer + qv, *y = lctVer + qu;
path_message res;
if (x->findRoot() != y->findRoot())
{
res.setInvalid();
return res;
}
x->makeRoot();
y->access();
return y->msg.midMsg;
}
int main()
{
int nQ;
cin >> n >> nQ;
cactus_init();
while (nQ--)
{
char type;
while (type = getchar(), type != 'l' && type != 'c' && type != 'a' && type != 'd');
if (type == 'l')
{
int v = getint(), u = getint(), wA = getint(), wB = getint();
if (cactus_link(v, u, wA, wB))
printf("ok\n");
else
printf("failed\n");
}
else if (type == 'c')
{
int v = getint(), u = getint(), wA = getint(), wB = getint();
if (cactus_cut(v, u, wA, wB))
printf("ok\n");
else
printf("failed\n");
}
else if (type == 'a')
{
int v = getint(), u = getint(), delta = getint();
if (cactus_add(v, u, delta))
printf("ok\n");
else
printf("failed\n");
}
else if (type == 'd')
{
int v = getint(), u = getint();
path_message ret = cactus_query(v, u);
printf("%d %d\n", ret.minLA, ret.minWB);
}
else
{
puts("error!");
}
}
return 0;
}上一篇： HDU - 6228
下一篇： 动态规划 - 49.丑数