信息學(xué)競賽中的差分技巧

信息學(xué)競賽中的差分技巧差分差分與前綴和在算法中往往對(duì)應(yīng)存在，它是一種策略或者是一種技巧。差分在各級(jí)別的算法競賽中幾乎沒有獨(dú)立考察的機(jī)會(huì)，它往往會(huì)作為一個(gè)技巧與某主要考點(diǎn)配合使用，比如區(qū)間求值問題，或樹問題等。令b[i]=a[i]?a[i-1]，即相鄰兩數(shù)的差，即是差分。差分?jǐn)?shù)組可以通過前綴和得到原數(shù)組。差分和前綴和是逆運(yùn)算。一維差分對(duì)于一個(gè)給定的一維數(shù)組arr[]，它的一維差分?jǐn)?shù)組d[]中的d[i]表示數(shù)組arr[]的第i個(gè)元素與第i-1個(gè)元素的差。用公式表示為：d[0]=arr[0],i==0；d[i]=arr[i]-arr[i-1],i>=1。一維差分?jǐn)?shù)組d[]的前綴和就是一維數(shù)組arr[]。一維差分在區(qū)間求值問題上的應(yīng)用快速將數(shù)組arr[]的區(qū)間[l,r]加一個(gè)值v。設(shè)有m次這樣的區(qū)間操作，每次操作給出l,r和v。要求輸出m次操作后的數(shù)組arr[]。遍歷區(qū)間[l,r]中的所有元素并加上一個(gè)值v，是最傳統(tǒng)的暴力思路。這樣的區(qū)間操作，每次的時(shí)間復(fù)雜度為O(n)，要求進(jìn)行m次，所以時(shí)間復(fù)雜度為O(m*n)。使用差分可以將在數(shù)組arr[]上的區(qū)間操作轉(zhuǎn)化為在差分?jǐn)?shù)組d[]上的"單點(diǎn)操作"。即將區(qū)間修改，轉(zhuǎn)化為單點(diǎn)修改。轉(zhuǎn)化方式：將數(shù)組arr[]的區(qū)間[l,r]加一個(gè)值v等價(jià)于將差分?jǐn)?shù)組中的d[l]+v，d[r+1]-v。差分?jǐn)?shù)組的前綴和相當(dāng)于原數(shù)組，所以給差分?jǐn)?shù)組中的d[l]+v，d[r+1]-v就相當(dāng)于將數(shù)組arr[]的區(qū)間[l,r]加一個(gè)值v。最終的時(shí)間復(fù)雜度為O(n+m)。一維差分的局限性一維差分可以將時(shí)間復(fù)雜度O(n)的區(qū)間修改，改為O(1)的端點(diǎn)修改。但是差分?jǐn)?shù)組對(duì)于單點(diǎn)查詢的效率不夠，一次查詢arr[i]需要計(jì)算d[i]的前綴和，時(shí)間復(fù)雜度為O(n)。例如長度為n的數(shù)列進(jìn)行m次區(qū)間修改，k次單點(diǎn)查詢，使用一維差分?jǐn)?shù)組的時(shí)間復(fù)雜度為O(m+n*k)，使用暴力算法的時(shí)間復(fù)雜度為O(m*n+k)。因此區(qū)間修改+單點(diǎn)查詢的問題，經(jīng)常使用差分?jǐn)?shù)組+樹狀數(shù)組/線段樹的組合。一維差分模板輸入一個(gè)長度為n的整數(shù)序列。接下來輸入m個(gè)操作，每個(gè)操作包含三個(gè)整數(shù)l，r，c，表示將序列中[l,r]之間的每個(gè)數(shù)加上c。請(qǐng)你輸出進(jìn)行完所有操作后的序列。輸入第一行包括兩個(gè)整數(shù)n和m。第二行包括n個(gè)整數(shù)，表示整數(shù)序列。接下來m行，每行包括三個(gè)整數(shù)l，r，c，表示一個(gè)操作。輸出共一行，包含n個(gè)整數(shù)，表示最終序列。輸入樣例：輸出樣例：63345342122121021241051二維差分一個(gè)給定的二維數(shù)組arr[]，它的二維差分?jǐn)?shù)組d[]中d[i][j]可以用如下公式計(jì)算：d[0][0]=arr[0][0],i,j==0；d[0][j]=arr[0][j]-arr[0][j-1],i==0,j>=1；d[i][0]=arr[i][0]-arr[i-1][0],i>=1,j==0；d[i][j]=arr[i][j]-arr[i-1][j]-arr[i][j-1]+arr[i-1][j-1],i,j>=1二維差分應(yīng)用二維差分的主要用處是快速地將一個(gè)區(qū)塊中的所有元素都加上一個(gè)值v。使用差分可以將在數(shù)組arr[]上的區(qū)塊操作轉(zhuǎn)化為在差分?jǐn)?shù)組d[]上的單點(diǎn)操作。差分矩陣模板輸入一個(gè)n行m列的整數(shù)矩陣，再輸入q個(gè)操作。每個(gè)操作包含五個(gè)整數(shù)x1,y1,x2,y2,c，其中(x1,y1)和(x2,y2)表示一個(gè)子矩陣的左上角坐標(biāo)和右下角坐標(biāo)。每個(gè)操作都要將選中的子矩陣中的每個(gè)元素的值加上c。請(qǐng)你將進(jìn)行完所有操作后的矩陣輸出。輸入第一行包含整數(shù)n,m,q。接下來n行，每行包含m個(gè)整數(shù)，表示整數(shù)矩陣。接下來q行，每行包含5個(gè)整數(shù)x1,y1,x2,y2,c，表示一個(gè)操作。輸出共n行，每行m個(gè)整數(shù)，表示所有操作進(jìn)行完畢后的最終矩陣。輸入樣例：輸出樣例：343234112214341322122221111001110212220231代碼略。有興趣的朋友可以在網(wǎng)站留言區(qū)討論代碼，謝謝。三維差分元素值用三維數(shù)組arr[][][]來定義，差分?jǐn)?shù)組d[][][]也是三維的。與之前低維度的差分類似，把三維差分想象成立體空間的操作。與之對(duì)應(yīng)的小立方塊有8個(gè)頂點(diǎn)，所以三維的區(qū)間需要修改8個(gè)d[][][]的值。在二維差分中，arr[][]是差分?jǐn)?shù)組d[][]的前綴和，即原點(diǎn)坐標(biāo)(1，1)和坐標(biāo)(i，j)圍成的矩陣面積。在三維差分中，arr[][][]是差分?jǐn)?shù)組d[][][]的前綴和，即原點(diǎn)坐標(biāo)(1,1,1)和坐標(biāo)(i,j,k)圍成的立體體積。把每個(gè)d[][][]看成一個(gè)小立方體，在坐標(biāo)(1，1，1)~(i，j，k)所圍成的空間中，所有小立體加起來的總體積即為arr[i][j][k]。在三維情況下，差分就變成了相鄰的arr[][][]的體積差。三維的差分?jǐn)?shù)組d[][][]，其遞推式如下：d[i][j][k]=s[i][j][k]?s[i?1][j][k]?s[i][j?1][k]?s[i][j][k?1]+s[i?1][j?1][k]+s[i?1][j][k?1]+s[i][j?1][k?1]?s[i?1][j?1][k?1]差分?jǐn)?shù)組應(yīng)用：三體攻擊三體人將對(duì)地球發(fā)起攻擊。為了抵御攻擊，地球人派出了A*B*C艘戰(zhàn)艦，在太空中排成一個(gè)A層B行C列的立方體。其中第i層第j行第k列的戰(zhàn)艦（記為戰(zhàn)艦(i,j,k)）的生命值為d(i,j,k)。三體人將會(huì)對(duì)地球發(fā)起m輪“立方體攻擊”，每次攻擊會(huì)對(duì)一個(gè)小立方體中的所有戰(zhàn)艦都造成相同的傷害。具體地，第t輪攻擊用7個(gè)參數(shù)lat,rat,lbt,rbt,lct,rct,ht描述；所有滿足i∈[lat,rat],j∈[lbt,rbt],k∈[lct,rct]的戰(zhàn)艦(i,j,k)會(huì)受到ht的傷害。如果一個(gè)戰(zhàn)艦累計(jì)受到的總傷害超過其防御力，那么這個(gè)戰(zhàn)艦會(huì)爆炸。指揮官希望你能告訴他，第一艘爆炸的戰(zhàn)艦是在哪一輪攻擊后爆炸的。輸入第一行包括4個(gè)正整數(shù)A,B,C,m；第二行包含A*B*C個(gè)整數(shù)，其中第((i?1)*B+(j?1))*C+(k?1)+1個(gè)數(shù)為d(i,?j,?k)；第3到第m+2行中，第(t?2)行包含7個(gè)正整數(shù)lat,?rat,?lbt,?rbt,?lct,?rct,?ht。輸出第一個(gè)爆炸的戰(zhàn)艦是在哪一輪攻擊后爆炸的。保證一定存在這樣的戰(zhàn)艦。數(shù)據(jù)范圍：1≤A*B*C≤10^6,1≤m≤10^6,0≤d(i,?j,?k),?ht≤10^9,1≤lat≤rat≤A,1≤lbt≤rbt≤B,1≤lct≤rct≤C，層、行、列的編號(hào)都從1開始。輸入樣例：輸出樣例：2223211111111121211111121211111112此題為典型的區(qū)間修改、查詢題目，且區(qū)間為三維。某一維的數(shù)據(jù)范圍在10^6，用暴力會(huì)導(dǎo)致直接超時(shí)。使用差分修改，在O(1)的時(shí)間復(fù)雜度，代替暴力O(n^2)修改，會(huì)好一些