/ Vijos / 题库 / 原题识别 /

题解

3 条题解

  • 1
    @ 2023-07-12 17:37:57 
    #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();
}
  • 1
    @ 2021-07-18 21:41:03 
    #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();
}
  • -1
    @ 2020-04-30 18:03:27 
    #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;}
  • 1

原题识别

信息

ID
2048
难度
8
分类
(无)
标签
递交数
42
已通过
13
通过率
31%
被复制
2
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1