How to write PHP Tree chain Partition + functional Segment Tree Code

本篇内容介绍了"PHP树链剖分+函数式线段树代码怎么写"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读，能够学有所成!

#include#include#include#include#include#include#includeusing namespace std;#define MID ( (l+r)>>1 )#pragma comment(linker, "/STACK:1024000000,1024000000")const int MAXN = 100005;map mp;int itp[MAXN];struct _edge{ int v, next; _edge(int _v=0, int _next=-1):v(_v),next(_next) {}};struct _seg{ int l, r; _seg(int ll=0, int rr=0):l(ll),r(rr) {}} seg[MAXN];int ns;struct FTree{ FTree* ch[2]; int siz;} *root[MAXN], da[MAXN*50], *nf;void build(FTree *& cur, int l, int r){ cur = nf++; cur->siz = 0; if (l == r) return; int m = MID; build(cur->ch[0], l,m); build(cur->ch[1], m+1,r);}int query(FTree* LF, FTree* RT, int L, int R, int l, int r){ if (L = r) return RT->siz-LF->siz; int res = 0; int m = MID; if (L ch[0], RT->ch[0], L,R,l,m); if (R > m) res += query(LF->ch[1], RT->ch[1], L,R,m+1,r); return res;}struct node{ int head[MAXN], cnt, n; _edge e[MAXN]; int son[MAXN], siz[MAXN], top[MAXN], fa[MAXN], dep[MAXN], pos[MAXN], np; void clear() { cnt = 0; memset(head, -1, sizeof head); np = 0; } void add(int u, int v) { e[cnt] = _edge(v, head[u]); head[u] = cnt++; } void dfs1(int u, int pre) { fa[u] = pre; dep[u] = dep[pre] + 1; siz[u] = 1; son[u] = 0; for (int i = head[u]; ~i; i=e[i].next) { int v = e[i].v; dfs1(v, u); siz[u] += siz[v]; if (siz[son[u]]

< siz[v]) son[u] = v; } } void dfs2(int u, int pre) { top[u] = pre; pos[u] = ++np; if (!son[u]) return; dfs2(son[u], pre); for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].v; if ( v!=son[u]) dfs2(v, v); } } void search(int u, int v) { while (top[u] != top[v]) { if (dep[top[u]] >

dep[top[v]]) swap(u,v); seg[ns++] = _seg(pos[top[v]], pos[v]); v = fa[top[v]]; } if (dep[u] > dep[v]) swap(u, v); seg[ns++] = _seg(pos[u], pos[v]); } int solve(int u, int v, _seg seg[], int m) { int res = 0; while (top[u] != top[v]) { if (dep[top[u]] > dep[top[v]]) swap(u,v); for (int i = 0; i

< ns; ++i) res += query(root[pos[top[v]]-1], root[pos[v]], seg[i].l, seg[i].r, 1, m); v = fa[top[v]]; } if (dep[u] >

dep[v]) swap(u, v); for (int i = 0; i

< ns; ++i) res += query(root[pos[u]-1], root[pos[v]], seg[i].l, seg[i].r, 1, m); return res; }} NA, NB;void insert(FTree* &cur, FTree* old, int x, int l, int r){ cur = nf++; if (l == r) { cur->

siz = old->siz + 1; return; } int m = MID; if (x ch[1] = old->ch[1]; insert(cur->ch[0], old->ch[0], x, l, m); } else { cur->ch[0] = old->ch[0]; insert(cur->ch[1], old->ch[1], x, m+1,r); } cur->siz = cur->ch[0]->siz + cur->ch[1]->siz;}void init(){ NA.clear(); NB.clear(); mp.clear(); nf = da; memset(root, 0, sizeof root);}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif int u, q, v, a, b; while (scanf("%d", &NA.n) != EOF) { init(); for (int i = 1; i< NA.n; ++i) { scanf("%d", &u); NA.add(u, i+1); } NA.dfs1(1, 0); NA.dfs2(1, 1); for (int i = 1; i