由于程序很多所以就不放在上面了。
只是寫了一下總結(jié)。
樹狀數(shù)組題目列表
POJ 3378 Crazy Thairs (WA)
POJ 2481 Cows AC
POJ 2352 Stars AC
POJ 3321 Apple Tree AC
POJ 3067 Japan AC
POJ 1195 Mobile phones AC
POJ 2155 Matrix AC
POJ 1990 MooFest AC
二中培訓(xùn)題3 【這顯然是線段樹吧。。。】
總結(jié)
第一周寫作業(yè)就沒寫完。。。對不起大家。
留下了三道題目繼續(xù)思考。那個培訓(xùn)題3就當(dāng)做下一周的線段樹吧。
poj2352（3次AC）
根據(jù)題意用樹狀數(shù)組模擬。
這道題我竟想了好久，寫完之后數(shù)組上向下溢出。。。
（可能是英語水平退步的緣故，讀完題各種條件印象不深）
poj1195（2次AC）
二維樹狀數(shù)組
一開始沒有注意循環(huán)的處理，由于樣例不過，檢查出來了。
改后提交WA，
原來是不小心打錯了y1->y2。。。
（沒有檢查！）
poj3067（AC）
排序+樹狀數(shù)組
貌似是以前做過的。。。但還是花了不少時間。（還研究了一下sort和qsort）
這里排序是雙關(guān)鍵字，用了cstdlib的快排。
關(guān)于cstdlib的快排用法的文章已經(jīng)轉(zhuǎn)到了我的cppblog
數(shù)據(jù)比較大，要用long long
【固定思維是：升序排序+樹狀數(shù)組倒著用。何必呢?樹樁數(shù)組才是主題，降序排序不就行了嗎。。。】
poj3378 (WA)
簡單DP
實現(xiàn)時用樹狀數(shù)組+離散化
數(shù)據(jù)規(guī)模大得驚人！！
寫了高精度后莫名地掛掉。
poj2155(AC)
模式二的水題，而且還可以化簡為 ^ 運算。。。
快速地學(xué)習(xí)了一下模式二就AC了
poj2481（5次AC）
看似只是簡單的sort+樹狀數(shù)組。
其實細(xì)節(jié)比較多，sort是雙關(guān)鍵字。
然后由
Given two cows: cowi and cowj, their favourite clover range is [Si, Ei] and [Sj, Ej].
If Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj, we say that cowi is stronger than cowj.
知邊界可以相同，又不能完全相同。
加上poj.org和我家的時間不一致，導(dǎo)致我以為沒有提交成功。。。提交了幾次錯誤的代碼。。。。。
poj3321（2次AC）
利用樹的歐拉序列，記錄每個節(jié)點的起始時間和它的子樹的結(jié)束時間。
化點為線，且a是b的子節(jié)點<==>區(qū)間a屬于區(qū)間b
怎么WA的一次忘記了。。
poj1990（AC）
這題是最難最難的。
按V排序，利用樹狀數(shù)組計算
sigma|xj-xi|=xi*sigma(1)[xj<xi]-sigma(xj)[xj<xi]
+sigma(xj)[xj>xi]-xi*sigma(1)[xj>xi]