孔爷的杂题系列；LCT清新题/ODT模板题
题目大意
定义一颗无根树的燃烧序列为：每次选取编号最小的叶子节点形成的序列。
要求支持操作：查询一个点$u$在燃烧序列中的排名；将一个点的编号变成最大
$n \le 200000$
题目分析
首先初始的燃烧序列容易构造，那么考虑进行一次up操作对序列会产生什么影响。
这里对$3$进行一次$up$，得到下图。
容易发现，记上一个版本序列最后一个元素为$las$，进行$up\,\,\,x$相当于是把路径$(las,x)$的答案变成从$las$到$x$的等差数列。因为$x$被$up$之后，这条路径只能从另一端的$las$走过来。
等差数列用线段树容易维护，这里讲一种ODT维护的方式：将路径$(las,x)$染为一种新颜色$c$，查询答案就是$1..c-1$颜色种类数+$dis(las,x)+1$.
那么就是一道难得的ODT+树剖模板题了。
关于下面132行的细节处理：写成root[i-1]=root[i]=u是因为对于初始序列，查询时候要保持dist(u, root[c-1])=0；但是对于之后修改的询问root[n]应该为n。
1 #include 2 const int maxn = 200035; 3 const int maxm = 400035; 4 5 struct node 6 { 7 int l,r,val; 8 node(int a=0, int b=0, int c=0):l(a),r(b),val(c) {} 9 bool operator < (node a) const 10 { 11 return l < a.l; 12 } 13 }; 14 struct point 15 { 16 int fa,son,top,tot; 17 }a[maxn]; 18 char opt[13]; 19 int n,m,tim,lst,chain[maxn],chTot,root[maxn<<1]; 20 int edgeTot,head[maxn],nxt[maxm],edges[maxm],deg[maxn],dep[maxn]; 21 std::set s[maxn]; 22 std::priority_queue
, std::greater
> q; 23 typedef std::set
::iterator itr; 24 namespace BIT 25 { 26 int f[maxn<<1]; 27 void add(int x, int c){ for (x+=5; x<=n+m+5; x+=x&-x) f[x] += c;} 28 int query(int x) 29 { 30 int ret = 0; 31 for (x+=5; x; x-=x&-x) ret += f[x]; 32 return ret; 33 } 34 }; 35 36 int read() 37 { 38 char ch = getchar(); 39 int num = 0, fl = 1; 40 for (; !isdigit(ch); ch=getchar()) 41 if (ch=='-') fl = -1; 42 for (; isdigit(ch); ch=getchar()) 43 num = (num<<1)+(num<<3)+ch-48; 44 return num*fl; 45 } 46 void addedge(int u, int v) 47 { 48 ++deg[u], ++deg[v]; 49 edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot; 50 edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot; 51 } 52 void dfs1(int x, int fa) 53 { 54 a[x].fa = fa, a[x].tot = 1; 55 a[x].son = a[x].top = -1, dep[x] = dep[fa]+1; 56 for (int i=head[x]; i!=-1; i=nxt[i]) 57 { 58 int v = edges[i]; 59 if (v==fa) continue; 60 dfs1(v, x), a[x].tot += a[v].tot; 61 if (a[x].son==-1||a[a[x].son].tot < a[v].tot) a[x].son = v; 62 } 63 } 64 void dfs2(int x, int top) 65 { 66 if (x==top) s[x].insert(node(n+1, n+1, 0)); 67 chain[x] = ++chTot, a[x].top = top; 68 if (a[x].son==-1) return; 69 dfs2(a[x].son, top); 70 for (int i=head[x]; i!=-1; i=nxt[i]) 71 if (edges[i]!=a[x].fa&&edges[i]!=a[x].son) 72 dfs2(edges[i], edges[i]); 73 } 74 int Lca(int u, int v) 75 { 76 while (a[u].top!=a[v].top) 77 { 78 if (dep[a[u].top] > dep[a[v].top]) std::swap(u, v); 79 v = a[a[v].top].fa; 80 } 81 if (dep[u] > dep[v]) std::swap(u, v); 82 return u; 83 } 84 int dist(int u, int v) 85 { 86 int anc = Lca(u, v); 87 return dep[u]+dep[v]-(dep[anc]<<1); 88 } 89 itr split(int i, int pos) 90 { 91 itr loc = s[i].lower_bound(node(pos)); 92 if (loc!=s[i].end()&&loc->l==pos) return loc; 93 int l = (--loc)->l, r = loc->r, val = loc->val; 94 s[i].erase(loc), s[i].insert(node(l, pos-1, val)); 95 return s[i].insert(node(pos, r, val)).first; 96 } 97 void insert(int i, int l, int r, int c) 98 { 99 itr rpos = split(i, r+1), lpos = split(i, l);100 for (itr it=lpos; it!=rpos; ++it)101 BIT::add(it->val, -(it->r-it->l+1)); //遍历清除历史颜色102 s[i].erase(lpos, rpos);103 BIT::add(c, r-l+1);104 s[i].insert(node(l, r, c));105 }106 void chainModify(int u, int v)107 {108 while (a[u].top!=a[v].top)109 {110 if (dep[a[u].top] > dep[a[v].top]) std::swap(u, v);111 insert(a[v].top, chain[a[v].top], chain[v], tim);112 v = a[a[v].top].fa;113 }114 if (dep[u] > dep[v]) std::swap(u, v);115 insert(a[u].top, chain[u], chain[v], tim);116 }117 int query(int u)118 {119 int c = split(a[u].top, chain[u])->val;120 return BIT::query(c-1)+dist(u, root[c-1])+1; //查询答案 root[c-1]是指上一个历史版本的最后一个元素las121 }122 int main()123 {124 memset(head, -1, sizeof head);125 n = read(), m = read();126 for (int i=1; i