CodeForces528A （STLset）

题面

CodeForces

题解

横着切和竖着切是互相不影响的。

假设现在横着切成了很多段，显然此时面积最大的矩形的一边长就是这些段中长度最长的一段。竖着切的也是一样的。

所以就可以用$set$来维护切过的横、纵坐标与每一段的长度。

修改时，先找到相邻的两刀，再找到对应的长度，删去这个长度，再加入切出来的两个新的长度。

一开始要把$\mathbf W$、$\mathbf H$这些东西加进去。

#include <set>

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::min; using std::max;

using std::sort; using std::swap;

using std::unique; using std::lower_bound;

using std::set;

typedef long long ll;

template<typename T>

void read(T &x) {

    int flag = 1; x = 0; char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int _ = 2e5 + 10;

int W, H, n, w[_], h[_];

int main () {

	read(W), read(H), read(n);

	set<int> sw, sh, qw, qh;

	sw.insert(W), sw.insert(-W);

	sh.insert(H), sh.insert(-H);

	qw.insert(0), qw.insert(W), qw.insert(-W);

	qh.insert(0), qh.insert(H), qh.insert(-H);

	++w[W], ++h[H]; char ch[3]; int x;

	for(int i = 1; i <= n; ++i) {

		scanf("%s%d", ch, &x);

		if(ch[0] == 'H') {

			qh.insert(x), qh.insert(-x);

			int r = *(qh.upper_bound(x));

			int l = -*(qh.upper_bound(-x));

			if(h[r - l]) --h[r - l];

			if(!h[r - l]) sh.erase(r - l), sh.erase(l - r);

			sh.insert(x - l), ++h[x - l];

			sh.insert(r - x), ++h[r - x];

			sh.insert(l - x), sh.insert(x - r);

		} else {

			qw.insert(x), qw.insert(-x);

			int r = *(qw.upper_bound(x));

			int l = -*(qw.upper_bound(-x));

			if(w[r - l]) --w[r - l];

			if(!w[r - l]) sw.erase(r - l), sw.erase(l - r);

			sw.insert(x - l), ++w[x - l];

			sw.insert(r - x), ++w[r - x];

			sw.insert(l - x), sw.insert(x - r);

		}

		set<int>::iterator r1, r2;

		r1 = sh.begin(), r2 = sw.begin();

		printf("%lld\n", (ll)(*r1) * (*r2));

	}

	return 0;

}