SPOJ - ADAFIELD - Ada and Field - 思维+二分 - Mutual Training for Wannafly Union #7

1.题目描述：

ADAFIELD - Ada and Field

#binary-search  #datastructures

Ada the Ladybug owns a beautiful field where she grows vegetables. She often visits local Farmers Market, where se buys new seeds. Since two types of vegetable can't share same field, she always divide the field, by either vertical or horizontal line (she is very precise, so the width of line is negligible). Since she visits Farmers Market almost every day, she has already made a lot of such lines, so she needs your help with finding out the area of biggest field.

Input

The first line will contain 0 < T ≤ 200, the number of test-cases.

Then T test-cases follow, each beginning with three integers 1 ≤ N,M ≤ 2*109, 1 ≤ Q ≤ 105, top right corner of field (field goes from [0,0] to [N,M]) and number of field divisions.

Afterward Q lines follows:

0 x (0 ≤ x ≤ N), meaning that line was made vertically, on coordinate x

1 y (0 ≤ y ≤ M), meaning that line was made horizontally, on coordinate y

Sum of Q over all test-cases won't exceed 106

Output

Print Q lines, the area of biggest field after each line was made.

Example Input

2
10 10 5
0 5
0 8
1 1
1 9
1 5
10 10 5
0 5
1 4
1 6
1 8
0 5
      

Example Output

50
50
45
40
20
50
30
20
20
20
      

 Submit solution!

2.题意概述：

有一片菜地，有q次操作，

0 x (0 ≤ x ≤ N), 意味着划分在坐标为 x 的位置上垂直划分一条线

1 y (0 ≤ y ≤ M), 意味着划分在坐标为 y 的位置上垂直划分一条线

每次操作后要你输出菜地被这些线划分以后的最大子矩形面积

3.解题思路：

有见到300ms的和800ms离线做法，大概思路是先把所有数据读入，再一条条拆线，每拆一次维护一次最大值，最后倒着输出。

我的思路很朴素，用set维护一下当前x的线和y的线的坐标用lower_bound维护一下当前坐标左边和右边的位置，greater的map维护一下当前x(y)轴的最大值，结果就是当前x轴的最大连续长度和y的最大连续长度乘积，注意long long就行。

我还想到一种思路，类似于二维的POJ2559实际上划线就相当于矩形化边，然后维护最大矩形面积。

4.AC代码：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 100100
#define N 1111
#define eps 1e-6
#define pi acos(-1.0)
#define e exp(1.0)
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	long _begin_time = clock();
#endif
	int t, n, m, q;
	scanf("%d", &t);
	while (t--)
	{
		set<int> s[2];
		map<int, int, greater<int> > mp[2];
		scanf("%d%d%d", &n, &m, &q);
		mp[0][n] = 1;
		mp[1][m] = 1;
		s[0].insert(0);
		s[0].insert(n);
		s[1].insert(0);
		s[1].insert(m);
		int pos[2] = { n, m };
		while (q--)
		{
			int dir, num;
			scanf("%d%d", &dir, &num);
			if (!s[dir].count(num))
			{
				s[dir].insert(num);
				set<int>::iterator mid = s[dir].lower_bound(num);
				set<int>::iterator l = mid, r = mid;
				if (mid != s[dir].begin())
					l--;
				if (mid != s[dir].end())
					r++;
				mp[dir][*mid - *l]++;
				mp[dir][*r - *mid]++;
				mp[dir][*r - *l]--;
				if (mp[dir][*r - *l] == 0)
					mp[dir].erase(*r - *l);
				pos[dir] = mp[dir].begin()->first;
			}
			printf("%lld\n", 1LL * pos[0] * pos[1]);
		}
	}
#ifndef ONLINE_JUDGE
	long _end_time = clock();
	printf("time = %ld ms.", _end_time - _begin_time);
#endif
	return 0;
}