分治 CDQ分治
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 1755 Solved: 764
有n朵花，每朵花有三個屬性：花形(s)、顔色(c)、氣味(m)，又三個整數表示。現要對每朵花評級，一朵花的級别是它擁有的美麗能超過的花的數量。定義一朵花A比另一朵花B要美麗，當且僅當Sa>=Sb,Ca>=Cb,Ma>=Mb。顯然，兩朵花可能有同樣的屬性。需要統計出評出每個等級的花的數量。
第一行為N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的數量和最大屬性值。
以下N行，每行三個整數si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的屬性
包含N行，分别表示評級為0...N-1的每級花的數量。
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
3
1
1 <= N <= 100,000, 1 <= K <= 200,000
CDQ分治
三維排名，第一維先排序，當做是時間，後兩維鋪在平面上，當做是平面上的修改。
于是原問題可以看成一個按一定順序添加點，然後詢問某時間某個點左下方有多少點的問題。
可用CDQ分治做。
代碼學(chao)自hzwer
注釋掉的代碼看上去思路一樣，但不知道為什麼會WA，姑且放着。
本文為部落客原創文章，轉載請注明出處。