自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 22:02:00，当前版本为作者最后更新于2018-06-03 14:06:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

SDOI2018全部做完一遍祭

感觉是R2六道题中最精神污染的一道……

慢慢肝吧……

claris的树状数组题解太神啦没有看懂……

所以我们这里介绍一个简(chao)单(ji)易(nan)懂(xie)的主席树做法

---

前置芝士:主席树(可持久化线段树,可持久化数组)

什么敢刚SD二轮题不会主席树?

出门左转luogu膜板区

本题题解

题目简单易懂,树上数颜色

如果只有操作1的显然可以树上莫队莽过去

但是我们有可爱的操作2此时的操作就略显辣手了

但是你仔细看一眼会发现数据是ran出来的!

这意味着一件事情,任意一个点到主链的距离均是O(logn)级别的

另外一件事情就是每种颜色的种类是O(1)级别的

因此我们的思路就是把这个树上问题变成序列问题，抽取路径的上的一条长链用序列上的数据结构进行维护

剩余的O(logn)个散点暴力插入，这样的话我们最后的复杂度是$O(nlog^2n)$的

所以让我们先来考虑一下序列上的问题~

序列问题

操作1

当然你可以直接莫队莽过去

但是这是序列，我们考虑一个优雅一点的log做法

这里有一个十分经典的套路叫只数每个颜色左侧第一个点

为此我们记$pre_{i}$表示i左侧第一个和它同色点的位置,如果这样的点不存在的话$pre_{i}=0$

那么一个点i是$[l,r]$中的左侧第一个点当且仅当$pre_{i}<l$

问题变成了查询区间中$pre_{i}<l$的点的个数

主席树经典问题,一个主席树即可解决了

操作2

在序列上操作2的限制变成了要求x在[1,A]之间,y在[1,B]之间了

讲一句很不要脸的话,我们考虑贡献(因为大部分时候你都是不知道怎么考虑的)!

原来是枚举每一个询问考虑有多少个点对这个询问产生了贡献

现在我们是枚举每一个点看有多少个有效询问覆盖它

然后分两种情况讨论

case1:i在(A,B]之间

此时我们发现i产生了贡献的询问必须满足3个条件

1.$pre_{i}<A$

2.左端点在$(pre_{i},A]$之间

3.右端点在$[i,B]$之间

所以这样的询问一共有$(A-pre_{i})(B-i+1)$种

拆一下式子就是点i的贡献是$[pre_{i}<A](A(B+1)-pre_{i}(B+1)-Ai+ipre_{i})$

case2:i在[1,A]之间

case 2.1:左端点是x

此时我们发现i产生了贡献的询问必须满足两个条件

1.左端点在$(pre_{i},i)$之间

2.右端点在$[i,B]$之间

所以这样的询问有$(i-pre_{i})(B-i+1)$种

case 2.2:左端点是y

此时我们发现i产生了贡献的询问必须满足两个条件

1.左端点在$(pre_{i},i)$之间

2.左端点在$[i,A]$之间

所以这样的询问一共有$(i-pre_{i})(B-i+1)$种

那么我们把两个点的贡献加起来点i的贡献就是

$(i-pre_{i})(A+B)+(i-pre_{i})(-2i+2)-1$减1是为了避免重复计算$(i,i)$这个询问

那么我们发现case2的贡献可以轻易的使用前缀和O(1)的进行维护

而case1的贡献可以使用主席树维护$(1,i,pre_{i},ipre_{i})$的和来进行维护

那么我们的操作2就解决啦~

---

序列上树

操作1

我们发现一个非常神奇的性质，这棵树任意两点间的路径，他们的lca总是离一个点特别近，近到了$O(logn)$的级别

假设我们处理一个$(x,y)$的询问(假设lca离x更近)，那么我们先建一个树形主席树，然后这样就可以快速查出(lca,y)的颜色种类数，这里的pre你可以每种颜色开一个栈在dfs的时候顺手维护一下

此时我们枚举(x,lca)路径上的点，查询这种颜色是否在(lca到y)上出现过

问题来了怎么查询？

你当然可以把这问题转化为一个查询区间里某种颜色出现多少次，然后树形主席树大力维护即可

可是我们的操作2还需要一些奇奇怪怪的信息来维护，因此我们考虑另一种方法来进行查询工作

我们建一个树形的可持久化数组(其实还是主席树)，每经过一个点i，进行一个赋值操作，将下标为$a_{i}$的位置赋值为i

那么我们在某一个点x的数组历史版本对应的就是x到1路径上某个颜色最后一次出现的点的编号

那么我们查询(lca,y)路径上是否出现了某种颜色x其实就是查询y这个历史版本的数组的第x项的深度是否大于等于lca的深度，如果大于等于的话证明颜色x最后一次出现的位置在链上，因此x就在路径里出现了

这样的话我们可以$O(log^2n)$的解决操作1

操作2

我们先处理直路径的部分，因为这一部分可以直接套用序列问题的代码，只是需要把序列的普通主席树改成树上主席树，可能需要注意的一点是，主席树中的下标应该是深度

所以我们先计算这3部分操作2的答案

1.x在(1,lca),y在(1,B)

2.y在(1,lca),x在(1,A)

3.然后发现 (1,lca) ,(1,lca)的路径被重复计数了，因此减去这一部分的答案

上述3部分全部可以直接套用序列问题的代码，不再赘述

好了下面我们要考虑 x在(lca,A],y在(lca,B]的部分了

我们还是继续统计贡献

首先先特判掉lca的贡献，因为我们的x和y都不能取到lca但是lca一定出现在这部分路径上

显然lca一定会被数到所以lca的贡献是$(dep_{A}-dep_{lca})(dep_{B}-dep_{lca})$

然后我们考虑你在操作1的时候是如何处理这种弯的路径的

显然是先查了一个长链然后向长链里暴力插点对吧

所以两种点的贡献方式完全不同，分情况考虑一下贡献

case 1:长链中点的贡献

那么我们在长链上跑的是普通的区间数颜色

无论如何y的个数都是$(dep_{B}-dep_{lca})$个

无论如何x的个数都是$(dep{A}-dep_{i}+1)$个

只需要考虑这个点到底是不是链上的第一个颜色点就行了

所以加上一个限制$dep_{pre_{i}}<dep_{lca}$

然后把序列上的主席树搬过来之后就可以利用主席树查贡献展开式的各种项相加就好了

case2:短链中点的贡献

应该是最难的部分了

我们发现操作1中我们直接对短链进行暴力了，因此我们从这个暴力什么时候会让答案+1的角度考虑短链中点的贡献

首先如果这个点i的pre的深度大于等于lca的深度是不会产生贡献的，因为无论怎么取他都不是第一个点

之后我们考虑查这个点的颜色是否在(lca,A)中出现过，如果没有出现的话y可能的取值共有$(dep_{B}-dep_{i}+1)$种，而此时x是可以随便取的因此可能的取值共有$(dep_{A}-dep_{lca})$种，所以贡献就是二者相乘了

接下来如果出现过的话我们是需要找一个这样的点，从lca出发向A的方向往下走，第一个出现的和i同色的点pr，如果x在pr和lca之间的话我们就还是可以暴力插点成功的

问题来了怎么求这个玩意？

我们的可持久化数组只能告诉我们每种颜色最后一次出现的点是什么，但是我们先是要求某种颜色第一次出现的位置

还记得吗？每种颜色的个数是期望$O(1)$的

所以我们求出这个颜色最后一次出现的位置之后直接顺着他的pre开始跳，直到我们要跳出了lca位置，这样我们就找到了这个颜色第一次出现的位置，期望进行O(1)次跳跃

那么此时点y可能的取值还是有$dep_{B}-dep_{i}+1$中，而x可能出现的取值有$(dep_{pr}-dep_{lca}-1)$种，点i的贡献就是是二者相乘了

分析下复杂度会发现复杂度是期望$O(log^2n)$的

这样我们成功解决了操作2就可以写这道题了

---

当然不用我多说也知道这道题有多难写了吧……(然而跑的飞起，所有点都在2s内跑完了)

如果胡写乱写基本调试不出来，请注意代码风格

当然这里的代码基本就不能看了，仅供参考

上代码~

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;const int N=1e5+10;const int E=20*N;typedef long long ll;typedef unsigned int uit;
int n;int m;int p;int v[2*N];int x[2*N];int ct;int al[N];int pre[N];int dep[N];int a[N];bool book[N];
stack <int> s[N];int fa[N];int T;
struct data//主席树强行维护信息
{
    int v0;ll v1;ll v2;ll v3;data(int a=0,ll b=0,ll c=0,ll d=0){v0=a;v1=b;v2=c;v3=d;}
    friend data operator +(data a,data b){return data(a.v0+b.v0,a.v1+b.v1,a.v2+b.v2,a.v3+b.v3);}
    friend data operator -(data a,data b){return data(a.v0-b.v0,a.v1-b.v1,a.v2-b.v2,a.v3-b.v3);}
};
struct answ//树上前缀和
{
    ll v1;ll v2;answ(ll a=0,ll b=0){v1=a;v2=b;}
    friend answ operator +(answ a,answ b){return answ(a.v1+b.v1,a.v2+b.v2);}
    friend answ operator -(answ a,answ b){return answ(a.v1-b.v1,a.v2-b.v2);}
}val[N];
struct per_linetree//主席树的板子
{
    data v[E];int s[E][2];int root[N];int ct;
    inline void modify(int p1,int p2,int l,int r,const int& pos,const data& pl)
    {
        v[p2]=v[p1]+pl;if(r-l==1){s[p2][0]=0;s[p2][1]=0;return;}int mid=(l+r)/2;
        if(pos<=mid){s[p2][1]=s[p1][1];modify(s[p1][0],s[p2][0]=++ct,l,mid,pos,pl);}
        else {s[p2][0]=s[p1][0];modify(s[p1][1],s[p2][1]=++ct,mid,r,pos,pl);}
    }
    inline data query(int p,int l,int r,int dl,int dr)
    {
        if(p==0||dl==l&&dr==r){return v[p];}int mid=(l+r)/2;data ret;
        if(dl<mid)ret=ret+query(s[p][0],l,mid,dl,min(dr,mid));
        if(mid<dr)ret=ret+query(s[p][1],mid,r,max(dl,mid),dr);return ret;
    }
    inline void cmodify(int p1,int p2,int pos,const data& pl)
    {modify(root[p1],root[p2]=++ct,0,n+1,pos+1,pl);}
    inline data cquery(int p1,int p2,int l,int r)
    {return query(root[p2],0,n+1,l+1,r+1)-query(root[p1],0,n+1,l+1,r+1);}
    inline void clear(){ct=1;}
}plt;
struct per_array//可持久化数组，还是主席树的板子
{
    int v[E];int s[E][2];int root[N];int ct;
    inline void modify(int p1,int p2,int l,int r,const int& pos,const int & pl)
    {
        v[p2]=pl;if(r-l==1){s[p2][0]=0;s[p2][1]=0;return;}int mid=(l+r)/2;
        if(pos<=mid){s[p2][1]=s[p1][1];modify(s[p1][0],s[p2][0]=++ct,l,mid,pos,pl);}
        else {s[p2][0]=s[p1][0];modify(s[p1][1],s[p2][1]=++ct,mid,r,pos,pl);}
    }
    inline int query(int p,int l,int r,int pos)
    {
        if(p==0||r-l==1){return v[p];}int mid=(l+r)/2;
        if(pos<=mid){return query(s[p][0],l,mid,pos);}
        else {return query(s[p][1],mid,r,pos);}
    }
    inline void cmodify(int p1,int p2,const int& pos,const int& pl)
    {modify(root[p1],root[p2]=++ct,0,n+1,pos+1,pl);}
    inline int cquery(int p,int pos){return query(root[p],0,n+1,pos+1);}
    inline void clear(){ct=1;}
}pa;
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline void dfs(int u,int f)//dfs建树形主席树，顺手处理出pre和树上前缀和
{
    pre[u]=s[a[u]].empty()?0:s[a[u]].top();s[a[u]].push(u);int dp=dep[pre[u]];
    plt.cmodify(f,u,dp,data(1,dep[u],dp,(ll)dp*dep[u]));
    pa.cmodify(f,u,a[u],u);fa[u]=f;
    val[u]=val[f]+answ(dep[u]-dp,(ll)(dep[u]-dp)*(-2*dep[u]+2)-1);
    for(int i=al[u];i;i=x[i]){dep[v[i]]=dep[u]+1;dfs(v[i],u);}
    s[a[u]].pop();
}
inline int query1(int u,int v)
{
    if(dep[u]>dep[v])swap(u,v);int lc=u;int lc1=v;//暴力找lca
    for(;lc1>p;lc1=fa[lc1])book[lc1]=true;
    for(;lc>p;lc=fa[lc])if(book[lc])goto ed1;
    lc=(dep[lc]<dep[lc1])?lc:lc1;ed1:;
    for(int x=v;x>p;x=fa[x])book[x]=false;
    int ans=plt.cquery(fa[lc],v,-1,dep[lc]-1).v0;//提取长链信息
    for(int x=u;x!=lc;x=fa[x])
        if(dep[pre[x]]<dep[lc]&&dep[pa.cquery(v,a[x])]<dep[lc])ans++;//暴力插入短链
    return ans;
}
inline ll subquery(int l,int r)//操作2的序列问题
{
    ll L=dep[l];ll R=dep[r];data ret=(l!=r)?plt.cquery(l,r,-1,dep[l]):data();//无脑考虑贡献即可
    return val[l].v1*(L+R)+val[l].v2+ret.v0*L*(R+1)-L*ret.v1-(R+1)*ret.v2+ret.v3;
}
inline ll query2(int u,int v)//操作2
{
    if(dep[u]>dep[v])swap(u,v);int lc=u;int lc1=v;//还是暴力找lca
    for(;lc1>p;lc1=fa[lc1])book[lc1]=true;
    for(;lc>p;lc=fa[lc])if(book[lc])goto ed1;
    lc=(dep[lc]<dep[lc1])?lc:lc1;ed1:;
    for(int x=v;x>p;x=fa[x])book[x]=false;
    ll ret=subquery(lc,v)+subquery(lc,u)-subquery(lc,lc);//处理直路径
    if(lc==u)return ret;data tr=plt.cquery(lc,v,-1,dep[lc]-1);//弯路径的长链贡献,主席树查一发即可
    ret+=(dep[u]-dep[lc])*((ll)tr.v0*(dep[v]+1)-tr.v1)+(ll)(dep[v]-dep[lc])*(dep[u]-dep[lc]);//记得加上lca
    for(int x=u;x!=lc;x=fa[x])
    {
        if(dep[pre[x]]>=dep[lc]){continue;}//如果数不到这个点就跳过
        int pr=pa.cquery(v,a[x]);
        if(dep[pr]<dep[lc]){ret+=(ll)(dep[v]-dep[lc])*(dep[u]-dep[x]+1);continue;}//如果一定可以插入成功就直接算贡献
        for(;dep[pre[pr]]>=dep[lc];pr=pre[pr]);if(dep[pr]==dep[lc])continue;//跳pre找第一次出现的点
        ret+=(ll)(dep[pr]-dep[lc]-1)*(dep[u]-dep[x]+1);//计算贡献
    }return ret;
}
namespace Maker//生成器代码,直接粘就行了
{
    uit SA,SB,SC;
    uit rng61(){SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;uit t=SA;SA=SB;SB=SC;SC^=t^SA;return SC;}
    void gen()
    {
    	scanf("%d%d%u%u%u",&n,&p,&SA,&SB,&SC);
    	for(int i=2;i<=p;i++)add(i-1,i);
    	for(int i=p+1;i<=n;i++)add(rng61()%(i-1)+1,i);
    	for(int i=1;i<=n;i++)a[i]=rng61()%n+1;
    }
}
inline void solve()
{
    Maker::gen();scanf("%d",&m);dep[1]=1;dfs(1,0);
    for(int i=1,t,l,r;i<=m;i++)
    {scanf("%d%d%d",&t,&l,&r);printf("%lld\n",(t==1)?query1(l,r):query2(l,r));}
}
inline void clear(){plt.clear();pa.clear();for(int i=1;i<=n;i++)al[i]=0;ct=0;}
int main(){scanf("%d",&T);for(int z=1;z<=T;z++){solve();clear();}return 0;}//拜拜程序~