前言：

   上来一看，这不是要先$C\times R$处理一下吗，于是看到了数据范围

   遍历一遍都不让怎么瞎搞。。。不过N是100000+随机数据emmm

感谢写出让我看得懂得题解的xyz32768

以及我的博客传送门

题解：

   统计有一个资源点的矩形个数，感觉一时半会推不出公式。于是了解了补集转换，就是用所有矩形个数减去没有资源点的个数，貌似有点像Vijos 1225 月饼盒，不过还是不好想。先看怎么统计所有矩形的个数：因为矩形是由线段×线段得到的，所以用横线段个数乘上纵线段个数，就是矩形个数。长度为1的横线段有$C$条，长度为2的横线段有$C-1$条，……，长度为$C$的线段有1条，同理长度为1的纵线段有$R$条等等。因此横线段的个数为$\frac{C(C+1)}2$，纵线段的个数为$\frac{R(R+1)}2$，相乘就得到了$\frac{C(C+1)R(R+1)}4$个矩形，乘开之后，发现要开long long（不开long long 是有10分的）。

   这个题要推导的数学公式很多，因为我们仍然要计算空矩形个数。

   接着看怎么统计空矩形个数，根据样例，第一行是这样的（O表示空点，X表示有资源）

OXOOO

   图中共有7个空矩形，左边的一个O贡献了1个，右边的3个O贡献了6个。计算方式就是对每一个纵向连续最长的O，用它及它左边连续纵向 不比它短 的O的个数乘上它及它右边连续纵向比它长的O的个数，就不会冲突了。也就是1×1+1×1+2×1+3×1=7。那如果矩形的宽大于1怎么处理？一样地，我们仍然可以这样计算，举个例子：

OXOOO
OOXOO

   对于第二行最左边一个O，如果我们同样计算，它所贡献的矩形有2(高度)×1(左边)×1(右边)=2个（以此类推纵向高度为k的矩形新贡献的矩形有k个），第二个O贡献了1×2×1=2个，第四个O贡献了2×1×1=2个，第五个贡献了2×2×1=4个。则第二行一共有8个空矩形。

   如何维护并尽快计算这个结果呢？因为数据随机，对于第i列到此连续O的个数，用t[i]来表示，把i的序号用Treap维护（随机时Treap的深度有保证），再用t[i]来维护Treap。在Treap上，有BST的性质，所以与某个位置相邻的且比它短的点，都在它的左右孩子处；因为每向下扩展一行就会使很多个t[i]自增1，所以我们维护t[i]保存的是第i列以当前行位置从下往上数第一个X在哪一行，每次处理用当前行数减去t[i]就是新贡献矩形个数。那么这样我们按t[i]维护一个大根堆，这样一来，上面的连续纵向比它长的就分别是左右孩子的数量+1了。新增矩形个数$=(sz[ls]+1)(sz[rs]+1)$，Treap每次旋转也要维护这个值。

   构建Treap：一开始所有点的权值都为0，我们直接按照BST构建就可以了，每次取中点，左右区间作为左右孩子，递归建树。

   Treap里要存$t[i]×(sz[i_{ls}]+1)(sz[i_{rs}]+1)$、子树中这个数据的和以及基础的BST信息。因为没学过Treap，我的Treap是按splay风格写的，不要太介意。

平衡树多maintain总没有错。

   时间复杂度：$O(C+R+N\log C)$

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid (l+r>>1)
int r,c,n;
struct node
{
    int key,v;//关键字 维护值
    long long sz,ans,anstt;//子树大小 乘积(v与sz) 乘积之和 v之和
    long long sztt;
    node *s[2];
    node(int key,int v)
    {
        this->key=key;
        this->v=v;
        sz=1;
        sztt=1;
        ans=0;
        anstt=0;
        s[0]=NULL;
        s[1]=NULL;
    }
    node()
    {
        v=0;
        sz=1;
        sztt=1;
        ans=1;
        anstt=0;
        s[0]=NULL;
        s[1]=NULL;
    }
    long long getsz()//访问节点大小
    {
        if(!this)
            return 0;
        return sz;
    }
    long long getsztt()
    {
        if(!this)
            return 0;
        return sztt;
    }
    long long getanstt()
    {
        if(!this)
            return 0;
        return anstt;
    }
    long long getd(int x)//询问方向
    {
        if(x==key)
            return -1;
        return x>key;
    }
    long long getv()//访问维护值
    {
        if(!this)
            return -1;
        return v;
    }
    void maintain()
    {
        sz=s[0]->getsz()+s[1]->getsz()+1;
        sztt=(s[0]->getsz()+1)*(s[1]->getsz()+1)+s[0]->getsztt()+s[1]->getsztt();
        ans=v*(s[0]->getsz()+1)*(s[1]->getsz()+1);
        anstt=ans+s[0]->getanstt()+s[1]->getanstt();
    }
}*root=NULL;
void build(node *&rt,int l,int r)
{
    rt=new node(mid,0);
    if(l==r)
        return;
    if(mid>l)
        build(rt->s[0],l,mid-1);
    if(mid<r)
        build(rt->s[1],mid+1,r);
    rt->maintain();
    return;
}
void Rotate(node *&rt,int d)
{
    node *tmp=rt->s[d];
    rt->s[d]=tmp->s[d^1];
    tmp->s[d^1]=rt;
    rt->maintain();
    rt=tmp;
    rt->maintain();
    return;
}
void treap(node *&rt)
{
    //大根堆
    if(rt->v>rt->s[0]->getv()&&rt->v>rt->s[1]->getv())
        return;
    if(rt->s[0]->getv()>rt->s[1]->getv())//把左孩子拉上来
    {
        Rotate(rt,0);
        treap(rt->s[1]);
    }
    else
    {
        Rotate(rt,1);
        treap(rt->s[0]);
    }
    rt->maintain();
}
void change(node *&rt,int t,int x)//把t改为x
{
    int d=rt->getd(t);
    if(d==-1)
    {
        rt->v=x;//可能有问题
        rt->maintain();
        treap(rt);
        rt->maintain();
        return;
    }
    change(rt->s[d],t,x);
    treap(rt);
    rt->maintain();
}
struct pnt
{
    int x,y;//行 列数
    friend bool operator <(pnt a,pnt b)
    {
        if(a.x!=b.x)
            return a.x<b.x;
        return a.y<b.y;
    }
}p[101000];
int main()
{
    scanf("%d%d%d",&r,&c,&n);//r行c列
    build(root,1,c);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    std::sort(p+1,p+1+n);
    int cur=1;
    long long sum=(long long)((r+1)*r/2)*((c+1)*c/2);
    for(int i=1;i<=r;i++)
    {
        while(p[cur].x==i)
        {
            change(root,p[cur].y,i);
            cur++;
        }
        sum-=i*(root->sztt)-root->anstt;
    }
    printf("%lld\n",sum);
    return 0;
}