首页 > 代码库 > HDU4718 The LCIS on the Tree(LCT)
HDU4718 The LCIS on the Tree(LCT)
又是一枚LCT,写一发加深一下对LCT的理解。本题的坑爹之处就在于，它实在是太坑爹了。询问的是树路径上的最长连续上升的子串，考验的是怎么样去维护。一开始的想法是维护三个变量 ls,rs,mxl,分别表示左起最长上升，右末最长上升，以及总的最长上升，那么最长上升一定是可以在下面的条件下求到的，
mxl=max(ch[0]->mxl,ch[1]->mxl) 以及
令temp=1 存一下左右区间的左右lval,rval,
if val>ch[0]->rval temp+=ch[0]->rs
if val<ch[1]->lval temp+=ch[1]->ls
但是由于提路径的时候必须要转根，转根的时候区间要有翻转标记，所以要维护信息必须还要知道左起最长下降ld，右末最长下降rd,以及区间总的最长下降mxd.那么每次reverse的时候就可以:
swap(lval,rval) swap(ls,rd) swap(rs,ld) swap(mxl,mxd)。
但是坑爹就在于我们还要特别处理一下各种null，所以本题的坑爹之处很大在于怎么写好这个upd函数。反正我的upd写了100行。。我心都碎了。。。
#pragma warning(disable:4996)#include <iostream>#include <cstring>#include <string>#include <vector>#include <cmath>#include <cstdio>#include <algorithm>using namespace std;#define ll long long#define maxn 150000#define INF 1500000000#define NINF -1struct Node{ Node *p, *ch[2]; bool rev; int val,size; int lval, rval; int ls, rs, mxl; int ld, rd, mxd; bool isRoot; Node *fa; Node(){ val = 0; size = 0; ls = rs = mxl = 0; ld = rd = mxd = 0; lval = INF; rval = NINF; isRoot = 0; } void setc(Node *c, int d){ ch[d] = c; c->p = this; } bool d(){ return p->ch[1] == this; } void upd(); void relax(); void revIt(); void setRoot(Node *f);}Tnull,*null=&Tnull;void Node::upd(){ size = ch[0]->size + ch[1]->size + 1; lval = ch[0] != null ? ch[0]->lval : val; rval = ch[1] != null ? ch[1]->rval : val; if (ch[0] == null){ if (ch[1] == null) ls = ld = 1; else{ ls = 1; ld = 1; if (val < ch[1]->lval) ls += ch[1]->ls; if (val > ch[1]->lval) ld += ch[1]->ld; } } else{ if (ch[0]->ls == ch[0]->size){ ls = ch[0]->size; if (ch[0]->rval < val){ ls += 1; if (val < ch[1]->lval){ ls += ch[1]->ls; } } } else{ ls = ch[0]->ls; } if (ch[0]->ld == ch[0]->size){ ld = ch[0]->size; if (ch[0]->rval > val){ ld += 1; if (val > ch[1]->lval){ ld += ch[1]->ld; } } } else { ld = ch[0]->ld; } } if (ch[1] == null){ if (ch[0] == null) rd = rs = 1; else{ rd = rs = 1; if (val > ch[0]->rval) rs += ch[0]->rs; if (val < ch[0]->rval) rd += ch[0]->rd; } } else{ if (ch[1]->rs == ch[1]->size){ rs = ch[1]->size; if (val < ch[1]->lval){ rs += 1; if (val>ch[0]->rval){ rs += ch[0]->rs; } } } else{ rs = ch[1]->rs; } if (ch[1]->rd == ch[1]->size){ rd = ch[1]->size; if (val > ch[1]->lval){ rd += 1; if (val < ch[0]->rval){ rd += ch[0]->rd; } } } else{ rd = ch[1]->rd; } } mxl = max(ch[0]->mxl, ch[1]->mxl); mxd = max(ch[0]->mxd, ch[1]->mxd); int temp = 1; if (ch[0] != null&&val > ch[0]->rval) temp += ch[0]->rs; if (ch[1] != null&&val < ch[1]->lval) temp += ch[1]->ls; mxl = max(mxl, temp); temp = 1; if (ch[0] != null&&val < ch[0]->rval) temp += ch[0]->rd; if (ch[1] != null&&val>ch[1]->lval) temp += ch[1]->ld; mxd = max(mxd, temp);}void Node::revIt(){ swap(ch[0], ch[1]); swap(lval, rval); swap(ls, rd); swap(rs, ld); swap(mxl, mxd); rev ^= 1;}void Node::setRoot(Node *f){ fa = f; isRoot = true; p = null;}void Node::relax(){ if (rev){ for (int i = 0; i < 2; i++){ if (ch[i] != null) ch[i]->revIt(); } rev = 0; }}Node mem[maxn], *C = mem;Node *make(int v){ C->lval = C->rval = C->val = v; C->ls = C->rs = C->mxl = 1; C->ld = C->rd = C->mxd = 1; C->rev = 0; C->ch[0] = C->ch[1] = null; C->isRoot = true; C->p = C->fa = null; return C++;}void rot(Node *t){ Node *p = t->p; p->relax(); t->relax(); bool d = t->d(); p->p->setc(t, p->d()); p->setc(t->ch[!d], d); t->setc(p, !d); p->upd(); if (p->isRoot){ p->isRoot = false; t->isRoot = true; t->fa = p->fa; }}void pushTo(Node *t){ static Node *stk[maxn]; int top = 0; while (t != null){ stk[top++] = t; t = t->p; } for (int i = top - 1; i >= 0; i--) stk[i]->relax();}void splay(Node *u, Node *f = null){ pushTo(u); while (u->p != f){ if (u->p->p == f) rot(u); else u->d() == u->p->d() ? (rot(u->p), rot(u)) : (rot(u), rot(u)); } u->upd();}Node *v[maxn];vector<int> G[maxn];int n, nQ;int que[maxn], fa[maxn], qh = 0, qt = 0;int wht[maxn];void bfs(){ qh = qt = 0; que[qt++] = 1; while (qh < qt){ int u = que[qh++]; int e; for (int i = 0; i < G[u].size(); i++){ e = G[u][i]; if (e != fa[u]){ v[e]->fa = v[u]; que[qt++] = e; } } }}Node *expose(Node *u){ Node *v; for (v = null; u != null; v = u, u = u->fa){ splay(u); u->ch[1]->setRoot(u); u->setc(v, 1); v->fa = u; } return v;}void makeRoot(Node *u){ expose(u); splay(u); u->revIt();}int main(){ int T; cin >> T; int ca = 0; while (T--){ scanf("%d", &n); C = mem; for (int i = 1; i <= n; i++){ scanf("%d", wht + i); v[i] = make(wht[i]); G[i].clear(); } fa[1] = -1; int ti; for (int i = 2; i <= n; i++){ scanf("%d", &ti); fa[i] = ti; G[i].push_back(ti); G[ti].push_back(i); } bfs(); scanf("%d", &nQ); int ui, vi; Node *nu, *nv; printf("Case #%d:\n", ++ca); for (int i = 0; i < nQ; i++){ scanf("%d%d", &ui, &vi); nu = v[ui]; nv = v[vi]; makeRoot(nu); expose(nv); splay(nv); printf("%d\n", nv->mxl); } if (T != 0) puts(""); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。