http://codeforces.com/problemset/problem/527/C
这题总体思路就是，每画一条线，然后就找到x间距的最max值和y间距的最max值，相乘就是当前的ans
那么我需要维护这样的一个数列，每次往里面添加一个元素，然后查询相邻两个元素的差值的最大值。
倒着做比较简单，首先把所有元素插上去，然后最大值直接暴力算一次。然后后来只有删除操作，这个操作只会让最大值变大。
每次删除后，检查上面和下面的新间距，和最大值比较一下就好。
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; set<int> ss[2]; LL ans[200000 + 20]; struct Node { char op; int val; }node[200000 + 20]; void fuck(int id) { if (node[id].op == ‘H‘) { ss[1].erase(node[id].val); } else ss[0].erase(node[id].val); } void work() { int w, h, n; cin >> w >> h >> n; ss[0].insert(0); ss[0].insert(w); ss[1].insert(0); ss[1].insert(h); set<int> :: iterator it1, it2; for (int i = 1; i <= n; ++i) { char str[2]; int val, flag = false; scanf("%s%d", str, &val); if (str[0] == ‘H‘) { ss[1].insert(val); } else ss[0].insert(val); node[i].op = str[0]; node[i].val = val; } int mx1 = 1; // v it2 = ss[0].begin(); it2++; for (it1 = ss[0].begin(); it2 != ss[0].end(); ++it2, ++it1) { mx1 = max(mx1, *it2 - *it1); } int mx2 = -inf; it2 = ss[1].begin(); it2++; for (it1 = ss[1].begin(); it2 != ss[1].end(); ++it2, ++it1) { mx2 = max(mx2, *it2 - *it1); } ans[n] = 1LL * mx1 * mx2; // cout << mx1 << " " << mx2 << endl; fuck(n); mx1 = 1; // v it2 = ss[0].begin(); it2++; for (it1 = ss[0].begin(); it2 != ss[0].end(); ++it2, ++it1) { mx1 = max(mx1, *it2 - *it1); } mx2 = 1; it2 = ss[1].begin(); it2++; for (it1 = ss[1].begin(); it2 != ss[1].end(); ++it2, ++it1) { mx2 = max(mx2, *it2 - *it1); } for (int i = n - 1; i >= 1; --i) { if (node[i].op == ‘H‘) { it1 = ss[1].lower_bound(node[i].val); it2 = it1; it2++; mx2 = max(mx2, *it2 - *it1); it2 = it1; it1--; mx2 = max(mx2, *it2 - *it1); it1++; } else { it1 = ss[0].lower_bound(node[i].val); it2 = it1; it2++; mx1 = max(mx1, *it2 - *it1); it2 = it1; it1--; mx1 = max(mx1, *it2 - *it1); it1++; } it2 = it1; it2++; it1--; fuck(i); ans[i] = 1LL * mx1 * mx2; if (node[i].op == ‘H‘) { mx2 = max(mx2, *it2 - *it1); } else mx1 = max(mx1, *it2 - *it1); } for (int i = 1; i <= n; ++i) { cout << ans[i] << endl; } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
写的很乱，因为是绝杀的。
正着也可以。
用一个multiset来维护当前拥有的差值，一开始是h
然后每添加一条边，可以找出在原数组中的上界和下界，这个差值是要删除的那个差值，然后添加新差值即可。
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; set<int> x, y; multiset<int> xx, yy; void work() { int w, h, n; cin >> w >> h >> n; x.insert(0), x.insert(w); y.insert(0), y.insert(h); xx.insert(w), yy.insert(h); for (int i = 1; i <= n; ++i) { char str[2]; int pos; cin >> str >> pos; if (str[0] == ‘H‘) { auto it1 = y.lower_bound(pos); int d1 = *it1; it1--; int d2 = *it1; auto del = yy.lower_bound(d1 - d2); yy.erase(del); yy.insert(d1 - pos); yy.insert(pos - d2); y.insert(pos); } else { auto it1 = x.lower_bound(pos); int d1 = *it1; it1--; int d2 = *it1; auto del = xx.lower_bound(d1 - d2); xx.erase(del); xx.insert(d1 - pos); xx.insert(pos - d2); x.insert(pos); } auto itx = xx.rbegin(), ity = yy.rbegin(); cout << 1LL * (*itx) * (*ity) << endl; } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif IOS; work(); return 0; }
原文：http://www.cnblogs.com/liuweimingcprogram/p/7222972.html
