导航：首页 > 开发技术 >

PHP树链剖分+函数式线段树代码怎么写

发表于：2025-01-19 作者：千家信息网编辑

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

千家信息网最后更新 2025年01月19日PHP树链剖分+函数式线段树代码怎么写

本篇内容介绍了"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 <= 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树链剖分+函数式线段树代码怎么写"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！

很赞哦！