---

我用線段樹加懶標，結果沒過(複雜度的問題??)，而且今天zj好奇怪，前一個小時之前丟可以拿20%(通過兩個剩下TLE)，再丟一次相同的程式變8%(只過第一個)，還是其實這題不能用線段樹?

 

---

我用線段樹加懶標，結果沒過(複雜度的問題??)，而且今天zj好奇怪，前一個小時之前丟可以拿20%(通過兩個剩下TLE)，再丟一次相同的程式變8%(只過第一個)，還是其實這題不能用線段樹?

我用線段樹+懶人標記過的(剛剛丟了一次 AC 1.4s)

 

---

我用線段樹加懶標，結果沒過(複雜度的問題??)，而且今天zj好奇怪，前一個小時之前丟可以拿20%(通過兩個剩下TLE)，再丟一次相同的程式變8%(只過第一個)，還是其實這題不能用線段樹?

我用線段樹+懶人標記過的(剛剛丟了一次 AC 1.4s)

那想請教你大概是怎麼做到的（像是你懶人標記是記什麼東西），因為其實我是第一次實作懶人標記，所以其實還不太懂到底怎麼寫比較好

 

---

那想請教你大概是怎麼做到的（像是你懶人標記是記什麼東西），因為其實我是第一次實作懶人標記，所以其實還不太懂到底怎麼寫比較好

我們可以先思考一個問題 如果今天題目的區間修改變成:"針對該區間[a,b]的每個元素 數值增加k" lazyTage需要怎麼紀錄數值

很簡單 區間[a,b]的元素數量 * k

現在回來看題目 我們的目標 就是想辦法去記錄 剛才的"區間[a,b]的元素數量 * k" (又或者說怎麼去獲得這個值)

假設現在有一個長度為n 編號為(1~n)的區間 現在從中挑出一個區間[a,b] 來進行觀察

我們按照題目的修改方式 對於區間[a,b]進行一次修改 這時[a,b] 所增加的數值為 1+2+3...+b

也就是 (b+1)*b/2，公差d = 1

接著我們對 [a-1, b] 進行一次修改 我們可以觀察到 每個元素各自增加的值如下

a:(1+2)=3  a+1:(2+3)=5   a+2:(3+4)=7 ... b:(b+b+1)

總和變成 (2b+1 + 3)*b / 2，公差d = 2

2b+1 也可以寫成 3+(b-a)*d

也就是說 求出區間總和 我們需要: 1.公差 2.首相的值(a所需要增加的值)  3.區間元素的數量

而公差就是修改的次數 

我們需要去紀錄的值有兩樣:公差 首相，所以我們需要2個lazyTage (我把這兩個用class綁在一起)

public static class LazyTage{

    int count = 0;//修改次數

    long num = 0;//增加的值

    public Lazy(){

    }

    public void add(long n, int c){

        count += c;

        num += n;

    }

    public void add(long n){

        count++;

        num += n;

    }

    public void clear(){

        num = count = 0;

    }

}

把lazyTage下推的過程如下:

public static void pushDown(int ind, int leftNodeNum, int rightNodeNum){ //index, 左節點數量, 右節點數量

    if(lazy[ind].num > 0){ //如果有需要修改

        tree[ind << 1] += diff(lazy[ind].num, leftNodeNum, lazy[ind].count); //解等差級數和

        tree[(ind << 1) + 1] += diff(lastNum(lazy[ind].num, leftNodeNum+1, lazy[ind].count), rightNodeNum, lazy[ind].count); 

        //lastNum 是拿來計算末項的 左區間的末項+d = 右區間的首相

        

        lazy[ind << 1].add(lazy[ind].num, lazy[ind].count);

        lazy[(ind << 1) + 1].add(lastNum(lazy[ind].num, leftNodeNum+1, lazy[ind].count), lazy[ind].count);

        

        lazy[ind].clear();

    }

}

public static long diff(long a, long b, long diff){ //首相的值, 節點數量, 公差

    long last = lastNum(a, b, diff);

    return ((a+last)*b) >> 1;

}

public static long lastNum(long s, long n, long diff){ 

    return s + (n-1)*dif;

} 

在update時 [a,b]被包含在需要被修改之區間中的時候:

if(l >= changeLeft && r <= changeRight){

    int a = l-changeLeft+1;

    tree[ind] += diff(a, r-l+1, 1);

    lazy[ind].add(a);

    return;

}

剩下的 基本上就和普通的區間修改差不多

 

以上 希望有幫到你

 

---

 

我們可以先思考一個問題 如果今天題目的區間修改變成:"針對該區間[a,b]的每個元素 數值增加k" lazyTage需要怎麼紀錄數值

很簡單 區間[a,b]的元素數量 * k

現在回來看題目 我們的目標 就是想辦法去記錄 剛才的"區間[a,b]的元素數量 * k" (又或者說怎麼去獲得這個值)

假設現在有一個長度為n 編號為(1~n)的區間 現在從中挑出一個區間[a,b] 來進行觀察

我們按照題目的修改方式 對於區間[a,b]進行一次修改 這時[a,b] 所增加的數值為 1+2+3...+b

也就是 (b+1)*b/2，公差d = 1

接著我們對 [a-1, b] 進行一次修改 我們可以觀察到 每個元素各自增加的值如下

a:(1+2)=3  a+1:(2+3)=5   a+2:(3+4)=7 ... b:(b+b+1)

總和變成 (2b+1 + 3)*b / 2，公差d = 2

2b+1 也可以寫成 3+(b-a)*d

也就是說 求出區間總和 我們需要: 1.公差 2.首相的值(a所需要增加的值)  3.區間元素的數量

而公差就是修改的次數 

我們需要去紀錄的值有兩樣:公差 首相，所以我們需要2個lazyTage (我把這兩個用class綁在一起)

public static class LazyTage{

    int count = 0;//修改次數

    long num = 0;//增加的值

    public Lazy(){

    }

    public void add(long n, int c){

        count += c;

        num += n;

    }

    public void add(long n){

        count++;

        num += n;

    }

    public void clear(){

        num = count = 0;

    }

}

把lazyTage下推的過程如下:

public static void pushDown(int ind, int leftNodeNum, int rightNodeNum){ //index, 左節點數量, 右節點數量

    if(lazy[ind].num > 0){ //如果有需要修改

        tree[ind << 1] += diff(lazy[ind].num, leftNodeNum, lazy[ind].count); //解等差級數和

        tree[(ind << 1) + 1] += diff(lastNum(lazy[ind].num, leftNodeNum+1, lazy[ind].count), rightNodeNum, lazy[ind].count); 

        //lastNum 是拿來計算末項的 左區間的末項+d = 右區間的首相

        

        lazy[ind << 1].add(lazy[ind].num, lazy[ind].count);

        lazy[(ind << 1) + 1].add(lastNum(lazy[ind].num, leftNodeNum+1, lazy[ind].count), lazy[ind].count);

        

        lazy[ind].clear();

    }

}

public static long diff(long a, long b, long diff){ //首相的值, 節點數量, 公差

    long last = lastNum(a, b, diff);

    return ((a+last)*b) >> 1;

}

public static long lastNum(long s, long n, long diff){ 

    return s + (n-1)*dif;

} 

在update時 [a,b]被包含在需要被修改之區間中的時候:

if(l >= changeLeft && r <= changeRight){

    int a = l-changeLeft+1;

    tree[ind] += diff(a, r-l+1, 1);

    lazy[ind].add(a);

    return;

}

剩下的 基本上就和普通的區間修改差不多

 

以上 希望有幫到你

太感謝了!!感謝你花那麼多時間和心思回應問題，寫的很精采，現在終於過了!

對於怎麼求等差級數和，我當時還煩惱了很久到底怎麼懶標記加起來，原來是利用d(公差)跟a(首項)紀錄，之後走訪的時候再利用等差級數和的公式計算!!