在其他题解中获得了许多教益，终于看懂了这题，于是写一些其他题解中认为过于基础而略去的细节来帮助像我这样的萌新。

感谢奆佬和奆佬。

首先是这题的题意转化：在所有子矩形中找到不包含给出的任何一个特殊点且周长最大的一个，输出其周长。

这题的 $n^2$ 做法是较为容易理解的：

我们一定有一种构造方案，使得答案为 $2 \times (\max(w,h)+1)$ ，具体就是长为 $\max(w,h)$，宽为 $1$ 的细长条。

于是最优的答案矩形周长不小于这个值，那么它不可能龟缩在整个大矩形的某个四分之一的角里。

于是它一定至少经过横坐标的中位线，或纵坐标的中位线。

我们讨论这两种情况，答案取 $\max$ 即可。这里不妨只讨论经过纵坐标中位线的情况。

我们在所有的点中取两个点来限定子矩形的左右边界，设为 $i,j$ ，不妨设 $i < j$。

当 $j=i+1$ 时，这两个点相邻，那么中间没有上下界的限制，可以顶满，答案就是 $2 \times (x_j - x_i + h)$。

否则这两个点中间还有其他点，由于这两个点被钦定为左右边界，其他点就只能做横向的分割。并且这里我们讨论的是越过纵坐标中位线的方法，于是可以知道纵坐标在中位线以上的点，我们将它的上半部分染成黑色，否则将它的下半部分染成黑色。

那么对于左右边界 $i,j$ ，我们的答案就应该是 $2 \times (x_j - x_i + \min_{i < k < j,2 \times y_k > h}y_k - \max_{i < k < j,2 \times y_k < h}y_k)$。

于是我们枚举左右端点，枚举同时处理这个上下边界，容易得到一个 $O(n^2)$ 的做法。

然后考虑如何优化这个做法。

我们考虑对于一个右边界，如何选择其左边界。

观察上边统计答案的式子，我们发现我们可以把左边界抽象成一个横坐标为 $i$,纵坐标为 $\max_{i < k < j,2 \times y_k < h}y_k) \sim \min_{i < k < j,2 \times y_k > h}y_k$ 的线段。

考察这个线段的变化趋势，发现随着 $i$ 单调递增，线段的上端点单调升高，下端点单调降低。于是我们可以使用一个单调栈来维护其上下端点的变化。

然后发现这时的答案就是 $2 \times \max(x_j - x_i + len_i)$，其中 $len_i$ 表示在第 $i$ 个特殊点位置的左边界线段。

$x_j$ 的取值是不变的，于是我们只需要维护 $len_i - x_i$ 的最大值，于是可以进行简单的线段树维护区间最大值，要求能进行区间加，原因是统计 $len_i$ 时我们选择先对这一段区间加上上端点，再减去下端点，这样可以更为简便地处理上下端点。

到这里就说完了整道题的思路，但是实现时的一些细节却不便于口述，于是放在代码注释中。

代码本来放在云剪贴板，但是自己博客里还是直接放源码罢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long ll;
#define N 300010
#define inf 0x3f3f3f3f
int w,h,n;
int ans = -inf;
struct node{
    int x,y;
    friend bool operator < (node a,node b)
    {return a.x < b.x;}
}a[N];

struct Tree{
    int maxx,lz;
}t[N << 2];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

void push_up(int x);
void push_down(int x);
void add(int x,int l,int r,int ql,int qr,int k);
int query(int x,int l,int r,int ql,int qr);
void calc();

void main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> w >> h >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i].x >> a[i].y;
    }
    a[n+1].x = w,a[n+1].y = h; // 在最后加入上界，否则会忽略最后一段的贡献（可参照下文理解
    calc();
    swap(w,h); // 交换横纵坐标，处理经过横轴中位线的情况。
    for(int i = 1;i <= n+1;i++) swap(a[i].x,a[i].y);
    calc();
    cout << (ans << 1);
    return;
}

struct flo{
    int pos,high;
    flo(int _p,int _h) : pos(_p),high(_h){}
};
stack<flo> up,down;

inline void upins(int x,int h)
{
    while(up.size() > 1 && up.top().high > h) 
    // 要求size>1，因为这次修改涉及的区间是上一个端点到这一个端点之间的区间。
    // 为什么修改区间是这样可以参照左端点线段的定义理解，下文同理。
    {
        auto x = up.top();up.pop();
        add(1,0,n,up.top().pos,x.pos-1,-x.high);
    }
    add(1,0,n,up.top().pos,x-1,h);
    up.emplace(x,h);
}

inline void dwins(int x,int h)
{
    while(down.size() > 1 && down.top().high < h) 
    {
        auto x = down.top();down.pop();
        add(1,0,n,down.top().pos,x.pos-1,x.high);
    }
    add(1,0,n,down.top().pos,x-1,-h);
    down.emplace(x,h);
}

inline void calc()
{
    memset(t,0,sizeof(t));
    while(up.size()) up.pop();
    while(down.size()) down.pop();
    up.emplace(0,0);
    down.emplace(0,0);
    // 加入起始点，否则会忽略第一段的贡献。
    sort(a+1,a+n+1);
    for(int i = 1;i <= n+1;i++)
    {
        // 这里枚举第i个点作为右端点，所以把第i-1个点插入到线段树和单调栈中，考虑了其作为左端点的情况。
        if((a[i-1].y << 1) < h) // down
        {
            upins(i-1,h);
            // 这里插入h的做法可以认为是防止未更新的部分影响答案更新，也可参照lTgMFePRoeZ的题解理解。
            dwins(i-1,a[i-1].y);
        }
        else // up
        {
            upins(i-1,a[i-1].y);
            dwins(i-1,0);
            // 这里插入0的目的同上边插入h
        }
        add(1,0,n,i-1,i-1,-a[i-1].x);
        ans = max(ans,a[i].x - a[i-1].x + h);
        // 左右端点相邻。
        ans = max(ans,query(1,0,n,1,i-2) + a[i].x);
        // 左右端点不相邻，由题解原文式子可得这里的转移。
    }
}

int query(int x,int l,int r,int ql,int qr)
{
    if(l > r || ql > qr) return -inf;
    if(l >= ql && r <= qr) return t[x].maxx;
    int ans = -inf;
    push_down(x);
    int mid = (l + r) >> 1;
    if(mid >= ql) ans = max(ans,query(ls(x),l,mid,ql,qr));
    if(mid < qr) ans = max(ans,query(rs(x),mid+1,r,ql,qr));
    return ans;
}

void add(int x,int l,int r,int ql,int qr,int k)
{
    if(l > r || ql > qr) return;
    if(l >= ql && r <= qr)
    {
        t[x].maxx += k;
        t[x].lz += k;
        return;
    }
    int mid = (l + r) >> 1;
    push_down(x);
    if(mid >= ql) add(ls(x),l,mid,ql,qr,k);
    if(mid < qr) add(rs(x),mid+1,r,ql,qr,k);
    push_up(x);
    return;
}

inline void push_down(int x)
{
    if(!t[x].lz) return;
    t[ls(x)].maxx += t[x].lz;
    t[rs(x)].maxx += t[x].lz;
    t[ls(x)].lz += t[x].lz;
    t[rs(x)].lz += t[x].lz;
    t[x].lz = 0;
    return;
}

inline void push_up(int x)
{
    t[x].maxx = max(t[ls(x)].maxx,t[rs(x)].maxx);
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}