题目概述

有一个 $R\times C$ 的网格，其中 $n$ 个格子有资源点，问至少有一个资源点的子网格个数。

解题报告

万年神坑。先补集转化，那么就是用总方案数减去一个资源点都没有的子网格个数，把资源点当成障碍，考虑扫描线。

维护每一列往上扩展的最远个数 $H_i$ ，以这一行为底的子网格个数就是从最小的 $H_i$ 开始，增大 $H_i$ 进行统计，每次增大 $H_i$ 就会让列分成两半（因为不能跨过原先的最小值）。假设上一次的最小值是 $last$ ，如果分成的块有 $si$ 列，并且均 $\ge H_i$ ，那么得到的贡献就是 ${si\choose2}(H_i-last)$ 。

可以发现这个过程实际上就是一棵列号为建值，$H_i$ 为堆值的笛卡尔树分割成两棵子树的过程，用Treap维护笛卡尔树，由于资源点随机所以树高是期望 $O(log_2n)$ 的。

示例程序

我怎么又双叒叕没return mid;啊……

#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
const int maxr=40000;

int n,R,C;vector<int> a[maxr+5];LL sum,ans;
int ro,son[maxr+5][2],fa[maxr+5],H[maxr+5],si[maxr+5],tag[maxr+5];

inline void Pushup(int p) {si[p]=si[son[p][0]]+1+si[son[p][1]];}
int Build(int L,int R,int pre=0){
    if (L>R) return 0;int mid=L+(R-L>>1);fa[mid]=pre;
    son[mid][0]=Build(L,mid-1,mid);son[mid][1]=Build(mid+1,R,mid);Pushup(mid);return mid;
}
inline void Addtag(int p,int k) {if (!p) return;H[p]+=k;tag[p]+=k;}
inline void Pushdown(int p) {if (tag[p]) Addtag(son[p][0],tag[p]),Addtag(son[p][1],tag[p]),tag[p]=0;}
inline LL val(int p) {if (!p) return 0;return ((LL)si[p]*(si[p]+1)>>1)*(H[p]-H[fa[p]]);}
inline void Dec(int p) {sum-=val(p)+val(son[p][0])+val(son[p][1]);}
inline void Inc(int p) {sum+=val(p)+val(son[p][0])+val(son[p][1]);}
#define Son(p) ((p)==son[fa[p]][1])
inline void Rotate(int t){
    int p=fa[t],d=Son(t);Dec(p);Dec(t);sum+=val(t);son[p][d]=son[t][d^1];son[t][d^1]=p;
    if (fa[p]) son[fa[p]][Son(p)]=t; else ro=t;Pushup(p);Pushup(t);
    if (son[p][d]) fa[son[p][d]]=p;fa[t]=fa[p];fa[p]=t;Inc(p);Inc(t);sum-=val(p);
}
inline void Clear(int p){
    static int top,stk[maxr+5];stk[top=1]=p;for (int i=fa[p];i;i=fa[i]) stk[++top]=i;
    while (top) Pushdown(stk[top--]);Dec(p);H[p]=0;Inc(p);while (fa[p]&&H[p]<H[fa[p]]) Rotate(p);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&R,&C,&n);for (int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),a[x].push_back(y);ro=Build(1,C);
    for (int i=1;i<=R;i++){
        sum-=val(ro);Addtag(ro,1);sum+=val(ro);
        for (int j=0,si=a[i].size();j<si;j++) Clear(a[i][j]);ans+=sum;
    }return printf("%lld\n",(((LL)R*(R+1)>>1)*((LL)C*(C+1)>>1))-ans),0;
}