CF 527C Glass Carving

数据结构维护二维平面

首先横着切与竖着切是完全没有关联的，

简单贪心，最大子矩阵的面积一定是最大长*最大宽

此处有三种做法

1.用set来维护，每次插入操作寻找这个点的前驱和后继，并维护一个计数数组，来维护最大值

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstring>

#include <set>

using namespace std;

const int MAXN = 400005;

int init() {

	int rv = 0, fh = 1;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') fh = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		rv = (rv<<1) + (rv<<3) + c - '0';

		c = getchar();

	}

	return fh * rv;

}

int w, h, n, maw, mah, cnt1[MAXN], cnt2[MAXN];

set <int> s1, s2;

set <int> :: iterator u, v;

int main() {

	freopen("in.txt", "r", stdin);

	w = init(); h = init(); n = init();

	mah = h; maw = w;

	cnt1[mah]++; cnt2[maw]++;

	s1.insert(h);s2.insert(0);s2.insert(w);s1.insert(0); //要提前把这两个点加上

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

		char c;

		scanf(" %c ", &c);

		int t = init();

		if(c == 'H'){

			s1.insert(t);

			u = v =s1.find(t);

			u--; v++;

			cnt1[*v - *u]--;

			cnt1[*v - t]++; cnt1[t - *u]++;

			while(!cnt1[mah]) mah--;   //此处因为mah是不增的，所以这个操作的总复杂度是O(h)

		}else {

			s2.insert(t);

			u = v =s2.find(t);

			u--; v++;

			cnt2[*v - *u]--;

			cnt2[*v - t]++; cnt2[t - *u]++;

			while(!cnt2[maw]) maw--;

		}

		printf("%lld\n", (long long)maw * mah);

	}

	fclose(stdin);

	return 0;

}

平衡树，与set类似
线段树，用 \(01\) 序列表示某条边哪里被切割，本题就变成了维护最长连续0

区间需要维护：区间左右开始连续0的长度，区间最长连续0的长度，区间是否全为0

巴特西

CF 527C Glass Carving

数据结构维护二维平面

最新文章

热门文章