题解 P4618 【[SDOI2018]原题识别】

shadowice1984 · 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的贡献就是

然后我们考虑你在操作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;}//拜拜程序~