Codeforces Round #301 (Div. 2)

經過GCJ的失敗後, 慢慢調整腳步回復正常

前幾天在公司看到了這場只有Div. 2 的Round

就跑去打了

話說原本的計劃是半休閒地打的

但這場的性質, 我認為是較陷阱型, 就是那些讓你不斷HACK人和被HACK的題目

本身題目能學習到的也不少, 但沒有前幾場那麼多

可能這場要真正參加才行吧...

我其實也是Virtual Participate的

但無奈在題B 的Implementation上卡了很久, 也被人發現我在做冗員就開始給我工作了

結果還是完了Virtual Participation之後當練習地慢慢打

題目方面除了是陷阱型, 題C我認為是題目1999...我理解完全錯誤 導至一直想不通

也不明白為何會這麼多人AC...下面再詳說吧~ 重點是題C-E (Div,1 的頹題) 學習到的東東

Codeforces Round #301 (Div. 2)

題目: http://codeforces.com/contest/540/problems

A: (Math, Greedy)

這題在老細的壓力下完成, 直接地說, 我是看Sample猜題目直接做直接交一棍AC...

題目就是給了兩個平時單車用的密碼鎖的密碼, 問你從第一個轉到第二個最少要多少下

就是每個digit greedy地看順時針轉還是逆時針轉較好了

B: (Math, Greedy)

沒想到這題卡我那麼久 害我WA了很多棍...

其實題目沒什麼好想的, 題目說明 n 個數字裡面給你 k 個 (n肯定是odd number)

然後問你能否把剩下的 n-k 個數字填上, such that SUM <= X && Median >= Y

思路大約就是Greedy地填, 由於想SUM<=X, 我們能填最少的都填最少 (i,e, 1)

但又想Median >= Y, 所以把n 個數字排序後,(假設已填好)  頭 n/2  個數字可以是1

中間那個數字及之後的直接填Y

這樣肯定SUM是最少的同時, MEDIAN 又 >= Y, 最後查一查SUM是否真的 <= X就好了

問題來了, 這題好多Case需要分析考慮...

例如可能給你的 k 個數字全部都 < Y, 而 k > n/2, 則答案直接是 -1

還有很多其它可能性...

簡單來說, 思路是這樣做的了, 但很多Case如果沒考慮就很易WA / 被Hack...

這題做Div. 2 的B 也算是有點難了 我個人認為 即場玩的話應該很多人都是Hack這一題來得分吧 以下是很難看的AC Code:

#include<bits/stdc++.h>
using namespace std;

int n,k,p,x,y,p1=0,p2=0, sum = 0;
vector<int> ans;
int main(){
    scanf("%d%d%d%d%d", &n, &k, &p, &x, &y);
    for(int i=0,a; i<k; i++){
        scanf("%d", &a); 
        sum += a;
        if(a < y) p1++; else p2++;
    }
    if(p1 > n/2) printf("-1\n");
    else{
        for(int i=0; i<min(n/2 - p1, n-k); i++) { ans.push_back(1); sum ++; }
        for(int i=0; i<n/2 - p2 + 1; i++) { ans.push_back(y); sum += y;}
        
        if(sum <= x) for(int i=0; i<ans.size(); i++) printf("%d ", ans[i]);
        else printf("-1\n");
    }
    return 0;
}

C: (Graph)

題目自己看, 看完再來看是我腦殘還是它語癌

題目給了一個 N*M 的Grid, 是典型用BFS 問由 S 能不能到 T 的問題

題目中說明每一格如果經過了一次, 會有裂痕, 第二次再經過就會掉下去了

本身格子有些已經裂了, 而S 是肯定裂的 (這個對Implement上有些影響)

問能否由S 到 T?

好了 我一直到不久前的理解是....我看到是 side view, 也就是說如果一格裂了

再到那一格, 玩家會直接掉去下面一格,  要是下面一格也裂了,就再掉...這樣

這樣的話問題就很複雜了, DFS/ BFS那種沒什麼次序的Transverse好像不行, 因為先走那一格都會影響到往後所有path...不能隨便走走走一直走到終點

反正就是沒什麼Idea

搞了很久, 甚至看了Editorial也不明白....到最後..真相是

題目的Grid 是Top View...所謂掉下去是...該格不能再走而已...

這樣就很簡單了..變回普通的BFS問題

但也沒這麼直接

首先由於題目要求的是走到T 那一格然後掉下去

所以如果T 本身是裂的, 那只要有Path到達就好了

如果T 本身沒裂, 則它旁邊最少要有 2個 "沒裂的格子"

(數"沒裂的格子"時要數上起點 S, 即使 S 已經裂了, 但如果它是T 的鄰居, 可以直接走去T使T變裂)

另外 S = T 也是Special Case, 處理方法是看 "沒裂的格子(不算S)" 是否 >= 1

基本上剩下的就是用BFS 看有沒有PATH能從S 到T 

當中注意的是每格不是用 isVisit[] 來看能不能走, 是直接看是不是裂的 (或者終點)

要是裂的直接當不能走, 要是能走的, 走完 (把點PUSH入QUEUE) 後 把該格變裂

#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,tx,ty;
char w[505][505];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
queue< pair<int,int> > q;
bool bfs(int cx, int cy){
    q.push({cx, cy});
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        if(x == tx && y == ty) return true;
        q.pop();
        for(int i=0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(w[nx][ny] == '.' || (nx==tx && ny==ty)) {
                q.push({nx,ny}); w[nx][ny] = 'X';
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d", &n,&m);
    int cnt = 0;
    for(int i=1; i<=n;i++){
        getchar();
        for(int j=1; j<=m ;j++) w[i][j] = getchar();
    }
    scanf("%d%d%d%d", &sx,&sy,&tx,&ty);
    for(int i=0; i<4; i++) if(w[tx+dx[i]][ty+dy[i]] == '.' || (tx+dx[i] == sx && ty+dy[i]==sy)) cnt++;

    if(sx == tx && sy == ty){
        puts(cnt >= 1? "YES":"NO");
        return 0;
    }
    if(w[tx][ty] == '.' && cnt <= 1) { puts("NO\n"); return 0;}

    if(bfs(sx,sy)) puts("YES");
    else puts("NO");
    return 0;
}

這題聽完也會覺得思路也是直接但又是很多Case要Handle要考慮, 又一題Hacking 爆分的題目...

還好這場沒參加...

D: (Math, DP, Probability)

這題學到東西了

首先題目很直接

是一個猜包剪dup的遊戲

由於題目數據, 基本直接就想到是 dp(x,y,z) 的形式了

formula也很快寫出來了

但反而是每一個Event的Probability有點難數

打和的情況也在想怎樣Handle的時候

最後看Editorial發現我一直理解 "equiprobably" 都有點錯誤

題目中: At some moments of time two random individuals meet (all pairs of individuals can meet equiprobably)

開始我的想法是每一種出現的機會是 1/3...

但它用的字眼是 "all pairs of individuals" 總覺得意思不一樣  也好像不用搞得很複雜
(如果是原本的想法, 數 species A 的數目 再算 n 隻入面抽中它們其中一隻的probability 就是 pairs of individual中 會抽到A 的機率....總之很複雜...這也令我更肯定我一定要重溫 (重新學習) Probability了...)

總之原來不用簡單複雜化, 又用nCr 又什麼的

題目說什麼是equiprobably, 就直接數那個東西的數目

在這題中是 "all pairs of individuals"

那就直接數啊... 所有可能性 就是 N =  r*s + s*p * p*r   <---s,r,p 是剪, dup, 石頭的數目

然後假設那一pair是 rock 跟scissor, 就是 r*s / N 啊...

剪刀死了 就把數目減一再DP啊...

注意這兒是直接沒有數打和的情況, 不論分子分母都沒有數!

我不知有沒有term, 但我形容的是, 在它考慮 "probability space"時已經直接排除打和了..很聰明正確的做法

所以就是這樣了 

設 DP(R,S,P) := probability to make the island have R rocks, S scissors, P papers left

這題用Top-Down絕對更易做

 int rp = (r+1)*s + s*p + (r+1)*p;
 int rs = r*(s+1) + (s+1)*p + r*p;
 int sp = r*s + s*(p+1) + r*(p+1);

 if(rp)
     dp[r][s][p] = (r+1)*p*1.0 / rp * DP(r+1,s,p) ;
 if(rs)
     dp[r][s][p] += 1.0*r*(s+1)/rs * DP(r,s+1,p); 
 if(sp)
     dp[r][s][p] += 1.0*s*(p+1)/sp * DP(r,s,p+1);
 return dp[r][s][p];

可能會有一種物種已經全死光了, 所以要查一下 if(rp), if(rs)等等 看是不是有可能出現這個組合

那麼石頭會贏的Probability

就是 Sum DP(i, 0, 0)  

另外2個會贏的Probability也是這樣做, 下面是一棍AC的Code
(這題沒什麼陷阱, 是想到就做到的題目, 我認為C是更難的...)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int R,S,P;
double dp[105][105][105] = {0};

double DP(int r, int s, int p){
    if(r > R || s > S || p > P) return 0;
    if(dp[r][s][p]) return dp[r][s][p];
    
    int rp = (r+1)*s + s*p + (r+1)*p;
    int rs = r*(s+1) + (s+1)*p + r*p;
    int sp = r*s + s*(p+1) + r*(p+1);

    if(rp)
        dp[r][s][p] = (r+1)*p*1.0 / rp * DP(r+1,s,p) ;
    if(rs)
        dp[r][s][p] += 1.0*r*(s+1)/rs * DP(r,s+1,p); 
    if(sp)
        dp[r][s][p] += 1.0*s*(p+1)/sp * DP(r,s,p+1);
    return dp[r][s][p];
}

int main(){
    scanf("%d%d%d", &R, &S, &P);
    dp[R][S][P] = 1;
    double a1,a2,a3;
    a1=a2=a3 = 0;
    for(int i=1; i<=R; i++) a1 += DP(i,0,0);
    for(int i=1; i<=S; i++) a2 += DP(0,i,0);
    for(int i=1; i<=P; i++) a3 += DP(0,0,i);
    printf("%.12f %.12f %.12f\n", a1,a2,a3);
    return 0;   
}

E: (Binary Indexed Tree, STL, Ad-hoc)

昨天終於最後AC了這一題....雖然也是有一半是靠Editorial啦...

這題新學到的東西不多  倒是應用了不久前學的東西!

就是 用BIT 來Count 一個 Array的 # of Inversions!

這題當然沒這麼簡單, 單單是把位置 map去一個 O10^5)大的array再用這個技巧

已經是又要用STL的Map又要STL的Set (當然可以不用...但反正這些都不是Complexity的Bottleneck就算了)

題目要求的答案可以分開兩部分算:

第一部分就是用這個技巧

我自己卡是卡在第二部分沒想通...現在想就很合道理了:

For 每一對連續受影響(有swap過)的 index, 它們本身的inversion已經用BIT (第一部分算了)

但它們之間 沒Swap過的數字與它們的Inversion(如果有)則沒有算, 這就是第二部分

方法其實很簡單, for 每一個swap過的數字 x ,  找回它原本的index, 數它們之間有多少個數字也是swap過的, 減走它們! 因為這些swap過的數字不論有否跟 x 組成inversion, 它們也已經在BIT那部分受考慮了,  減走它們正正是 "沒被SWAP過的數字" 數量, 這些數字肯定跟 x 會形成inversion.... 找 x 原本的位置可以用Binary Search做

這樣的話總結來說是 O(n lg n)的算法

這題最開心的是, 之前新學的Trick可以派上用場...也算是有真正apply這個技巧的經驗!!

但要是我能改改那些不小心的習慣, 例如 array開小了導至Runtime error 等等.... :o)

這也是這題為什麼多人AC的原因

因為第二部分(我卡的部分) 其實不難想, 主要是要懂用Merge Sort / BIT 去找 # of inversions

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;

int n, bit[200010] = {0};
map<int,int> mp;
set<int> st;
vector<int> swapList, value;

void update(LL x){
    for(; x <200010; x+=(x&-x)) bit[x]++;
}

LL query(LL x){
    LL ret = 0;
    for(; x ; x-= (x&-x)) ret += bit[x];
    return ret;
}

int main(){
    scanf("%d", &n);
    for(int i=0,l,r; i<n; i++){
        scanf("%d%d", &l, &r);
        if(mp[l] == 0) mp[l] = l;
        if(mp[r] == 0) mp[r] = r;
        swap(mp[l], mp[r]);
        st.insert(l); st.insert(r);
    }

    int tmp = 1;
    for(set<int>::iterator it = st.begin(); it!= st.end(); it++){
        swapList.pb(*it); value.pb(mp[*it]); mp[*it] = tmp++;
    }

    LL ans1 = 0, ans2 = 0;
    for(int i=value.size()-1; i>=0; i--){
        int id = mp[value[i]], tt = i;
        ans1 += query(id);
        update(id);
        int pos = lower_bound(swapList.begin(), swapList.end(), value[tt]) - swapList.begin();
        if(pos < tt) swap(pos, tt);
        ans2 += swapList[pos]-swapList[tt] - (pos-tt);

    }
    printf("%I64d\n", ans1+ans2);


    return 0;
}

看看能不能在下星期內也學回GCJ 1B / 1C 的題目吧...要是清掉了就沒什麼累積的東西了~

Segment Tree + BIT (Fenwick Tree) In Deep

今天GCJ Round 1C也GG了...要是早點交A-large 或者不做C-small...應該就過了...
看來要拿T-Shirt還有段距離, 明年請早 :"(

回到正常的步伐, 繼續原本計劃好的學習旅程
(大學時期每次打完比賽都會頹廢很久, 現在能直視自己的失敗真的感恩)

再來一篇記Concept / 技巧的文...
(因為這陣子除了GCJ都沒怎樣打完整的比賽, 較少比賽題目的紀錄)

這篇是針對Segment Tree 和 BIT 的一些深一步的了解而寫的

說是In Deep其實也是一些對Div.1 玩家來說很common的東東

其中有些concept我也不是100%肯定 但暫時理解是這樣

Segment Tree + BIT (Fenwick Tree) In Deep

首先故事是這樣的, 萬惡也是從Stack Overflow開始

我閑逛Stack Overflow的時候, 看到了一題有關SPOJ的題目

是關於Segment Tree的, 由於該問發問者的名稱很不錯 (叫Wen_dy)

我決定看一下, 發現是很赤裸的Segment Tree題目

1. Range Add Value
2. Range Query Sum

題目在此: http://www.spoj.com/problems/HORRIBLE/

BIT (Fenwick Tree) Part

本想借此重溫一下Segment Tree...沒想到一下子就卡住了

才發現根本一直都沒搞清楚Segment Tree的結構 (所謂沒搞清楚下面會再講)

然後更嚴重的是, 看了SPOJ下面的Comment, 竟然有人說可以用BIT做!

怎樣想也不懂...結果就跑去查了....

幸好找到了一個很好很好的BIT 說明 Reference:

https://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/
裡面還有一個更好的Reference, 是來自Quora的, 有信心保證:
http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree

讓我引用一下裡面說的東西:

基本上, BIT出現的形式有3種: 

Range Update Point Query . Point Update Range Query, 和最麻煩的Range Update Range Query

然後文中給出了頭2種基本的例子...大同小異的

Range Update Point Query 
Point Update Range Query

然後就是重中之中, 這題目要用到的技巧: Range Update Range Query!

長話短說, 這個技巧是用上 兩個BIT Array去完成的

update(ft, p, v):
for (; p <= N; p += p&(-p))
ft[p] += v

# Add v to A[a...b]
update(a, b, v):
update(B1, a, v)
update(B1, b + 1, -v)
update(B2, a, v * (a-1))
update(B2, b + 1, -v * b)

query(ft, b):
sum = 0
for(; b > 0; b -= b&(-b))
sum += ft[b]
return sum

# Return sum A[1...b]
query(b):
return query(B1, b) * b - query(B2, b)

# Return sum A[a...b]
query(a, b):
return query(b) - query(a-1)

上面的Code中的B1 是普通的Range Update Point Query, 可以用它來Range Add和Query某一個位置的value a[p]

然後考慮一下 index p 的range, 來想一下Range Update [a,b] Add v 後

S[p] = Sum [1..p] 的值會怎樣

1 <= p < a : 0
a <= p <= b : v * (p – (a – 1))
b < p <= N : v * (b – (a – 1))

留意假設只有這個Update的話, 只有上面第2點的range內會有value, 其它的value 都是0

所以如果我們Query B1(p) 的話 (就如上面說的, 就是普通的Point Query, 所以是a[p])

再乘以p自己, 然後得出的值如下:

1. 0
2. v*p
3. 0

對比上面我們想要得到的算式 (就是Sum[1..p]的算式)

不難發現對於每個range, 其實也是 Query B1(p) * p 減去一個constant X:

1. 0 - 0  = 0   --> X = 0
2. v*p - v*(a-1) =  v*(p-(a-1)) --> X =  v*(a-1)
3. 0 - (-v*(b-(a-1))) = v*(b-(a-1)) --> X =  -v*b + v(a-1)

B2 說白了, 就是儲存這個X的另一個 BIT (也是Range Update Point Query的形式)了

For 一個Update Query [a,b] + v: 

B2 先 Update B2 (a, v*(a-1)) <---所有 >= a 的 index都有影響

再Update B2 (b, -v*b) <-- v*(a-1) 的部分上面包括了

那麼: Query(L,R) = Sum[1..R] - Sum[1..L-1]  

= (Query(B1, R)*R - Query(B2, R)) - (Query(B1, L-1)*(L-1) - Query(B2, (L-1)))

(這兒順帶學習了C++一個很簡單的東西: 只要signature不同, function同名都可以, 於這兒不同種類的Update()/ Query() 利用會很方便)

再想個複雜一點的例子來說明Concept
假設現在有2個Range Query [a,b,v1] 和 [c,d,v2]

再假設現在想找 Sum[1..p] where p 只在 [c,d]內而不在[a,b]內

那麼Query(B1, p)*p 是多少? Query(B2, p) 又是多少?

Query(B1,p) =  (0+v2)  <--0是因為不受第一個Query影響

Query(B2,p) = -v1*b + v1*(a-1)   + v2*(c-1)

所以

Query(B1, p)*p - Query(B2,p) =   (0+v2)*p - (-v1*b + v1*(a-1)   + v2*(c-1))

= 0 - (-v1*b+v1*(a-1))    +    v2*p - v2*(c-1)

-->Sum[1..p] from Query 1 + Sum[1..p] from Query 2

其它Case也差不多可以這樣分解, 代表 n 個update 之後,  仍然可以用這個方法去Range Query的

道理上明白了, 最要緊是記得如何找出X, 自然就可以很簡單Code出來了

可惜BIT只能處理Add / Sum 之類的function...

下面是用這個變態技巧過 SPOJ Horrible的Code:

#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL T, n, c, t,p,q, v;
LL bit1[100005], bit2[100005];

void add(LL* bit,int x, LL v){
    for(; x <= n; x+= x&(-x)) bit[x] += v;
}
void add(int x, int y, LL v){
    add(bit1,x, v); add(bit1,y+1, -v);
    add(bit2,x, v*(x-1)); add(bit2, y+1, -v*y);
}

LL query(LL *bit, int x){
    LL ret = 0;
    for(; x ; x-= x&(-x)) ret += bit[x];
    return ret;
}
LL query(int x){
    return query(bit1, x)*x - query(bit2, x);
}

LL query(int x, int y){
    return query(y) - query(x-1);
}

int main(){
    scanf("%I64d", &T);
    while(T--){
        memset(bit1,0,sizeof(bit1));
        memset(bit2,0,sizeof(bit2));
        scanf("%I64d%I64d", &n,&c);
        for(int i=0; i<c;i++){
            scanf("%I64d%I64d%I64d", &t, &p, &q);
            if(!t) scanf("%I64d", &v);
            
            if(!t) add(p,q,v);
            else printf("%I64d\n", query(p,q));
        }
    }
    return 0;   
}

Segment Tree Part

學完新技巧, 回歸原點, 我決定以Segment Tree再過這一題

(人家在Stack Overflow原文是求Segment Tree的答案嘛...)

才發現自己對Segment Tree的理解是如此低

當年開了頭學習了基本implementation, complexity等等的東東

但仍是不到位

這題 (Range Add, Range Query Sum) 我印象中算是很Standard了

也肯定在POJ Code過類似的題目, 但這時又忘了..

才更覺得要認真看待這個Data Structure, 問了GG後, 又再看了看一些Reference後

又有一些(好像)深一點的理解

我看的是這個Reference:

http://letuskode.blogspot.in/2013/01/segtrees.html

(裡面附送人家寫的Segment Tree STL, 但它的方式實在不合口味, 雖然是很強大, 還是學Concept算了...)

首先是這個神奇的, 似懂非懂的Term: Lazy Propagation

原來一直聽的這個詞, 是等價於另一些人可能會說的Terms, 例如: Split, Push Down

但其意思/ 意義是一樣的, 指向同一個"動作"

這個動作的原意是想避免每次Update / Query 都會去到葉子

經POJ某份PDF所說, 這樣好像可以去到O(N), 不懂Proof, 感覺也不對, 但總之就是很慢, 慢到會TLE的樣子 (for eg: Range Update [a,b], 如果每次都到葉子, implementation很簡單, 也肯定正確, 但就是太慢了, 要是[a,b] 每次都是 [1,n] 怎辦?)

所以就出現了這個方法: Lazy Propagation, 故名思意, 就是要用到 (Tranverse到那一個Segment Node) 時候才Update Node的Information

而Lazy Propagation 之外, 又有另一種常聽 / 見的字眼: Merge, Pull Up...

這又是Segment Tree內另一種動作, 跟Lazy Propagation相對的

究竟這2種動作是什麼來的, 如何運作, 何時使用?

有沒有一種Standard的Rule / Structure決定, 何時要用上這些動作呢...

按GG 和該Reference所說, 是有的

Segment Tree的 Update / Query 是有一定結構的, 在不斷試驗理解後, 應該是這樣的:

Range Update():

    if (Current Segment covers the range){

        update this node's info; return;
    }

    Split();

    Recur Left / Right Son Part;

    Merge();

}

Range Query():

    if (Current Segment covers the range){

        return this node's info
    }

    Split();

    Recur Left / Right Son Part;

    Merge();

}

當中Split() 跟Merge() 是把Info 推向下層兩個兒子, 和從下層兩個兒子算出current segment的Info用的

就是這樣了! 原來是很Standard / General 的結構, 但為何以前很多時候都可以沒有Split / Merge呢?

原因是這樣的, 視情況而定, Node 的 Info, Split 和Merge的Implementation 也是視題目而定的...這就是Segment Tree難搞的地方, 因為沒有萬能藥, 可以萬年通用的Rule / Implmentation

但是還是有多少事情可以深入理解下:

首先, 不難發現到, 會執行Split 的 Segment, 也會執行Merge

那麼該Segement的Info 已經 1. 推向下層 2. 最後會由下層算出正確的Info

所以在Split的時候 基本上可以 把Info Reset了

例如在Horrible中, 一個Segment Node的Info 是 Sum 跟 Add

代表該Segment的總和, 和Add在該Segment的 value

在Split的時候, 先把Add 加去下一層, 又把下一層的Sum 加上 Add的value

然後需要把Add reset做 0 !

這時, 該Segment的下面2個node 的Sum已經update了, 要是有query的range 剛好包括它們2個其中1個, 那麼就如上面所說的, 直接return sum 就可以了, 要是還要再向下一層, 那麼會在query時再Split下去, recur下去

然後所有曾經Split下去的Segment的Sum 又會在Merge的時候從下面2個兒子算出 (下面2個兒子的Sum肯定正確的, 因為Split到盡頭時的Sum一定正確, 然後沿路一直Merge上來)

把Add reset做 0 是因為可能下次會再Update 該Segment

然後又可能會再需要Split下去, 記住我們Split的時候是把當時該Segment的Add Split下去再算Sum的 (用+=) 所以如果不reset 做0,  會加多很多value去下一層...

(這些Node的Split / Update, Merge等等的東西, 我極度懷疑真的是每題題目都要度身訂做, 慢慢試一些test case去試出來)

簡單地說, 這種Split 跟Merge的結構, 在我們從根到某個node的path, 經過path上的node時才一直push down 和merge (要是需要的話), 沒經過的path (上的node) 就不管了

這樣當然速度會相當快, 也不會TLE

最後Base on上面對Split 跟Merge的理解, 我有以下的猜測:

要是Update和Query 有其中一個不是Range的話, Split 跟Merge可能不用Implement:

如果是Point Update, 可能不用Split了...但需要Merge

如果是Point Query, 可能不用Merge了, 但需要Split

80%肯定, 但沒有Proof

反正最大的得著就是: Segment Tree的Update跟Query有很好很Stable的結構

但Node design, Split()和Merge()的 Implementation就真的要看題目了...

最後是用Segment Tree (Lazy Propagation) 過SPOJ Horrible的Code:

可以特別留意Split(), Merge() 的Implementation

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int T, n, c, p, q, v, t;

struct node
{
    int l,r,m;
    LL numleaves, add, sum;
    node(int l,int r, int m): l(l), r(r), m(m){
        add = sum = 0;
        numleaves = r-l+1;
    }
    node(){}
}tree[400010];

void build(int c, int u, int v){
    int m = (u+v)>>1;
    tree[c] = node(u,v, m);
    if(u == v) { tree[c].numleaves = 1; return;}
    build(2*c, u, m);
    build(2*c+1, m+1, v);
}

void push_down(int x){
    tree[2*x].add += tree[x].add;
    tree[2*x+1].add += tree[x].add;
    tree[2*x].sum += tree[x].add * tree[2*x].numleaves;
    tree[2*x+1].sum += tree[x].add * tree[2*x+1].numleaves;
    tree[x].add = 0;
}

void merge(int x){
    tree[x].sum = tree[2*x].sum + tree[2*x+1].sum;
}

void update(int c, int l, int r, int v){
    if(tree[c].l == l && tree[c].r == r){
        tree[c].add += v;
        tree[c].sum += v*tree[c].numleaves;
        return;
    }
    push_down(c);
    if(r <= tree[c].m) update(2*c, l,r, v);
    else if(l > tree[c].m) update(2*c+1, l,r, v);
    else{
        update(2*c, l, tree[c].m, v);
        update(2*c+1, tree[c].m+1, r, v);
    }
    merge(c);
}

LL query(int c, int l, int r){
    if(tree[c].l == l && tree[c].r == r){
        return tree[c].sum;
    }
    push_down(c);
    LL L,R; L = R = 0;
    if(r <= tree[c].m) L = query(2*c, l, r);
    else if(l > tree[c].m) R = query(2*c+1,l,r);
    else{
        L = query(2*c, l, tree[c].m);
        R = query(2*c+1, tree[c].m+1, r);
    }
    merge(c);
    return L+R;
}

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &c);
        build(1,1, n);
        for(int i=0; i<c;i++){
            scanf("%d%d%d", &t,&p,&q);

            if(!t) scanf("%d", &v);
            if(!t) update(1,p,q,v);
            else printf("%I64d\n", query(1,p,q));
        }

    }
    return 0;
}