点\((x_1,y_1)\) と点 \((x_2,y_2)\) を両端に持つ長方形を、半開区間の直積 \([x_1,x_2) \times [y_1,y_2)\) と同一視します。 すなわち、 \(x_1 \le x < x_2\) かつ \(y_1 \le y < y_2\) の領域がその長方形に含まれているものとします。

1つの解

\(A[i][j]\) は、\(10002 \times 10002\) 配列であって、座標 \((i, j)\) に長方形が含まれてるとき 1、そうでなければ 0 とします。

面積は \(A[i][j]\) の総和、 周長は \(A[i][j] \ne A[i+1][j]\) となるものの個数と \(A[i][j] \ne A[i][j+1]\) となるものの個数の和です。

\(A[i][j]\) を構築するには、2次元 imos 法を用います。各長方形 \([x_1,x_2) \times [y_1,y_2)\) に対し、次を行います。

• \(A[x_1][y_1] \leftarrow A[x_1][y_1] + 1\)
• \(A[x_1][y_2] \leftarrow A[x_1][y_2] - 1\)
• \(A[x_2][y_1] \leftarrow A[x_2][y_1] - 1\)
• \(A[x_2][y_2] \leftarrow A[x_2][y_2] + 1\)

すべての長方形について加算し終えたあと、2次元累積和を取ります。その後、各要素を \(A[i][j] \leftarrow \min(A[i][j], 1)\) とすれば完成です。

シートの枚数を \(n\) とし、座標の最大値を \(K=10000\) とします。 時間計算量は \(O(n+K^2)\) 、空間計算量は \(O(K^2)\) です。

時間制限には間に合いますが、メモリ制限の 64 MiB に引っかかります。\(\pm 10000\) に耐えられる \(10^8\) の配列を用意するには、16bit 整数を用いても 190 MiB ほど必要です。

より省メモリに（平面走査+1次元 imos 法）

平面走査（イベントソート）を考えます。\(x=0,1,\cdots, 10000\) ごとに個別に1次元のimos法を行うアプローチです。

まず、長さ \(10002\) の \(1\) 次元配列 \(A\) を用意します。初期値はすべて \(0\) です。

各長方形 \([x_1,x_2) \times [y_1,y_2)\) に対し、 \(x=x_1\) を見るときに

• \(A[y_1] \leftarrow A[y_1] + 1\)
• \(A[y_2] \leftarrow A[y_2] - 1\)

、 \(x=x_2\) を見るときに

• \(A[y_1] \leftarrow A[y_1] - 1\)
• \(A[y_2] \leftarrow A[y_2] + 1\)

を加算することを考えます。

\(x\) を見るときに適切に加算を行うために、そのための適切な指示をする配列を用意するとよいです。

各 \(x\) ではそのような加算をすべて行ったあとに累積和を取ります。これを \(S\) とおくことにすると、\(S[y] > 0\) なら \((x,y)\) は長方形に覆われていることわかります。

\(x-1\) での累積和配列 \(S\) も保持すれば周長の計算も行えます。周長の計算のために、 \(y\) 座標の昇順にも平面走査を行います。

この工夫により、全体の時間計算量は \(O(n+K^2)\) を維持したまま、空間計算量は \(O(n+K)\) とかなり抑えられます。

実装（C++, 267 ms, 6852 KiB） https://atcoder.jp/contests/joi2006ho/submissions/78138624