因为这题考虑可以观察一个性质,答案的下界为 \(2×(max(w,h) 1)\), 因为你至少可以空出一行或一列,因此这个矩形一定会经过 \(x=\frac{w}{2}\) 或 \(y=\frac{h}{2}\) . 先考虑经过 \(\frac{w}{2}\) 的情况 , 另一种情况是一样的.
先将坐标离散化.枚举矩形的上边界 \(yR\) ,对于每一个下边界 \(yL\) , 我们可以计算出矩形的最优左边界 \(xL=min\{Xi|Yi\in[yL,yR],Xi>\frac{w}{2}\}\) , 以 及 右 边 界 \(xR=max\{Xi|Yi\in[yL,yR],Xi≤\frac{w}{2}\}\) ,
此时可以找到一个周长为 \(2×(xR−xL yR−yL)\) 的矩形.
直接做是 \(O(n^2)\) 的,但该算法可以用线段树优化,在将上边界往上移的过程中动态维护每
个位置的 xL,xR,并维护全局最小值,不难发现只需要左右各开一个单调栈,在更新单调栈
时在线段树树上进行区间加减即可. O(nlogn) .
这其实就是一个计算极大subrectangle的过程, 因为知道中间边界, 基本原理来自于暴力, 就是简单的枚举长度, 更新宽度. 其实这题也很套路, 发现这题的边界是不断移动的, 在移动的时候会产生一部分的重复信息, 所以考虑采用数据结构维护, 分析一下颓余状态, 发现可以单调栈优化.
#include<bits/stdc .h>using namespace std;#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; i)#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)#define clar(a, b) memset((a), (b), sizeof(a))#define debug(...) fprintf(stderr, __VA_ARGS__)typedef long long LL;typedef long double LD;int read() { char ch = getchar(); int x = 0, flag = 1; for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1; for (;isdigit(ch); ch = getchar()) x = x * 10 ch - 48; return x * flag;}void write(int x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) write(x / 10); putchar(x % 10 48);} const int Maxn = 3e5 9;struct Point { int x, y; int operator < (const Point &a) const { return x < a.x; }}s[Maxn];int n, ans, h, w; void init() { w = read(), h = read(); n = read(); rep (i, 1, n) s[i].x = read(), s[i].y = read(); s[ n] = (Point){0, 0}; s[ n] = (Point){w, h};} pair<int, int> stkA[Maxn], stkB[Maxn]; int topa, topb; struct SGMTtree { int tree[Maxn << 2], add[Maxn << 2];#define lc(x) ((x) << 1)#define rc(x) ((x) << 1 | 1)#define ls rt << 1, l, mid#define rs rt << 1 | 1, mid 1, r void clear() { clar(tree, 0), clar(add, 0); } void pushup(int rt) { tree[rt] = max(tree[lc(rt)], tree[rc(rt)]); } void pushdown(int rt) { if (add[rt]) { add[lc(rt)] = add[rt]; add[rc(rt)] = add[rt]; tree[lc(rt)] = add[rt]; tree[rc(rt)] = add[rt]; add[rt] = 0; } } void modify(int rt, int l, int r, int p, int q, int v) { if (p <= l && r <= q) { add[rt] = v; tree[rt] = v; return ; } int mid = (l r) >> 1; pushdown(rt); if (q <= mid) modify(ls, p, q, v); else if (p >= mid 1) modify(rs, p, q, v); else modify(ls, p, q, v), modify(rs, p, q, v); pushup(rt); }#undef lc#undef rc#undef ls#undef rs}st; void ZhaoQingFei() { sort(s 1, s n 1); st.clear(); topa = topb = 0; rep (i, 1, n) { int Nxt = i - 1; if (s[i].y <= h / 2) { while (topa && stkA[topa].second <= s[i].y) { st.modify(1, 1, n, stkA[topa].first, Nxt, stkA[topa].second - s[i].y); Nxt = stkA[topa].first - 1; --topa; } if (Nxt != i - 1) stkA[ topa] = make_pair(Nxt 1, s[i].y); } else { while (topb && stkB[topb].second >= s[i].y) { st.modify(1, 1, n, stkB[topb].first, Nxt, s[i].y - stkB[topb].second); Nxt = stkB[topb].first - 1; --topb; } if (Nxt != i - 1) stkB[ topb] = make_pair(Nxt 1, s[i].y); } stkA[ topa] = make_pair(i, 0); stkB[ topb] = make_pair(i, h); st.modify(1, 1, n, i, i, h - s[i].x); ans = max(ans, s[i 1].x st.tree[1]); }} void solve() { ZhaoQingFei(); rep (i, 1, n) swap(s[i].x, s[i].y); swap(h, w); ZhaoQingFei(); cout << ans * 2 << endl;} int main() {// freopen("ARC047B.in", "r", stdin);// freopen("ARC047B.out", "w", stdout); init(); solve(); #ifdef Qrsikno debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);#endif return 0;}更新防死
联系客服
