前四天看了一下國慶專輯的題目，隻出了E題。
這個題目要求求區間最值，區間最值其實和區間求和差不多，就是将sum數組的含義轉移到max，然後通過特定的區間更新max。
在區間求和中，當我們維護max[i]的時候，要找到它前面所有的max[j]來更新，畫圖可知，max[i]需要的max隻有max[i-2^0],max[i-2^1],max[i-2^2]..max[i-lowbit(i)+1]。求區間最值時，很容易看出，我們找[l,r]的最值就是找在次區間的max，即遞減r，在這裡可以有個優化，即當找到一個max[i]，有i-lowbit(i)>=l時，更新後，i直接-=lowbit(i)，然後繼續遞減，當l>r就跳出循環。
A題 ：因為操作中隻有詢問沒有更新，可以對所有問按右區間升序排序。以該數字第一次在區間中出現的點代表所有的點。如果是第一次出現，那麼該數字在之前從未出現或上一次出現不再區間内。記錄每個位置i的數字的前一個相同數字出現的位置hash[i]，沒有前一個相同的hash[i]為0。然後從前到後掃描詢問，每次将上一個同值點的值加1，然後求目前區間的左界的字首和就是答案了。将目前位置下個位置的值減1，這樣做可以保證任意一個數字在任意一段區間中最多出現一次。但是一直都是逾時...
後面幾天做了樹狀數組和線段樹的專題。
樹狀數組D題：
題意：
共n個數，m次操作，Q表示詢問n個數有多少順序數，R a,b表示區間[a,b]中的數轉動一下（a+1~b每個數向前移動，a位置的數到b位置）.
思路：
如果每詢問一次就求一次順序數很費時間，先求出最初的順序數ans，每轉動一次時如果a+1~b位置的數大于a位置的數,ans--,如果小于a，ans++，那麼就用到了數狀數組求逆序數。
樹狀數組F題：
題意：N*N*N的立方體，元素為0或1（初始為0）。1操作将（x1,y1,z1）到（x2,y2,z2）之間的元素取反；0操作是詢問（x,y,z）為0或1。
題解：三維樹狀數組，原理跟一維，二維一樣。
樹狀數組O題：
題意：
BLACK x y l是指将第x行，y列到第x+l-1行，y+l-1列翻成黑色(初始化時為白色)
WHITE x y l是指将第x行，y列到第x+l-1行，y+l-1列翻成白色(初始化時為白色)
TEST x y l是指求從第x行，y列到第x+l-1行，y+l-1列中白色的有幾個。
解題思路：
這個題目可以用樹狀數組來做，更新一個二維區間，查找一個二維區間兩個函數，其中更新區間。
還看了看線段樹中關于掃描線的知識，是之前看HDU 1828的問題了解的，本題求得是周長,是以将所有上下位邊按y從小到大排序之後:
首先我們讀入第一條掃描線(下位邊+1),這條掃描線的長度直接加入ans結果中.
現線上段樹整體就有兩條豎向邊了(平行于y軸的),是以這兩條豎向邊從第一條掃描線到第二條掃描線之間是會增漲的,是以總周長ans+=2*(第二條掃描線的高h2-第一條掃描線的高h1).
然後我們讀入第二條掃描線(下位邊+1):
由于我們更新完這條掃描線後,sum[1]覆寫的範圍擴大了5,是以ans先加5.其次這個時候,我們的豎向邊由兩條變成了3條,是以ans+=3*(掃描線3的高度h3-掃描線2的高度h2).
然後我們讀入第三條掃描線(上位邊-1):
由于我們讀入該掃描線後sum[1]的覆寫值少了5,但是此時我們看圖知道其實這個矩形的另一條上邊了.是以我們不能用ans+=sum[1]了,我要執行ans+=abs(last-sum[1]),其中last是上一輪讀入掃描線後sum[1]的值。