IOI 2004 Artemis

O(N²) 時間可過! 但 memory 就唔得
做法也是用 inclusive-exclusive, 問題係點樣唔用 O(N²) memory 去 implement

先把點 sort by x
之後由左至右咁做, fix i for j, 每次都係 compute s[x_j][y_j]+s[x_i][y_i]-s[x_i][y_j]-s[x_j][y_i] 之類,
發現除了 s[x_j][y_j] 和 s[x_i][y_i], 其實都只係 depend on x_i, y_i

所以只要把和 i 有關的 2N 個「關鍵點」(共N²個「關鍵點」)計出, 即 s[x_i][*], s[*][y_i], 便可把 memory 降至 linear