[線段樹系列] LCT打延遲標記的正確姿勢

這一篇博客將教你什么?

如何用LCT打延遲標記,LCT和線段樹延遲標記間的關系,為什么延遲標記要這樣打。

——正片開始——

學習這一篇博客前,確保你會以下知識:

Link-Cut-Tree,普通線段樹

當然,不會也沒有關系,你可以先收藏這篇博客,等你學了以后再來看。

 

最好通過了這一道題:【模板】線段樹Ⅱ

沒有通過也沒關系,對于本篇的知識只是一個啟發作用。

我們平時使用的Link-Cut-Tree一般只需要打一個翻轉標記rev[x]。

然后我們用pushR(x)函數來下發翻轉標記。

那么我們現在來看這樣一道題:TreeⅡ

練習LCT打標記的絕世好題,可以說就是一道模板題了。

我們來看它需要維護什么:樹的權值。

如果能把這個操作2去掉,樹剖將絕殺,可惜換不得。

單走一個“樹”,nice,直接LCT。

詢問權值和,可以,給LCT來一個下傳標記,開始你的操作秀。

我們直接來看pushdown部分:

操作有乘和加兩種,根據運算法則,乘法優先,所以首先判斷

if(lazM[x]!=1){...}

然后是加法

if(lazA[x]){...}

最后回到我們的翻轉標記。

然后我們來看pushM和pushA部分

#define mul(x,y) x*=y;x%=MOD;
inline void pushM(unsigned int x,unsigned int d){
    mul(sum[x],d);mul(val[x],d);//節點信息直接更新
    mul(lazM[x],d);mul(lazA[x],d);//按照運算法則先把乘標記乘了,再把加標記乘了
}

有沒有回想起什么?沒錯,就是線段樹的懶標記。

我們看看線段樹2的懶標記下傳部分

void pushdown(int p){
        mul(p<<1)=(mul(p<<1)*mul(p))%P;
        mul(p<<1|1)=(mul(p<<1|1)*mul(p))%P;
        add(p<<1)=(add(p<<1)*mul(p))%P;
        add(p<<1|1)=(add(p<<1|1)*mul(p))%P;
        sum(p<<1)=(sum(p<<1)*mul(p))%P;
        sum(p<<1|1)=(sum(p<<1|1)*mul(p))%P;//按照運算法則更新標記和節點信息
        mul(p)=1;
        add(p<<1)=(add(p<<1)+add(p))%P;
        add(p<<1|1)=(add(p<<1|1)+add(p))%P;
        sum(p<<1)=(sum(p<<1)+add(p)*(r(p<<1)-l(p<<1)+1))%P;
        sum(p<<1|1)=(sum(p<<1|1)+add(p)*(r(p<<1|1)-l(p<<1|1)+1))%P;//按照運算法則更新標記和節點信息
        add(p)=0;
}

驚人的一致。

猜到pushA的寫法了吧?那我不講了,后面有代碼。

透過現象看本質。

兩種數據結構都是在維護一個區間,只不過LCT維護的樹上一段路徑的區間。

如果這道題把操作2去掉,我們用樹鏈剖分寫,線段樹維護,一樣是這樣打標記。

為什么?

如果你當初學線段樹的時候理解了線段樹2打標記里面先成后加的原理,你可能思考一下就明白了。

這里的原因和線段樹非常相似:精度。

我們的標記是打在父節點上的,告訴它它的孩子加了多少,乘了多少。

如果我們先加了那么多,再乘那么多,結果是不一樣的,如果非要等價,需要對式子變形。

我們看這樣一個式子:(a+b)*c,它并不等價于a*c+b,運算的順序是會影響結果的。

然而我們打標記的時候并不能確定順序。這時我們為何不用上很早就明白的運算法則呢?

看下面兩種順序:

先+后*:(a+b)*c = a*c+b*c,先*后+:(a+b)*c = a*c+b

我們發現,先+后*的式子并不等于先*后+的式子,要讓它相等必須在加的那一項也*上c。

但是要讓先*后+的式子轉化成先+后*的式子,我們就必須用到除法,就會變成實數運算,還有可能得到無限小數影響精度。所以我們只需要使用先*后+的優先順序,并且在打乘法標記時把加法標記也乘上這個值就可以了。

分析完后,相信各位應該能理解數據結構“懶標記”的概念以及為何選擇這種優先順序了。

那么剩下的就是很正常的LCT操作了,給出此題的代碼。

注意這道題有一個坑點:模數是51061,看上去很小,然而暗藏出題人的心機。

我們來看51061的平方 ——> 2516125921,再看int的數據范圍 —— > 2147483647

于是我們需要開long long,但是我寫的時候為了卡常用了unsigned int。

#include<bits/stdc++.h>
using namespace std;
int n,q;
const int N=1000010;
#define MOD 51061
unsigned int fa[N],val[N],ch[N][2],rev[N],lazM[N],lazA[N],siz[N],sum[N],stk[N];
#define add(x,y) x+=y;x%=MOD;
#define mul(x,y) x*=y;x%=MOD;
inline unsigned int read(){
    unsigned int data=0,w=1;char ch=0;
    while(ch!='-' && (ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0' && ch<='9')data=data*10+ch-'0',ch=getchar();
    return data*w;
}
inline bool chk(unsigned int x){
    return ch[fa[x]][1]==x;
}
inline bool nroot(unsigned int x){
    return ch[fa[x]][0]==x||ch[fa[x]][1]==x;
}
inline void pushup(unsigned int x){
    sum[x]=(sum[ch[x][0]]+sum[ch[x][1]]+val[x])%MOD;
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
template<class T>inline void fswap(T&x,T&y){
    T t=x;x=y;y=t;
}
inline void pushR(unsigned int x){
    fswap(ch[x][0],ch[x][1]);
    rev[x]^=1;
}
inline void pushM(unsigned int x,unsigned int d){
    mul(sum[x],d);mul(val[x],d);
    mul(lazM[x],d);mul(lazA[x],d);
}
inline void pushA(unsigned int x,unsigned int d){
    add(sum[x],d*siz[x]);add(val[x],d);
    add(lazA[x],d);
}
inline void pushdown(unsigned int x){
    if(lazM[x]!=1){
        pushM(ch[x][0],lazM[x]);
        pushM(ch[x][1],lazM[x]);
        lazM[x]=1;
    }
    if(lazA[x]){
        pushA(ch[x][0],lazA[x]);
        pushA(ch[x][1],lazA[x]);
        lazA[x]=0;
    }
    if(rev[x]){
        if(ch[x][0])pushR(ch[x][0]);
        if(ch[x][1])pushR(ch[x][1]);
        rev[x]=0;
    }
}
inline void rotate(unsigned int x){
    int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
    ch[y][k]=w;if(w)fa[w]=y;
    if(nroot(y))ch[z][chk(y)]=x;fa[x]=z;
    ch[x][k^1]=y;fa[y]=x;
    pushup(y);pushup(x);
}
inline void splay(unsigned int x){
    int y=x,z=0;
    stk[++z]=y;
    while(nroot(y))stk[++z]=y=fa[y];
    while(z)pushdown(stk[z--]);
    while(nroot(x)){
        y=fa[x];z=fa[y];
        if(nroot(y)){
            if(chk(x)==chk(y))rotate(y);
            else rotate(x);
        }rotate(x);
    }
    pushup(x);
}
inline void access(unsigned int x){
    for(int y=0;x;x=fa[y=x])
        splay(x),ch[x][1]=y,pushup(x);
}
inline void makeroot(unsigned int x){
    access(x);splay(x);
    pushR(x);
}
inline int findroot(unsigned int x){
    access(x);splay(x);
    while(ch[x][0])pushdown(x),x=ch[x][0];
    splay(x);
    return x;
}
inline void split(unsigned int x,unsigned int y){
    makeroot(x);
    access(y);splay(y);
}
inline void link(unsigned int x,unsigned int y){
    makeroot(x);
    if(findroot(y)!=x)fa[x]=y;
}
inline void cut(unsigned int x,unsigned int y){
    makeroot(x);
    if(findroot(y)==x && fa[y]==x && !ch[y][0]){
        fa[y]=ch[x][1]=0;
        pushup(x);
    }
}
int main(){
    n=read();q=read();
    for(int i=1;i<=n;i++)val[i]=siz[i]=lazM[i]=1;
    for(int i=1;i<n;i++){
        int a=read();int b=read();
        link(a,b);
    }
    char opt[10];
    int u,v,d;
    while(q--){
        scanf("%s",opt);
        if(opt[0]=='+'){
            u=read();v=read();d=read();
            split(u,v);pushA(v,d);
        }else if(opt[0]=='-'){
            u=read();v=read();
            cut(u,v);
            u=read();v=read();
            link(u,v);
        }else if(opt[0]=='*'){
            u=read();v=read();d=read();
            split(u,v);pushM(v,d);
        }else{
            u=read();v=read();
            split(u,v);
            printf("%d\n",sum[v]);
        }
    }
    return 0;
}

其實這也揭示了數據結構間的聯系:形式不同,作用相似。

透過現象看本質,通過結果推原因,都是學習數據結構的重要方式。

數據結構不只是背背代碼,用來加速這么簡單的,如果明白了數據結構的運行方式和原理,

你也一定會感慨里面蘊含著的發明者的智慧和它給你帶來的知識上的進步。

我是燈塔...一個喜歡數據結構的OIer博主,關注我,我將給你帶來更多精彩的文章。

posted @ 2019-10-31 17:31  LightHouseOfficial  閱讀(...)  評論(...編輯  收藏
11选5走势图