有一点难度，但不多。
题意
一个 \(H \times W\) 的地图上有 \(M\) 个障碍物。
有一辆车在 \((1,1)\)，一次行动可以向下或向右移动任意格（不得穿过障碍物）。
求这辆车在最多两次行动中可能到达多少个格子。
分析
车有四种选择：向右、向下、先向右再向下、先向下再向右。
然后设 \(h_i\) 表示第 \(i\) 行最右边可以到达的列，\(l_j\) 表示第 \(j\) 列最下边可以到达的行。
很显然总答案为 \(\sum\limits_{i=1}^{h_1}l_i + \sum\limits_{i=1}^{l_1}h_i - \text{重复计算的部分}\)，接下来难点就在于如何计算重复的部分。
考虑对于每一列 \(i \in [1,h_1]\)，被重复计算的就等于 \(\sum\limits_{j=1}^{\min(l_1,l_i)}[h_j \ge i]\)。
直接计算的复杂度是 \(O(HW)\)，无法接受。
题解区中 Lyccrius 大佬的题解使用了权值线段树，但是显然我不会，考虑换一种想法。
对于每个查询区间的左端点都是固定的，只需要让右端点单调不减，再用一个大小为 \(W\) 的树状数组记录出现次数即可，均摊单次复杂度 \(O(\log W)\)。
总体时间复杂度 \(O(W \log W)\)，可以通过此题。
代码
//the code is from chenjh
#include<cstdio>
#include<cstring>
#define NDEBUG
#include<cassert>
#include<algorithm>
#define MAXN 200005
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
template<typename T>
struct fenwick_tree{//树状数组模板。
public:
fenwick_tree(int _SIZE=0):SIZE(_SIZE){dt=new T[SIZE+1]();memset(dt,0,sizeof(T)*(SIZE+1));}
fenwick_tree(const fenwick_tree& y):SIZE(y.size()),dt(new T[y.size()+1]){memcpy(dt,y.get_dt(),sizeof(T)*(SIZE+1));}
~fenwick_tree(){delete[] dt;}
const T&operator [] (const int&x)const{assert(0<x&&x<=SIZE);return dt[x];}
fenwick_tree&operator = (const fenwick_tree&y){if(this!=&y){SIZE=y.size();T*new_dt=new T[SIZE+1]();memcpy(new_dt,y.get_dt(),sizeof(T)*(SIZE+1));delete[] dt;dt=new_dt;}return *this;}
inline void resize(int _SIZE){T*new_dt =new T[_SIZE+1]();memcpy(new_dt,dt,sizeof(T)*((SIZE<_SIZE?SIZE:_SIZE)+1));delete[] dt;dt=new_dt,SIZE=_SIZE; }
inline void clear(){SIZE=0;delete[] dt;dt=new T[SIZE+1]();memset(dt,0,sizeof(T)*(SIZE+1));}
inline int size()const{return SIZE;}
inline T* get_dt()const{return dt;}
inline void add(int x,const T&v){assert(0<x&&x<=SIZE);for(;x<=SIZE;x+=x&-x)dt[x]+=v;}
inline T sum(const int&l,const int&r)const{assert(0<l&&l<=r&&r<=SIZE);return sum(r)-sum(l-1);}
private:
T*dt=nullptr;
int SIZE;
inline T sum(int x)const{assert(0<=x&&x<=SIZE);T ret(0);for(;x;x^=x&-x)ret+=dt[x];return ret;}
};
int n,m,t;
int h[MAXN],l[MAXN];//同题解中的描述。
PII q[MAXN];//查询区间。
int main(){
scanf("%d%d%d",&n,&m,&t);
fill_n(h+1,n,m),fill_n(l+1,m,n);//记得初始化最远的边界。
for(int x,y;t--;) scanf("%d%d",&x,&y),h[x]=min(h[x],y-1),l[y]=min(l[y],x-1);//注意需要减一，因为是可以到达的。
LL ans=0;
for(int i=1;i<=h[1];i++) ans+=l[i],q[i]=make_pair(min(l[1],l[i]),i);
for(int i=1;i<=l[1];i++) ans+=h[i];
sort(q+1,q+h[1]+1);//按照右端点从小到大排序。
static fenwick_tree<int> T(m);
for(int i=1,j=1;i<=h[1];i++){
for(;j<=q[i].first;j++)T.add(h[j],1);//扩展查询区间。
ans-=T.sum(q[i].second,m);
}
printf("%lld\n",ans);
return 0;
}