洛谷 P1501 [国家集训队]Tree II 题解【LCT】【splay】

作者: wjyyy 分类: LCT,splay,解题报告 发布时间: 2019-01-17 18:53

点击量:25

第一次写路径加/乘的lct,多存了两个lazytag。

题目描述

一棵\(n\)个点的树,每个点的初始权值为\(1\)。对于这棵树有\(q\)个操作,每个操作为以下四种操作之一:

  • + u v c:将\(u\)到\(v\)的路径上的点的权值都加上自然数\(c\);
  • - u1 v1 u2 v2:将树中原有的边\((u1,v1)\)删除,加入一条新边\((u2,v2)\),保证操作完之后仍然是一棵树;
  • * u v c:将\(u\)到\(v\)的路径上的点的权值都乘上自然数\(c\);
  • / u v:询问\(u\)到\(v\)的路径上的点的权值和,求出答案对于\(51061\)的余数。

输入输出格式

输入格式:

第一行两个整数\(n,q\)

接下来\(n-1\)行每行两个正整数\(u,v\),描述这棵树

接下来\(q\)行,每行描述一个操作

输出格式:

对于每个/对应的答案输出一行

输入输出样例

输入样例#1:

3 2
1 2
2 3
* 1 3 4
/ 1 1

输出样例#1:

4

说明

\(10\%\)的数据保证,\(1\le n,q\le 2000\)

另外\(15\%\)的数据保证,\(1\le n,q\le 5\times 10^4\),没有-操作,并且初始树为一条链

另外\(35\%\)的数据保证,\(1\le n,q\le 5\times 10^4\),没有-操作

\(100\%\)的数据保证,\(1\le n,q\le 10^5\),\(0\le c\le 10^4\)

题解:

经典的lct操作。主要是维护路径加路径乘比较麻烦。

这个题目由于存在-操作,所以必须使用lct来完成。但是一个比较麻烦的事情是“对路径上所有点的点权乘上自然数\(c\)”,这时我们想起了洛谷的板子洛谷 P3373 【模板】线段树 2。在这个题中我们用两个lazytag维护了线段树(区间)上的加乘混合运算,可以把相似的思想套用到这道题上。

由于这道题在splay上完成,同时splay还有翻转操作,这时就需要存3个lazytag。此时要注意pushdown的操作顺序:区间翻转可以放在任何一个位置,但是乘标记和加标记必须先乘再加,打标记的原理可以看另一篇区间乘线段树的题解重点在于乘的时候也要对加标记做乘法

其余的操作就和lct一样了。

btw:不开long long当场去世

lct的题码量真的不大。

Code:

#include<cstdio>
#include<cstring>
#define ls ch[0][k]
#define rs ch[1][k]
#define which(k) (ch[1][fa[k]]==k)
#define isroot(k) (ch[0][fa[k]]!=k&&ch[1][fa[k]]!=k)
#define p 51061
#define ll long long
int ch[2][100100],fa[100100];
ll lazy[100100],lazy1[100100],lazy2[100100],key[100100],sum[100100],sz[100100];
void pushdown(int k)
{
    if(lazy[k])
    {
        int tmp=ls;
        ls=rs;
        rs=tmp;
        lazy[ls]^=1;
        lazy[rs]^=1;
        lazy[k]=0;
    }
    if(lazy2[k]!=1)
    {
        ll x=lazy2[k];
        lazy2[k]=1;
        //修改左右儿子(自己已被修改)
        key[ls]=key[ls]*x%p;
        sum[ls]=sum[ls]*x%p;
        lazy1[ls]=lazy1[ls]*x%p;
        lazy2[ls]=lazy2[ls]*x%p;
        key[rs]=key[rs]*x%p;
        sum[rs]=sum[rs]*x%p;
        lazy1[rs]=lazy1[rs]*x%p;
        lazy2[rs]=lazy2[rs]*x%p;
    }
    if(lazy1[k])
    {
        ll x=lazy1[k];
        lazy1[k]=0;

        key[ls]=(key[ls]+x)%p;
        sum[ls]=(sum[ls]+sz[ls]*x%p)%p;
        lazy1[ls]=(lazy1[ls]+x)%p;
        key[rs]=(key[rs]+x)%p;
        sum[rs]=(sum[rs]+sz[rs]*x%p)%p;
        lazy1[rs]=(lazy1[rs]+x)%p;
    }
}
void maintain(int k)
{
    pushdown(k);
    sum[k]=(sum[ls]+key[k]+sum[rs])%p;
    sz[k]=(sz[ls]+1+sz[rs])%p;
}
void Rotate(int k)
{
    int y=fa[k];
    if(!isroot(y))
        ch[which(y)][fa[y]]=k;
    bool d=which(k);
    fa[k]=fa[y];
    fa[y]=k;
    ch[d][y]=ch[!d][k];
    ch[!d][k]=y;
    fa[ch[d][y]]=y;
    maintain(y);
    maintain(k);
}
int stk[100100],tp=0;
void splay(int k)
{
    while(!isroot(k))
    {
        stk[++tp]=k;
        k=fa[k];
    }
    stk[++tp]=k;
    while(tp)
        pushdown(stk[tp--]);
    k=stk[1];

    while(!isroot(k))
    {
        int y=fa[k];
        if(!isroot(y))
            Rotate(which(k)^which(y)?k:y);
        Rotate(k);
    }
}
void access(int k)
{
    for(int x=k,y=0;x;y=x,x=fa[x])
    {
        splay(x);
        ch[1][x]=y;
        maintain(x);
    }
}
void makeroot(int k)
{
    access(k);
    splay(k);
    lazy[k]^=1;
}
void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}
void link(int x,int y)
{
    makeroot(x);
    fa[x]=y;
}
void cut(int x,int y)
{
    split(x,y);
    fa[x]=ch[0][y]=0;
}
char op[100];
int main()
{
    int n,m,u,v,w,x;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        key[i]=1,sum[i]=1,lazy2[i]=1,sz[i]=1;
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&u,&v);
        link(u,v);
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%s",op);
        if(op[0]=='+')
        {
            scanf("%d%d%d",&u,&v,&w);
            split(u,v);
            key[v]=(key[v]+w)%p;
            lazy1[v]=(lazy1[v]+w)%p;
            pushdown(v);
            maintain(v);
        }
        else if(op[0]=='-')
        {
            scanf("%d%d%d%d",&u,&v,&w,&x);
            cut(u,v);
            link(w,x);
        }
        else if(op[0]=='*')
        {
            scanf("%d%d%d",&u,&v,&w);
            split(u,v);
            key[v]=key[v]*w%p;
            lazy1[v]=lazy1[v]*w%p;
            lazy2[v]=lazy2[v]*w%p;
            pushdown(v);
            maintain(v);
        }
        else
        {
            scanf("%d%d",&u,&v);
            split(u,v);
            printf("%lld\n",sum[v]);
        }
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */