zcmimi's blog
查看原题

点击跳转

链上的情况

情况一

记录每个点i前一个与它一样的位置pre_i,

那么区间[l,r]内不同的个数也就是[l,r]pre_i<l的个数

主席树统计即可

情况二

考虑每个点对答案的贡献,分类讨论

  1. i\in [1,A]

    那么满足的y\in (pre_i,i],x\in [i,A]

    x\in (pre_i,i],y\in [i,B]

    总贡献为\sum (i-pre_i)\times(A+B-2i+2)-1

    (-1为了避免[i,i]被重复计算)

    拆下式子: (A+B+2)(\sum i-pre_i)-2(\sum i(i-pre_i))-\sum 1

    可以发现这种情况可以直接前缀和维护

  2. i\in (A,B],满足pre_i<A

    那么满足的x\in (pre_i,A],y\in [i,B]

    总贡献为\sum (A-pre_i)\times(B-i+1)

    拆下式子(A\sum 1-\sum pre_i)(B+1)-A\sum i+\sum ipre_i

    可以发现这种情况可以用主席树维护

树上情况

观察数据形成方式:

  • p个点形成一条主链,其他点随机向主链连边
    所以树上任意点对的\texttt{lca}距离他们期望为\mathcal O(\log n)
  • 每个点的颜色在[1,n]中随机,每种颜色数目期望为1

pre_ii的祖先中颜色与i相同的深度最大的点

第一问

xyx\texttt{lca}(x,y)更近

首先求出y\texttt{lca}链上的颜色总数,

然后再暴力枚举x\texttt{lca}链上的颜色更新答案

第二问

ABA\texttt{lca}(A,B)更近

分类讨论:

  1. x\in [1,\texttt{lca}],y\in [1,B],与链上的情况相同
  2. x\in [\texttt{lca},A],y\in [1,\texttt{lca}]

    x\in [1,A],y\in [1,\texttt{lca}]的答案减去

    x,y\in [1,\texttt{lca})的答案\sum (2(i-pre_i)(\texttt{lca}-i)-1)

    拆下式子: 2\texttt{lca}\sum (i-pre_i) - 2\sum i(i-pre_i)-\sum 1

  3. x\in [\texttt{lca},A],y\in [\texttt{lca},B]

    先求出i\in [\texttt{lca,B}]的贡献\sum (B-i+1)(A-\texttt{lca}+1)

    拆下式子: (A-\texttt{lca}+1)(\sum B+1 - \sum i)

    然后用i\in (\texttt{lca},A]更新

    pre_i\le\texttt{lca},设j[\texttt{lca},B]中第一个与它颜色相同的点

    贡献: (A-i+1)(j-\texttt{lca})

#include<bits/stdc++.h>
using std::list;
typedef long long ll;
const int N=100011;
int n,a[N];list<int>vec[N],e[N];
int RT[N];
struct node{
    ll v,pd,d,pdxd;// Σ1,Σdep[pre],Σdep[i],Σdep[pre]×dep[i]
    node operator+(const node&t){return node{v+t.v,pd+t.pd,d+t.d,pdxd+t.pdxd};}
    node operator-(const node&t){return node{v-t.v,pd-t.pd,d-t.d,pdxd-t.pdxd};}
};
struct prt{

int sz,ls[N*20],rs[N*20];
node s[N*20];
void build(int&x,int l,int r){
    s[x=++sz]=node{0,0,0,0};
    if(l==r)return;
    int m=l+r>>1;
    build(ls[x],l,m);build(rs[x],m+1,r);
}
void ins(int&x,int pre,int p,int l,int r,node v){
    s[x=++sz]=s[pre]+v;
    if(l==r)return;
    ls[x]=ls[pre],rs[x]=rs[pre];
    int m=l+r>>1;
    if(p<=m)ins(ls[x],ls[pre],p,l,m,v);
    else ins(rs[x],rs[pre],p,m+1,r,v);
}
node ask(int x,int y,int R,int l,int r){
    if(r<=R)return s[y]-s[x];
    int m=l+r>>1;
    node ans=ask(ls[x],ls[y],R,l,m);
    return R>m?ans+ask(rs[x],rs[y],R,m+1,r):ans;
}

}T;
int L[N],R[N],dfn,st[20][N*2];
int f[N],d[N],pre[N],b[N];ll sum[N][2];
void dfs(int x){
    st[0][L[x]=++dfn]=x;
    pre[x]=b[a[x]],b[a[x]]=x;
    T.ins(RT[x],RT[f[x]],pre[x],0,n,node{
        1,d[pre[x]],d[x],1ll*d[pre[x]]*d[x]
    });
    sum[x][0]=d[x]-d[pre[x]]+sum[f[x]][0];
    sum[x][1]=1ll*(d[x]-d[pre[x]])*d[x]+sum[f[x]][1];

    for(int to:e[x])d[to]=d[x]+1,dfs(to),st[0][++dfn]=x;
    R[x]=dfn;
    b[a[x]]=pre[x];
}
int gmd(int x,int y){return d[x]<d[y]?x:y;}
void ST(){
    for(int k=1;(1<<k)<=dfn;++k)
        for(int i=1;i<=dfn-(1<<k)+1;++i)
            st[k][i]=gmd(st[k-1][i],st[k-1][i+(1<<k-1)]);
}
void swap(int&x,int&y){int t=x;x=y;y=t;}
int lca(int x,int y){
    int l=L[x],r=L[y];
    if(l>r)swap(l,r);
    int k=log2(r-l+1);
    return gmd(st[k][l],st[k][r-(1<<k)+1]);
}
int v[N],ti;
bool chk(int x,int y,int p){
    return L[x]<=L[p]&&L[p]<=R[x]&&L[p]<=L[y]&&L[y]<=R[p];
}
ll ask1(int x,int y){
    if(d[x]>d[y])swap(x,y);
    int F=lca(x,y);
    ll ans=T.ask(RT[f[F]],RT[y],d[F]-1,0,n).v;
    ++ti;
    for(int i=x;i!=F;i=f[i])if(v[a[i]]!=ti){
        v[a[i]]=ti;
        bool ff=1;
        for(int j:vec[a[i]])
            if(chk(F,y,j)){ff=0;break;}
        ans+=ff;
    }
    return ans;
}
ll calc(int A,int B,node t){// i∈[1,A],i∈(A,B]
    return (d[A]+d[B]+2)*sum[A][0]-2*sum[A][1]-d[A]+
        (d[A]*t.v-t.pd)*(d[B]+1)-d[A]*t.d+t.pdxd;
}
ll ask2(int A,int B){
    if(d[A]>d[B])swap(A,B);
    int F=lca(A,B);
    node FA=T.ask(RT[f[F]],RT[A],d[F]-1,0,n),
        FB=T.ask(RT[f[F]],RT[B],d[F]-1,0,n);
    ll ans=calc(f[F],B,FB) // x∈[1,lca],y∈[1,B]
        +calc(f[F],A,FA);  // x∈[1,A],y∈[1,lca]
    ans-=2*(d[F]*sum[f[F]][0]-sum[f[F]][1])-(d[F]-1);// - x,y∈[1,lca)
    ans+=(d[A]-d[F]+1)*((d[B]+1)*FB.v-FB.d);// i∈[lca,B]
    list<int>sta;
    for(int i=A;i!=F;i=f[i])sta.push_back(i);
    ++ti;
    while(!sta.empty()){// i∈(lca,A]
        int i=sta.back();sta.pop_back();
        if(v[a[i]]!=ti){
            v[a[i]]=ti;
            int mi=d[B]+1;
            for(int j:vec[a[i]])
                if(chk(F,B,j)&&d[j]<mi)mi=d[j];
            ans+=ll(d[A]-d[i]+1)*(mi-d[F]);
        }
    }
    return ans;
}
unsigned int SA,SB,SC;
unsigned int rng61(){SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;unsigned int t=SA;SA=SB;SB=SC;SC^=t^SA;return SC;}
void solve(){
    int q,p,x,y;
    scanf("%d%d%u%u%u%d",&n,&p,&SA,&SB,&SC,&q);
    for(int i=2;i<=n;++i)
        e[f[i]=i>p?rng61()%(i-1)+1:i-1].push_back(i);
    for(int i=1;i<=n;++i)vec[a[i]=rng61()%n+1].push_back(i);
    T.build(RT[0],0,n);
    d[1]=1,dfs(1);ST();
    while(q--)
        scanf("%d%d%d",&p,&x,&y),
        printf("%lld\n",p==1?ask1(x,y):ask2(x,y));
    dfn=T.sz=0;
    for(int i=1;i<=n;++i)
        vec[i].clear(),e[i].clear(),
        RT[i]=v[i]=b[i]=0;
}
int main(){
    int T;scanf("%d",&T);
    while(T--)solve();
}
LG 4618 [SDOI2018]原题识别
comment评论
Search
search