题解 P5210 【[ZJOI2017]线段树】

· · 题解

丢人全局平衡二叉树，打不过树剖套树状数组……

这份评测记录是O(nlogn)的全局平衡二叉树

这份评测记录是O(nlog^2n)的树剖套树状数组

常数差别立判高下……

先说好这题是有结论的但是我懒了所以这题的后半部分我直接用数据结构硬上了……

想知道那个神奇的结论的同学可以去康题解

本题题解

题意已经肥肠清楚了，此处无需赘述了

那么我们首先需要理解线段树的"拆分"操作的本质究竟是什么

事实上有这样一个结论，线段树的拆分代码当中，之多有一次同时向左向右递归，其他情况下都是不断的向左递归和向右递归

并且，同时向左向右递归的那个节点就是节点(l,l)和(r,r)在线段树上的lca，因为lca的划分点一定分开了l和r

所以我们线段树的拆分的实质就是在lca处将(l,r)分成了(l,lca.mid)和(lca.mid,r)这两个区间

那么我们考虑lca的左子树和右子树，你会发现接下来我们要做的事情就是在lca的左子树(lca.l,lca.mid)拆分(l,lca.mid)这个区间以及在lca的右子树(lca.mid,lca.r)处拆分(lca.mid,r)这个区间

那么你会发现相对于lca的左子树来讲我们拆分的是一个后缀。

相对于lca的右子树来讲我们拆分的区间是一个前缀

那么我们将拆分区间转化成了拆分前缀和后缀之后又有什么用呢？

下面我们来研究一下拆分前缀时的性质，后缀与之类似

当我们拆分的区间是一个前缀的时候，我们发现拆分出来的节点都是左儿子，除非我们拆的是(1,n)这个前缀，此时我们选择的节点是根节点

因此我们可以仅仅保留线段树的所有左儿子，这样我们就得到了这样的一个树

wow，我们得到了一株树状数组！

事实上树状数组本质上就是仅仅保留左儿子的zkw线段树

回想一下树状数组的查找前缀代码


for(int x=p;x;x-=x&(-x))res+=ta[x];

你会发现我们其实做的事情就是每次将x迭代成x-lowbit(x)，这东西可以理解成一个不断向上跳父亲的过程，换句话说，如果我们将树状数组中的节点x和x-lowbit(x)连边，我们就得到了一颗"前缀树",其中(1,x)的拆分就是点x到0路径上的所有节点

那么我们现在也需要处理拆分前缀和后缀，所以我们需要建出来一个类似于广义树状数组一类的东西，由于现在是一颗普普通通的线段树，所以没有lowbit这么nb的东西可以帮助我们找父亲了，我们必须手动把树状数组建出来

这里以建前缀树状数组为例，注意一个节点在树状数组上的父亲和在线段树上的父亲不同

在线段树上dfs，假设我们dfs到了p，并且已经知道了这个节点在树状数组上的father是谁

我们先dfsp的左儿子，并且左儿子的father和p的father相同

然后我们dfsp的右儿子，将右儿子的father设成左儿子

然后删掉所有在线段树上是右儿子的点，我们就得到了一颗广义树状数组，这个算法的正确性可以大力归纳法证明一下，如果整不出来还可以手玩一下

那么我们发现当我们在线段树的一个子树当中拆分一个前缀的时候，我们拆分出来的节点在广义树状数组上是一条直上直下的路径

所以现在的问题就是有两颗树，每次给出一个点集S(u,v)和一个询问点p，询问

\sum_{q \in S(u,v)} T1.dis(p,q)

而S(u,v)指的是第二颗树上u到v路径上的所有点构成的集合，保证u是v的祖先

那么我们解决问题的手段非常简单粗暴

\sum_{q \in S(u,v)} dep(p)+dep(q)-2dep(T1.lca(p,q)) |S(u,v)|dep(p)+\sum_{q \in S(u,v)}dep(q)-2\sum_{q \in S(u,v)}dep(T1.lca(p,q))

好了接下来是一个经典问题，如何求一个点到一堆点的lca深度之和呢？

答案是让这一堆点都做一个到根的路径+1的链加操作，最后求询问点到根路径的和就是这个点到这一堆点的lca深度之和了，正确自己画图玩玩就出来了

那么我们就有了解决这个问题的思路了

现在我们希望被执行链加的集合是S(u,v)，那么我们将询问离线，然后拆成S(1,v)-S(1,fa(u))这两个询问，我们需要做的就是快速回答S(1,p)这样的询问

在第二颗树上dfs，dfs到u的时候让u到根的路径上+1，dfs完u之后让u到根的路径上-1，如此这般处理，我们在dfs到u的时候只有u在第二颗路径上到根的点在第一颗树上被做了路径+1的操作，此时我们询问一下询问点到根的和就可以回答S(1,u)这样的询问了

所以我们需要实现的底层数据结构就是一个资瓷链加和链上求和的数据结构，如果我们使用全局平衡二叉树的话我们可以达到O(nlogn)的优秀复杂度，然鹅现实是这东西太丢人了……

所以我们选择树剖套树状数组，常数小并且好写~

现在唯一的问题是如何快速的将一个区间(l,r)拆成树状数组上的一条路径

首先由于我们仅仅保留了所有的左儿子和根节点，因此所有节点的右端点互不相同，那么我们可以对于每一个右端点记录一下它对应着那个节点，这样我们就找到了底下的节点了，接下来我们在树状数组上倍增一下就能找到另外一个节点了

然后这题就做完了，细节方面就是特判一下lca就是拆分节点以及拆分前缀后缀的时候如果拆出来的是lca左右儿子那么这个点可以不在树状数组上

复杂度O(nlogn)/O(nlog^2n)

上代码~

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;const int N=4*1e5+10;typedef long long ll;struct opt{int id;int u;};
template <typename T>
inline void gm(T*& bas,int siz,T*& op){op=bas;bas+=siz;}int n;int m;ll ans[N];int dep[N];
namespace INPUT_SPACE{
    const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
    char gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; }
    inline int inn()
    {
        int x,ch,sgn=1;while(((ch=gc())<'0'||ch>'9')&&ch!='-');
        if(ch=='-') sgn=-1,x=0;else x=ch^'0';
        while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');
        return x*sgn;
    }
}using INPUT_SPACE::inn;
namespace Tree
{
    ll B_bas[N<<1];ll* B_t;int A_bas[N<<1];int* A_t;int id[N];
    struct tra//树状数组支持区间加区间求和 
    {
        int* ta1;ll* ta2;int len;
        inline void stadd(int pos,int pl)
        {
            for(int x=pos;x;x-=x&(-x))ta1[x]+=pl;pl*=pos;
            for(int x=pos;x<=len;x+=x&(-x))ta2[x]+=pl;
        }
        inline ll sum(int pos)
        {
            ll res1=0;for(int x=pos+1;x<=len;x+=x&(-x))res1+=ta1[x];
            ll res2=0;for(int x=pos;x;x-=x&(-x))res2+=ta2[x];return pos*res1+res2;
        }
        inline void cbuild(int* q,int tot)
        {len=tot;gm(B_t,tot+1,ta2);gm(A_t,tot+1,ta1);for(int i=1;i<=len;i++)id[q[i]]=i;}
    }lt[N];int v[N<<1];int x[N<<1];int ct;int al[N];int siz[N];int top[N];
    int h[N];int fa[N];int q[N];int hd;
    inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
    inline int dfs(int u)
    {
        for(int i=al[u];i;i=x[i])
            fa[v[i]]=u,siz[u]+=dfs(v[i]),h[u]=(siz[v[i]]>siz[h[u]])?v[i]:h[u];return ++siz[u];
    }
    inline void solve(int u)
    {
        for(int p=u;p;p=h[p])
            for(int i=al[p];i;i=x[i])if(v[i]!=h[p])solve(v[i]);hd=0;
        for(int p=u;p;p=h[p])q[++hd]=p,top[p]=u;lt[u].cbuild(q,hd);
    }
    inline void modi(int u,int pl){for(int p=u;p;p=fa[top[p]])lt[top[p]].stadd(id[p],pl);}
    inline ll qry(int u){ll res=0;for(int p=u;p;p=fa[top[p]])res+=lt[top[p]].sum(id[p]);return res;}
}
namespace Tree1//广义树状数组 
{
    int v[N<<1];int x[N<<1];int ct;int al[N];vector <opt> ve[N];
    inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
    inline void pb(int u,opt nod){ve[u].push_back(nod);}
    inline void dfs(int u,ll sum,int cnt)
    {
        sum+=dep[u];cnt++;Tree::modi(u,1);
        for(vector <opt>:: iterator it=ve[u].begin();it!=ve[u].end();++it)
        {
            int op=(it->u<0)?-1:1;it->u*=op;
            ans[it->id]+=op*(sum+(ll)cnt*(dep[it->u]+2)-2*Tree::qry(it->u));
        }for(int i=al[u];i;i=x[i])dfs(v[i],sum,cnt);Tree::modi(u,-1);
    }
    inline void clr()
    {for(int i=1;i<=n;i++)al[i]=0;ct=0;for(int i=1;i<=n;i++)ve[i].clear();}
}
namespace SegTree
{
    int mid[N];int s[N][2];int fa[N][22];int pl[N];int pr[N];int sfa[N];
    int ct;int fuc[N];int bas[N];struct qry{int u;int l;int r;int lc;}qr[N];
    inline void ctr(int p,int l,int r)
    {
        for(int i=0;fa[p][i];i++)fa[p][i+1]=fa[fa[p][i]][i];
        pl[p]=l+1;pr[p]=r;bas[r]=p;if(r-l==1)return;mid[p]=inn();
        s[p][0]=++ct;fa[ct][0]=p;dep[ct]=dep[p]+1;ctr(ct,l,mid[p]);
        s[p][1]=++ct;fa[ct][0]=p;dep[ct]=dep[p]+1;ctr(ct,mid[p],r);
    }
    inline void csuf(int p,int f,int tp)//建后缀树 
    {
        if(tp==1){if(f)Tree1::add(f,p),sfa[p]=f;fuc[pl[p]]=p;}
        if(s[p][0])csuf(s[p][0],s[p][1],0),csuf(s[p][1],f,1);
    }
    inline void cpre(int p,int f,int tp)//建前缀树 
    {
        if(tp==0){if(f)Tree1::add(f,p),sfa[p]=f;fuc[pr[p]]=p;}
        if(s[p][1])cpre(s[p][1],s[p][0],1),cpre(s[p][0],f,0);
    }
    inline int lca(int u,int v)
    {
        if(dep[u]<dep[v])swap(u,v);for(int d=dep[u]-dep[v],i=0;d;d>>=1,i++)if(d&1)u=fa[u][i];
        if(u==v)return u;for(int i=19;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
        return fa[u][0];
    }
    inline void mainsolve()
    {
        n=inn();ct=1;ctr(1,0,n);m=inn();
        for(int i=1;i<=m;i++)qr[i].u=inn(),qr[i].l=inn(),qr[i].r=inn();
        for(int i=1;i<=ct;i++)if(s[i][0])Tree::add(i,s[i][0]),Tree::add(i,s[i][1]);
        Tree::dfs(1);Tree::solve(1);//前后各做一次树上差分 
        for(int i=1;i<=m;i++)qr[i].lc=lca(bas[qr[i].l],bas[qr[i].r]);csuf(1,0,1);
        for(int z=1,l,r,p;z<=m;z++)
        {
            l=qr[z].l;r=qr[z].r;p=qr[z].lc;if(l==pl[p]&&r==pr[p])continue;
            if(l==pl[p]){ans[z]+=dep[qr[z].u]+dep[s[p][0]]-2*dep[lca(qr[z].u,s[p][0])];continue;}
            Tree1::pb(fuc[l],(opt){z,qr[z].u});int t=bas[mid[p]];
            for(int i=19;i>=0;i--)if(fa[t][i]&&l<=pl[fa[t][i]])t=fa[t][i];
            if(sfa[t])Tree1::pb(sfa[t],(opt){z,-qr[z].u});
        }for(int p=1;p;p=s[p][1])Tree1::dfs(p,0,0);Tree1::clr();
        for(int i=1;i<=n;i++)sfa[i]=0;cpre(1,0,0);
        for(int z=1,l,r,p;z<=m;z++)
        {
            l=qr[z].l;r=qr[z].r;p=qr[z].lc;if(l==pl[p]&&r==pr[p])continue;
            if(r==pr[p]){ans[z]+=dep[qr[z].u]+dep[s[p][1]]-2*dep[lca(qr[z].u,s[p][1])];continue;}
            Tree1::pb(fuc[r],(opt){z,qr[z].u});int t=bas[mid[p]+1];
            for(int i=19;i>=0;i--)if(fa[t][i]&&pr[fa[t][i]]<=r)t=fa[t][i];
            if(sfa[t])Tree1::pb(sfa[t],(opt){z,-qr[z].u});
        }for(int p=1;p;p=s[p][0])Tree1::dfs(p,0,0);
        for(int z=1,l,r,p;z<=m;z++)
        {
            l=qr[z].l;r=qr[z].r;p=qr[z].lc;
                if(l==pl[p]&&r==pr[p])ans[z]=dep[qr[z].u]+dep[p]-2*dep[lca(qr[z].u,p)];
        }for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
    }
}int main(){Tree::B_t=Tree::B_bas;Tree::A_t=Tree::A_bas;SegTree::mainsolve();return 0;}//拜拜程序~