本篇内容介绍了“PHP树链剖分+函数式线段树代码怎么写”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
#include #include #include #include #include #include #include using 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 <= l && R >= r) return RT->siz-LF->siz; int res = 0; int m = MID; if (L <= m) res += query(LF->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 <= m) { cur->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<= NA.n; ++i) scanf("%d", &u), mp[u] = NA.pos[i]; scanf("%d", &NB.n); for (int i = 1; i< NB.n; ++i) { scanf("%d", &u); NB.add(u, i+1); } NB.dfs1(1, 0); NB.dfs2(1, 1); for (int i = 1; i<= NB.n; ++i) { scanf("%d", &u); itp[NB.pos[i]] = mp.count(u)?mp[u]:0; } build(root[0], 1, NA.n); for (int i = 1; i<= NB.n; ++i) { if (itp[i]) insert(root[i], root[i-1], itp[i], 1, NA.n); else root[i] = root[i-1]; } scanf("%d", &q); while (q--) { scanf("%d%d%d%d", &u, &v, &a, &b); ns = 0; NA.search(u, v); printf("%d\n", NB.solve(a, b, seg, NA.n)); } } return 0; }
“PHP树链剖分+函数式线段树代码怎么写”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
在线咨询
拨打电话
