學習日記15

           今天中午，老師帶領我們改變了學習政策。要先學習知識點，看題解，學習做題技巧和方法，然後再自己做題，這時候，就算做不出題來，也不能看那題解，同學之間互相商量，找出程式中的不足并解決它。 

          我先要制定自己的學習計劃，我打算看第一個人的部落格的時候，要慢慢看，把所有關于這個知識點的方法都掌握牢固，再接着看下一個，這樣再看下一個人的部落格時，很多相同類型的題，可能看一眼就知道怎麼回事了，隻需看一下需要注意的地方就可以了，把題浏覽一遍估計這道題就算是看完了。

          我今天把昨天看的基礎知識點又回看了一遍，一是因為感覺掌握的不牢固，二是要看部落格了，要把是以得基礎知識牢記在心才可以。下面就是我今天的主要收獲了，也是我記得筆記，在這裡存起來，下次忘記的時候友善查閱。

 一。---樹狀數組的基本函數。

              1。lowbit（）------算出a&（-a）

              2。add（）-------更新操作，當有某個值添加或者删除（增加或減少）的時候用。

              3。sum（）--------求和，sum（i）表示a[1]到a[i]的和。也可以求a[i]的值。

 二。----基礎操作----區間更新，單點求和。

               當[a,b]區間加1時。

               可以         add（a，1）；從這之後的sum（）都會加1。

                               add（b+1，-1）；   從這之後的sum（）都會減1。也就是從這之後原來的加一被抵消了。

               這樣原來的求和數組已經不是原來的意義了，這已經不是為了求和了。

               這時候在區間[a,b]内求一個值sum（i）會比原先加1.

 三。----基礎操作------單點更新，區間區和。

當需要a[i]增加d時，

可以       add（a[i]，d）；

這樣   當 x > i 時，sum（x）求和都增大了d。

求和時，求區間[ j , k  ] 的和，sum（k）- sum（j-1）；

四----離散化

離散化一般都要定義結構體，結構體裡一般包含兩個數，一個數是輸入的原值 v ，一個數是記錄輸入的先後次序的  id。

1。在輸入資料時，要便輸入邊對結構體的 id 進行指派，從1到n。（輸入的先後順序）

2。根據結構體中資料的大小進行排序。（排序）

3。建立立一個數組b，結構體的 id  作為數組下表，然後，根據排序的先後順序，給數組b賦從1到n的值代表他們原來的大小關系。（大小的代換）

離散化完畢，現在這些不集中的資料，已經變得集中了。在處理資料大，資料量不大的資料時可以采用離散化。

五-----順序對 （在b[ i ]前面，比b[ i ]小的數的數量）

當離散化完畢後會得到一個數組  b[ i ] ，   b[ i ] 代表原來值的大小，  i  代表輸入的先後順序。（沒有離散也是一樣的）

求順序對時，

先求加和          ans+=sum（b[ i ]）；

後更新             add（b[ i ] ，1）；

sum（b[ i ])  是比b[ i ]先進入數組 且 比 b[ i ]要小的數，也就是以b[ i ]結尾的順序對的數量。

ans   就是全部的順序對的數量。

六-------逆序對（在b[ i ]前面，比b[ i ]大的數的數量）

當離散化完畢後會得到一個數組  b[ i ] ，   b[ i ] 代表原來值的大小，  i  代表輸入的先後順序。（沒有離散也是一樣的）

先更新             add（b[ i ] ，1）；

後求加和          ans+=n-  sum（b[ i ]）；

n是此時進入數組的數的數量。

sum（b[ i ])  是比b[ i ]先進入數組 且 比 b[ i ]要小的數。

兩者相減就是比b[ i ]先進入數組 且 比 b[ i ]要大的數。（就是以b[ i ]結尾的逆序對的數量）

ans   就是全部的逆序對的數量。

當看完了這個我曾經想過，到底有沒有三對上升，或者四對，甚至n對那。果然，那是有的。

七----三對順序或者逆序。

當一個數存入數組用1來表示，沒有存入用0來表示，本身這個樹狀數組就不是求和了。

因為樹狀數組的sum1（k）操作，取出的數字，表示比 k  先進入數組的，比k 小的數的個數，也就是輸入時，排在k前面比 k 小的數的個數。這是，按照輸入順序放入樹狀數組的情況。

當倒着把資料放入樹狀數組時，sum2（ k ），取出的數字，就是排在 k 後面的，比k 小的數字的個數。

那麼當正着輸入時   max1=k - sum1（k）

倒着輸入時   max2= n - sum2（k）

此時，max1就是排在 k 前面比k大的數的個數。

max2就是排在 k 後面比 k 大的數的個數。（這個原因在六，逆序對中有）

最後的總數就是   sum1（k）*max2+sum2（k）*max1；

八-----連續上升或下降的n元子序列的求法。（這裡說四元上升子序列）

可能用到的知識點   1.離散化（如果資料過大）2 dp（當n>3）時，比如現在是四。3 樹狀數組  （n個）  4 高精度（如果64位都不夠用的話）

輸入資料為a[ i ]。

下面的   x  y都是a [ i ] 。。。  sum（）不是樹狀數組的函數了，是對裡面的所有符合條件的數組求和。

dp過程

dp[ x ][ 2 ] = sum(dp[ y ][ 1 ])；

dp[ x ][ 3 ] = sum(dp[ y ][ 2 ])；

dp[ x ][ 4 ] = sum(dp[ y ][ 3 ])；

其中dp[ x ][ 2 ]  表示的意思是，x為子序列最後一個數字時的二進制上升子序列的個數。

因為所有的3元都是來自于之前的二進制，是以可以用這個來實作。

其中的樹狀數組有n個，每次輸入一個資料，都需要對所有的樹狀數組進行更新。

九-----求逆序的一個有意思的題型。（這種題需要離散化之後再做）

從1到n有n個數，叫做 a[ i ] ，雜亂的排成一行，可以算出他們的逆序對數的綜合 ans ，但是，現在你需要把a[ 1 ]放到a[ n ]後面，然後再算逆序對數，下一步，把現在的a[ 1 ]放到後面，再算一次，知道循環完畢。要求算出最小的逆序對數。

這時，我們先按照算逆序對數的正常思路，算出ans，

如果第一個移動到最後的時a[ 1 ]，在除了a[ 1 ]的所有數中，比a[ 1 ]小的數的個數min=a[ 1 ]-1；

                                                                                                         比a[ 1 ]大的數的個數max=n-a[ 1 ]；

但是，移動的時候，關于a[ 1 ]的逆序對數改變了，當然其他的沒變，原來比它小的，變成了順序，比它大的變成了逆序。

也就是ans+=max-min；這樣就求出了在這一次移動中，ans的變化，然後我們隻需要讓它循環n-1次，就求出了最小的ans（逆序對的個數）。

這種方法的關鍵就是a[ i ]是由1到n的，就是需要離散化。

今天學習的主要内容就是這些了，我把我記錄的書面筆記，比較條理的整理了一遍，複習了一遍，很多記得不是很清楚的地方都變得清楚了，通過今天一天的學習，我的收貨很大，希望我能不斷汲取知識，不斷成長，讓我的内力越來越深厚，招式越來越複雜。

祝明天更美好。