496
模擬-hdoj-4831-百度之星2014初賽第二場
Scenic Popularity
Problem Description
臨近節日，度度熊們最近計劃到室外遊玩公園，公園內部包括了很多的旅遊景點區和休息區，由於旅遊景點很熱門，導致景點區和休息區都聚集了很多人。所以度度熊在旅遊之前想通過百度地圖查看一下公園內各個地方的熱門程度。
假設所有景點區和休息區都是X軸直線上的一係列頂點，所對應的坐標Xi 保證唯一。每個景點區有個初始的熱度值，而一個休息區(坐標為Xi)的熱度值等於離它距離最近的景點區Xj的熱度值（距離定義為|Xi-Xj|），如果此休息區與兩個景點區的距離一樣，則休息區的熱度值選擇兩個景點區中的熱度值最大值，如果兩個熱度值都一樣，則隨意選擇其中一個。
度度熊在出門之前會經常去查看百度地圖，每次查看前會有某些景點區的熱度值已發生改變，從而也會導致周圍的休息區的熱度值發生改變，然後度度熊想知道當前熱度值<=Rk的頂點(包括景點區和休息區)有多少個
Input
輸入數據的第一行是測試Case的個數(T<=100）。
每個Case的第一行是N(0<N<=10000)，表示景點區和休息區的總數。
接著會有N行數據，每一列首先是頂點的X坐標Xi (0< Xi <=1e8)，第二列是一個整數Hi(0=<Hi <=100000)，如果Hi 不為0，則表示當前頂點為風景區且初始的熱度值為Hi，否則表示當前頂點為休息區。這N行數據會按照坐標Xi遞增的方式依次給出。
接著的一行數據是操作的次數K(K<=100)，最後會有K行數據，每一行的第一列要麼是’U’或者’Q’，’U’表示當前操作為更改熱度操作，’Q’表示當前操作為查詢操作。如果是更改操作，接著會有兩列數據，分別是熱度值要改變的風景區的下標Lk(0<=Lk<N)以及改變後的熱度值Vk(0< Vk<=100000)；如果是查詢操作，第二列是要查詢的熱度範圍Rk(0< Rk<=100000)
Output
對於第k組測試數據，第一行輸出Case #k:，接下來對每次查詢操作(即Q操作)會輸出一個整數，表示滿足條件的頂點數有多少個
Sample Input
1
4
10 0
20 3
30 0
40 2
3
Q 3
U 3 4
Q 3
Sample Output
Case #1:
4
2
Source
2014年百度之星程序設計大賽 - 初賽（第二輪）
樹狀數組貌似是考察點。我目前隻會模擬，閑了再說。
最後更新：2017-04-03 08:26:17