Cells Not Under Attack [Codeforces 364 : Div2 B]

問題

http://codeforces.com/contest/701/problem/B

n×nのチェス盤がある。
ここに m 個のルークを置く。
ルークは縦横を攻撃できる。
ルークが1個目から順番に置かれていく。
ルークが1個目からi個目まで置かれたとき、盤面の中で攻撃されないマスをそれぞれ数えて答えよ。

1 <= n <= 10^5
1 <= m <= min(10^5,n^2)

考察

1. 盤面があり、1回のクエリで縦横が使えなくなる系はよくある
2. ルークを置くと横縦の長さが1だけ減る
3. 例

....    x...                    Rxxx
.... -> Rxxx --"."をまとめる--> x...
....    x...                    x...
....    x...                    x...

まとめると話がややこしくなる気もしますが、とにかくルークを置くことで、4×4が3×3と同等になるってことです
4. 長さが減らない時もあって、すでに他のルークによって減らされた列であれば、減りません
5. なので、今までのルークによって消された行・列をsetあたりで保存して、その分だけ縦・横を消してやればいい

実装

http://codeforces.com/contest/701/submission/19330206

typedef long long ll;
ll n, m;
//-----------------------------------------------------------------
int main()
{
	scanf("%d %d", &n, &m);
	set<int> xx, yy;

	rep(i, 0, m) {
		int x, y; scanf("%d %d", &x, &y);
		xx.insert(x);
		yy.insert(y);

		ll ans = (ll)(n - xx.size()) * (ll)(n - yy.size());

		printf("%I64d ", ans);
	}
	printf("\n");
}