小蓝的好友
题解
貌似很板的一道题
好吧，由于感觉与以前做过的一些题很像，所以就想到了单调栈。
很显然，我们要求的就是所有全白的格子个数。我们对于每一行，用单调栈维护它每一列这行的白格子高度。
然后就很容易计算出它的所有矩形的方案数，一个的算法就诞生了。
可这明显会TLE。
好吧，我们发现对于每新加的一行，若i处有黑格，就把它赋值为0，否则加1吧。这东西明显还可以用平衡树维护。
于是，加上一个平衡树就是了，数据是随机的，不卡单调栈。
源码
很好写
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
#define int LL
#define gc() getchar()
const int MAXN=4e4+5;
template<typename _T>
inline void read(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
int r,c,n;
class Tree{public:int ch[MAXN][2],father[MAXN],root;int val[MAXN],sum[MAXN],siz[MAXN];void pushup(int rt){siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1;sum[rt]=val[rt]*(siz[ch[rt][0]]+1)*(siz[ch[rt][1]]+1);sum[rt]+=sum[ch[rt][0]]+sum[ch[rt][1]];}#define lson ch[mid][0]#define rson ch[mid][1]int build(int l,int r){if(l>r)return 0;if(l==r){siz[l]=1;return l;}int mid=(l+r)>>1;lson=build(l,mid-1);if(lson)father[lson]=mid;rson=build(mid+1,r);if(rson)father[rson]=mid;pushup(mid);return mid;}int identify(int x){return ch[father[x]][1]==x;}void connect(int f,int x,int d){father[x]=f;ch[f][d]=x;} void rotate(int rt){int p=father[rt];int d1=identify(rt);//printf("%d %d %d\n",rt,p,d1);int d2=identify(p);if(root==p)root=rt;connect(p,ch[rt][d1^1],d1);connect(father[p],rt,d2);connect(rt,p,d1^1);pushup(p);pushup(rt);}
}Tree;
pair<int,int> zy[100005];
int ans;
signed main(){read(r);read(c);read(n);for(int i=1;i<=n;i++)read(zy[i].first),read(zy[i].second);sort(zy+1,zy+n+1);Tree.root=Tree.build(1,c);int las=1;Tree.val[0]=r+1;for(int i=1;i<=n;i++){while(las!=zy[i].first)ans+=Tree.sum[Tree.root],las++;int now=zy[i].second;Tree.val[now]=zy[i].first;while(Tree.val[Tree.father[now]]<Tree.val[now])Tree.rotate(now);while(now)Tree.pushup(now),now=Tree.father[now];}while(las<=r)ans+=Tree.sum[Tree.root],las++;printf("%lld\n",ans);return 0;
}