mirror of
https://github.com/Kiritow/OJ-Problems-Source.git
synced 2024-03-22 13:11:29 +08:00
457 lines
11 KiB
Plaintext
457 lines
11 KiB
Plaintext
|
============<3D><><EFBFBD>ݽṹģ<E1B9B9><C4A3>================
|
|||
|
|
|
|||
|
|
<EFBFBD><EFBFBD>̬<EFBFBD><EFBFBD>
|
|||
|
|
<EFBFBD><EFBFBD>̬<EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD>Ҫ<EFBFBD><EFBFBD>ά<EFBFBD><EFBFBD>ɭ<EFBFBD>ֵ<EFBFBD><EFBFBD><EFBFBD>ͨ<EFBFBD>Ե<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ܳƣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ҫ<EFBFBD><EFBFBD>ά<EFBFBD><EFBFBD>ij<EFBFBD><EFBFBD><EFBFBD>㵽<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ijЩ<EFBFBD><EFBFBD><EFBFBD>ݣ<EFBFBD>֧<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>з֣<EFBFBD><EFBFBD>ϲ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Լ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ijЩ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>н<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ijЩ<EFBFBD>棨<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>IJ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ļ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ݽṹ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>LCT(link-cut tree)<29><>
|
|||
|
|
|
|||
|
|
const int MAXN = 100010;
|
|||
|
|
struct Node
|
|||
|
|
{
|
|||
|
|
Node *ch[2], *p;
|
|||
|
|
int size, value;
|
|||
|
|
bool rev;
|
|||
|
|
Node(int t = 0);
|
|||
|
|
inline bool dir(void)
|
|||
|
|
{
|
|||
|
|
return p->ch[1] == this;
|
|||
|
|
}
|
|||
|
|
inline void SetC(Node *x, bool d)
|
|||
|
|
{
|
|||
|
|
ch[d] = x;
|
|||
|
|
x->p = this;
|
|||
|
|
}
|
|||
|
|
inline void Rev(void)
|
|||
|
|
{
|
|||
|
|
swap(ch[0], ch[1]);
|
|||
|
|
rev ^= 1;
|
|||
|
|
}
|
|||
|
|
inline void Push(void)
|
|||
|
|
{
|
|||
|
|
if (rev)
|
|||
|
|
{
|
|||
|
|
ch[0]->Rev();
|
|||
|
|
ch[1]->Rev();
|
|||
|
|
rev = 0;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
inline void Update(void)
|
|||
|
|
{
|
|||
|
|
size = ch[0]->size + ch[1]->size + 1;
|
|||
|
|
}
|
|||
|
|
} Tnull, *null = &Tnull, *fim[MAXN];
|
|||
|
|
// Ҫ<>ǵö<C7B5><C3B6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>null<6C><6C><EFBFBD><EFBFBD>Ϣ
|
|||
|
|
Node::Node(int _value)
|
|||
|
|
{
|
|||
|
|
ch[0] = ch[1] = p = null;
|
|||
|
|
rev = 0;
|
|||
|
|
}
|
|||
|
|
inline bool isRoot(Node *x)
|
|||
|
|
{
|
|||
|
|
return x->p == null || (x != x->p->ch[0] && x != x->p->ch[1]);
|
|||
|
|
}
|
|||
|
|
inline void rotate(Node *x)
|
|||
|
|
{
|
|||
|
|
Node *p = x->p;
|
|||
|
|
bool d = x->dir();
|
|||
|
|
p->Push();
|
|||
|
|
x->Push();
|
|||
|
|
if (!isRoot(p)) p->p->SetC(x, p->dir());
|
|||
|
|
else x->p = p->p;
|
|||
|
|
p->SetC(x->ch[!d], d);
|
|||
|
|
x->SetC(p, !d);
|
|||
|
|
p->Update();
|
|||
|
|
}
|
|||
|
|
inline void splay(Node *x)
|
|||
|
|
{
|
|||
|
|
x->Push();
|
|||
|
|
while (!isRoot(x))
|
|||
|
|
{
|
|||
|
|
if (isRoot(x->p)) rotate(x);
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
if (x->dir() == x->p->dir())
|
|||
|
|
{
|
|||
|
|
rotate(x->p);
|
|||
|
|
rotate(x);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
rotate(x);
|
|||
|
|
rotate(x);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
x->Update();
|
|||
|
|
}
|
|||
|
|
inline Node* Access(Node *x)
|
|||
|
|
{
|
|||
|
|
Node *t = x, *q = null;
|
|||
|
|
for (; x != null; x = x->p)
|
|||
|
|
{
|
|||
|
|
splay(x);
|
|||
|
|
x->ch[1] = q;
|
|||
|
|
q = x;
|
|||
|
|
}
|
|||
|
|
splay(t); //info will be updated in the splay;
|
|||
|
|
return q;
|
|||
|
|
}
|
|||
|
|
inline void Evert(Node *x)
|
|||
|
|
{
|
|||
|
|
Access(x);
|
|||
|
|
x->Rev();
|
|||
|
|
}
|
|||
|
|
inline void link(Node *x, Node *y)
|
|||
|
|
{
|
|||
|
|
Evert(x);
|
|||
|
|
x->p = y;
|
|||
|
|
}
|
|||
|
|
inline Node* getRoot(Node *x)
|
|||
|
|
{
|
|||
|
|
Node *tmp = x;
|
|||
|
|
Access(x);
|
|||
|
|
while (tmp->Push(), tmp->ch[0] != null) tmp = tmp->ch[0];
|
|||
|
|
splay(tmp);
|
|||
|
|
return tmp;
|
|||
|
|
}
|
|||
|
|
// һ<><D2BB>Ҫȷ<D2AA><C8B7>x<EFBFBD><78>y֮<79><D6AE><EFBFBD>б<EFBFBD>
|
|||
|
|
inline void cut(Node *x, Node *y)
|
|||
|
|
{
|
|||
|
|
Access(x);
|
|||
|
|
splay(y);
|
|||
|
|
if (y->p != x) swap(x, y);
|
|||
|
|
Access(x);
|
|||
|
|
splay(y);
|
|||
|
|
y->p = null;
|
|||
|
|
}
|
|||
|
|
inline Node* getPath(Node *x, Node *y)
|
|||
|
|
{
|
|||
|
|
Evert(x);
|
|||
|
|
Access(y);
|
|||
|
|
return y;
|
|||
|
|
}
|
|||
|
|
inline void clear(void)
|
|||
|
|
{
|
|||
|
|
null->rev = 0;
|
|||
|
|
null->sie = 0;
|
|||
|
|
null->value = 0;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
splay<EFBFBD><EFBFBD>ģ<EFBFBD>壬<EFBFBD><EFBFBD>Ϊ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>֣<EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊsplay<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƽ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʹ<EFBFBD>ã<EFBFBD><EFBFBD>ڶ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊsplay<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>߶<EFBFBD><EFBFBD><EFBFBD>ά<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʹ<EFBFBD>á<EFBFBD>ע<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ÿ<EFBFBD><EFBFBD>Insert֮<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ҫsplay<EFBFBD>䷵<EFBFBD><EFBFBD>ֵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ܵĽڵ<C4BD><DAB5><EFBFBD>
|
|||
|
|
const int MAXN = 100010;
|
|||
|
|
// ÿ<><C3BF><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ǵIJ<C7B5><C4B2><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ǹ<EFBFBD><C7B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD>Ϣ<EFBFBD><CFA2>Ȼ<EFBFBD><C8BB><EFBFBD><EFBFBD><EFBFBD>ӽڵ<D3BD><DAB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
struct Node
|
|||
|
|
{
|
|||
|
|
Node *ch[2], *p;
|
|||
|
|
int size, value;
|
|||
|
|
bool rev;
|
|||
|
|
inline bool dir(void)
|
|||
|
|
{
|
|||
|
|
return p->ch[1] == this;
|
|||
|
|
}
|
|||
|
|
inline void SetC(Node *x, bool d)
|
|||
|
|
{
|
|||
|
|
ch[d] = x;
|
|||
|
|
x->p = this;
|
|||
|
|
}
|
|||
|
|
inline void Rev(void)
|
|||
|
|
{
|
|||
|
|
swap(ch[0], ch[1]);
|
|||
|
|
rev ^= 1;
|
|||
|
|
}
|
|||
|
|
// null<6C><6C>Զ<EFBFBD><D4B6><EFBFBD><EFBFBD>push
|
|||
|
|
inline void Push(void)
|
|||
|
|
{
|
|||
|
|
if (rev)
|
|||
|
|
{
|
|||
|
|
ch[0]->Rev();
|
|||
|
|
ch[1]->Rev();
|
|||
|
|
rev = 0;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
// null<6C><6C>Զ<EFBFBD><D4B6><EFBFBD><EFBFBD>update
|
|||
|
|
inline void Update(void)
|
|||
|
|
{
|
|||
|
|
size = ch[0]->size + ch[1]->size + 1;
|
|||
|
|
}
|
|||
|
|
inline void initInfo(void)
|
|||
|
|
{
|
|||
|
|
rev = 0;
|
|||
|
|
}
|
|||
|
|
} Tnull, *null = &Tnull, *data, POOL[MAXN];
|
|||
|
|
class Splay
|
|||
|
|
{
|
|||
|
|
public:
|
|||
|
|
Node *root;
|
|||
|
|
inline void rotate(Node *x)
|
|||
|
|
{
|
|||
|
|
Node *p = x->p;
|
|||
|
|
bool d = x->dir();
|
|||
|
|
p->Push();
|
|||
|
|
x->Push();
|
|||
|
|
p->p->SetC(x, p->dir());
|
|||
|
|
p->SetC(x->ch[!d], d);
|
|||
|
|
x->SetC(p, !d);
|
|||
|
|
p->Update();
|
|||
|
|
}
|
|||
|
|
inline void splay(Node *x, Node *G)
|
|||
|
|
{
|
|||
|
|
if (G == null) root = x;
|
|||
|
|
while (x->p != G)
|
|||
|
|
{
|
|||
|
|
if (x->p->p == G) rotate(x);
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
if (x->dir() == x->p->dir())
|
|||
|
|
{
|
|||
|
|
rotate(x->p);
|
|||
|
|
rotate(x);
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
rotate(x);
|
|||
|
|
rotate(x);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
x->Push();
|
|||
|
|
x->Update();
|
|||
|
|
}
|
|||
|
|
inline Node* Renew(int value)
|
|||
|
|
{
|
|||
|
|
Node *ret = data++;
|
|||
|
|
ret->ch[0] = ret->ch[1] =ret->p = null;
|
|||
|
|
ret->size = 1;
|
|||
|
|
ret->value = value;
|
|||
|
|
ret->initInfo();
|
|||
|
|
return ret;
|
|||
|
|
}
|
|||
|
|
inline Node* getMin(Node *x)
|
|||
|
|
{
|
|||
|
|
Node *tmp = x;
|
|||
|
|
while (tmp->ch[0] != null) tmp = tmp->ch[0];
|
|||
|
|
return tmp;
|
|||
|
|
}
|
|||
|
|
inline Node* getMax(Node *x)
|
|||
|
|
{
|
|||
|
|
Node *tmp = x;
|
|||
|
|
while (tmp->ch[1] != null) tmp = tmp->ch[1];
|
|||
|
|
return tmp;
|
|||
|
|
}
|
|||
|
|
// <20><>ѯ<EFBFBD><D1AF>k<EFBFBD><6B>
|
|||
|
|
inline Node* getKth(int k)
|
|||
|
|
{
|
|||
|
|
Node *tmp = root;
|
|||
|
|
assert(k > 0 && k <= root->size);
|
|||
|
|
while (true)
|
|||
|
|
{
|
|||
|
|
tmp->Push();
|
|||
|
|
if (tmp->ch[0]->size + 1 == k) return tmp;
|
|||
|
|
if (tmp->ch[0]->size >= k) tmp = tmp->ch[0];
|
|||
|
|
else k -= tmp->ch[0]->size + 1, tmp = tmp->ch[1];
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
// <20><><EFBFBD><EFBFBD>Ϊsplay<61><79><EFBFBD><EFBFBD>ƽ<EFBFBD><C6BD><EFBFBD><EFBFBD>ʹ<EFBFBD><CAB9>
|
|||
|
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>value = v<><76>Ԫ<EFBFBD><D4AA>, <20><><EFBFBD><EFBFBD>֮<EFBFBD><D6AE>splay
|
|||
|
|
inline Node* find(int v)
|
|||
|
|
{
|
|||
|
|
Node *tmp = root;
|
|||
|
|
while (tmp != null)
|
|||
|
|
{
|
|||
|
|
tmp->Push();
|
|||
|
|
if (tmp->value == v) return tmp;
|
|||
|
|
if (v < tmp->value) tmp = tmp->ch[0];
|
|||
|
|
else tmp = tmp->ch[1];
|
|||
|
|
}
|
|||
|
|
return null;
|
|||
|
|
}
|
|||
|
|
// ͳ<><CDB3><EFBFBD>ж<EFBFBD><D0B6><EFBFBD>Ԫ<EFBFBD><D4AA>С<EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD>v, <20><>flag = 1ʱ<31><CAB1>ͳ<EFBFBD>ƶ<EFBFBD><C6B6><EFBFBD>Ԫ<EFBFBD><D4AA><EFBFBD>ϸ<EFBFBD>С<EFBFBD><D0A1>v, һ<><D2BB>Ҫ<EFBFBD>ǵ<EFBFBD>splay<61><79><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ǹ<EFBFBD>tmp
|
|||
|
|
inline int Count(int v, bool flag = 0)
|
|||
|
|
{
|
|||
|
|
Node *tmp = root, *last = null;
|
|||
|
|
int ret = 0;
|
|||
|
|
while (tmp != null)
|
|||
|
|
{
|
|||
|
|
tmp->Push();
|
|||
|
|
last = tmp;
|
|||
|
|
if ((!flag && tmp->value > v) || (flag && tmp->value >= v))
|
|||
|
|
{
|
|||
|
|
tmp = tmp->ch[0];
|
|||
|
|
}
|
|||
|
|
else ret += tmp->ch[0]->size + 1, tmp = tmp->ch[1];
|
|||
|
|
}
|
|||
|
|
if (last != null) splay(last, null);
|
|||
|
|
return ret;
|
|||
|
|
}
|
|||
|
|
// ɾ<><C9BE>x<EFBFBD><78><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
inline void erase(Node* x)
|
|||
|
|
{
|
|||
|
|
splay(x, null);
|
|||
|
|
if (x->ch[0] == null || x->ch[1] == null)
|
|||
|
|
{
|
|||
|
|
int d = x->ch[1] != null;
|
|||
|
|
root = x->ch[d];
|
|||
|
|
root->p = null;
|
|||
|
|
return;
|
|||
|
|
}
|
|||
|
|
Node *L = getMax(x->ch[0]), *R = getMax(x->ch[1]);
|
|||
|
|
splay(L, x);
|
|||
|
|
splay(R, x);
|
|||
|
|
L->SetC(R, 1);
|
|||
|
|
L->p = null;
|
|||
|
|
root = L;
|
|||
|
|
L->Update();
|
|||
|
|
}
|
|||
|
|
// <20><><EFBFBD><EFBFBD>һ<EFBFBD><D2BB>ֵΪvalue<75>Ľڵ㣬<DAB5><E3A3AC>ʼҪ<CABC><D2AA>Insert(root, null, value)<29><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD>֮<EFBFBD><D6AE>splay
|
|||
|
|
inline Node* Insert(Node *&now, Node* father, int value)
|
|||
|
|
{
|
|||
|
|
if (now == null)
|
|||
|
|
{
|
|||
|
|
now = Renew(value);
|
|||
|
|
now->p = father;
|
|||
|
|
return now;
|
|||
|
|
}
|
|||
|
|
Node *ret;
|
|||
|
|
now->Push();
|
|||
|
|
if (value <= now->value) ret = Insert(now->ch[0], now, value);
|
|||
|
|
else ret = Insert(now->ch[1], now, value);
|
|||
|
|
now->Update();
|
|||
|
|
return ret;
|
|||
|
|
}
|
|||
|
|
// <20><><EFBFBD><EFBFBD>Ϊsplayά<79><CEAC><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20><>ʼҪ<CABC><D2AA>ԭ<EFBFBD><D4AD><EFBFBD><EFBFBD><EFBFBD>з<EFBFBD><D0B7><EFBFBD>һ<EFBFBD><D2BB>-inf<6E><66>inf<6E><66><EFBFBD><EFBFBD>ֹ<EFBFBD>߽<EFBFBD><DFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
// <20>õ<EFBFBD>ԭ<EFBFBD><D4AD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>[l,r]<5D><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ӧ<EFBFBD>Ľ<EFBFBD><C4BD>㣬<EFBFBD><E3A3AC><EFBFBD><EFBFBD>l == r + 1<><31><EFBFBD><EFBFBD>ʾ<EFBFBD><CABE>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
inline Node* getInterval(int l, int r)
|
|||
|
|
{
|
|||
|
|
assert(l <= r + 1);
|
|||
|
|
Node *L = getKth(l), *R = getKth(r + 2);
|
|||
|
|
splay(L, null);
|
|||
|
|
splay(R, L);
|
|||
|
|
return R->ch[0];
|
|||
|
|
}
|
|||
|
|
// ɾ<><C9BE>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>[l,r]
|
|||
|
|
inline void eraseInterval(int l, int r)
|
|||
|
|
{
|
|||
|
|
getInterval(l, r);
|
|||
|
|
root->ch[1]->ch[0] = null;
|
|||
|
|
root->ch[1]->Update();
|
|||
|
|
root->Update();
|
|||
|
|
}
|
|||
|
|
// <20><>λ<EFBFBD><CEBB>l<EFBFBD>ĺ<EFBFBD><C4BA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>x (0 <= l <= n)
|
|||
|
|
inline void insertInterval(int l, Node *x)
|
|||
|
|
{
|
|||
|
|
Node *L = getKth(l + 1), *R = getKth(l + 2);
|
|||
|
|
splay(L, null);
|
|||
|
|
splay(R, L);
|
|||
|
|
R->SetC(x, 0);
|
|||
|
|
R->Update();
|
|||
|
|
L->Update();
|
|||
|
|
}
|
|||
|
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>a<EFBFBD><61>[l,r]<5D><><EFBFBD><EFBFBD>Ϊһ<CEAA><D2BB>splay
|
|||
|
|
inline Node* Build(int l, int r, int a[])
|
|||
|
|
{
|
|||
|
|
if (l > r) return null;
|
|||
|
|
int mid = (l + r) >> 1;
|
|||
|
|
Node *ret = Renew(a[mid]);
|
|||
|
|
if (l == r) return ret;
|
|||
|
|
ret->SetC(Build(l, mid - 1, a), 0);
|
|||
|
|
ret->SetC(Build(mid + 1, r, a), 1);
|
|||
|
|
ret->Update();
|
|||
|
|
return ret;
|
|||
|
|
}
|
|||
|
|
} T;
|
|||
|
|
void clear(void)
|
|||
|
|
{
|
|||
|
|
data = POOL;
|
|||
|
|
T.root = null;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>㷨<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>飬ʱ<EFBFBD>临<EFBFBD>Ӷ<EFBFBD>Ϊ $O(n \lg n)$. ע<><D7A2><EFBFBD>ַ<EFBFBD><D6B7><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>յĺ<D5B5><EFBFBD><D7BA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> 1 <20><>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD>. Ҫ<><D2AA>֤<EFBFBD>ַ<EFBFBD><D6B7><EFBFBD><EFBFBD>ж<EFBFBD>Ϊ<EFBFBD><CEAA><EFBFBD><EFBFBD>0<EFBFBD><30><EFBFBD>ַ<EFBFBD>, <20><><EFBFBD><EFBFBD><EFBFBD>ַ<EFBFBD><D6B7><EFBFBD><EFBFBD>ĵ<EFBFBD>n+1λӦ<CEBB><D3A6>Ϊ0.
|
|||
|
|
// string is 1-base, sa is 1-base
|
|||
|
|
int w[MAXM];
|
|||
|
|
inline void Sort(int a[], int ret[], int n, int m = MAXM - 1)
|
|||
|
|
{
|
|||
|
|
for (int i = 0; i <= m; i++) w[i] = 0;
|
|||
|
|
for (int i = 1; i <= n; i++) w[a[i]]++;
|
|||
|
|
for (int i = 1; i <= m; i++) w[i] += w[i - 1];
|
|||
|
|
for (int i = n; i >= 1; i--) ret[w[a[i]]--] = i;
|
|||
|
|
}
|
|||
|
|
int wa[MAXN], wb[MAXN], tmp[MAXN];
|
|||
|
|
inline void getSA(int ch[], int sa[], int n)
|
|||
|
|
{
|
|||
|
|
int *x = wa, *y = wb;
|
|||
|
|
for (int i = 1; i <= n; i++) x[i] = ch[i];
|
|||
|
|
Sort(ch, sa, n);
|
|||
|
|
for (int j = 1, p = 1, m = MAXN - 1; p < n; m = p, j <<= 1)
|
|||
|
|
{
|
|||
|
|
p = 0;
|
|||
|
|
for (int i = n - j + 1; i <= n; i++) y[++p] = i;
|
|||
|
|
for (int i = 1; i <= n; i++) if (sa[i] > j) y[++p] = sa[i] - j;
|
|||
|
|
for (int i = 1; i <= n; i++) tmp[i] = x[y[i]];
|
|||
|
|
Sort(tmp, sa, n, m);
|
|||
|
|
for (int i = 1; i <= n; i++) sa[i] = y[sa[i]];
|
|||
|
|
swap(x, y);
|
|||
|
|
x[sa[1]] = p = 1;
|
|||
|
|
for (int i = 2; i <= n; i++)
|
|||
|
|
{
|
|||
|
|
if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) x[sa[i]] = p;
|
|||
|
|
else x[sa[i]] = ++p;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
sa[0] = n + 1; // for calculate height.
|
|||
|
|
}
|
|||
|
|
int rank[MAXN];
|
|||
|
|
inline void getHeight(int ch[], int sa[], int height[], int n)
|
|||
|
|
{
|
|||
|
|
for (int i = 1; i <= n; i++) rank[sa[i]] = i;
|
|||
|
|
for (int i = 1, t = 0; i <= n; i++)
|
|||
|
|
{
|
|||
|
|
if (t > 0) t--;
|
|||
|
|
while (ch[i + t] == ch[sa[rank[i] - 1] + t]) t++;
|
|||
|
|
height[rank[i]] = t;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Զ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͳ<EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵĴ<EFBFBD><EFBFBD><EFBFBD>ʱ<EFBFBD><EFBFBD>ֻ<EFBFBD><EFBFBD>ͳ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ӧ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>У<EFBFBD>endΪtrue<EFBFBD>Ľڵ<EFBFBD><EFBFBD>ĸ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ɡ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>нڵ㰴valֵ<EFBFBD><EFBFBD>С<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ɵõ<EFBFBD>parent<EFBFBD><EFBFBD><EFBFBD>ɸ<EFBFBD><EFBFBD><EFBFBD>ʼ<EFBFBD><EFBFBD>BFS<EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
|
|||
|
|
struct Node
|
|||
|
|
{
|
|||
|
|
Node *next[26], *par;
|
|||
|
|
int val, end; // 26 is volatile
|
|||
|
|
} POOL[MAXN << 1], *data, *root, *last; //Note that the size of POOL should be doubled.
|
|||
|
|
inline void Add(int x)
|
|||
|
|
{
|
|||
|
|
Node *p = last, *np = data++;
|
|||
|
|
np->val = p->val + 1;
|
|||
|
|
np->end = true;
|
|||
|
|
while (p && !p->next[x])
|
|||
|
|
p->next[x] = np, p = p->par;
|
|||
|
|
if (p == 0)
|
|||
|
|
{
|
|||
|
|
np->par = root;
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
Node *q = p->next[x];
|
|||
|
|
if (q->val == p->val + 1)
|
|||
|
|
{
|
|||
|
|
np->par = q;
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
Node *nq = data++;
|
|||
|
|
nq->val = p->val + 1;
|
|||
|
|
memcpy(nq->next, q->next, sizeof q->next);
|
|||
|
|
nq->par = q->par;
|
|||
|
|
np->par = q->par = nq;
|
|||
|
|
while (p && p->next[x] == q)
|
|||
|
|
p->next[x] = nq, p = p->par;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
last = np;
|
|||
|
|
}
|
|||
|
|
void Clear(void)
|
|||
|
|
{
|
|||
|
|
data = POOL;
|
|||
|
|
last = root = data++;
|
|||
|
|
}
|
|||
|
|
|