洛谷P2611 [ZJOI2012]小蓝的好友

总子矩形个数减去内部没有资源点的子矩形个数即为答案。

考虑枚举子矩形的下边界，从上到下进行扫描。对列建笛卡尔树，其中序遍历为下标，维护堆性质的权值为该列上点的行数最大值。然后在笛卡尔树上的每个节点统计贡献。

扫描时需要支持单点修改权值，那么直接用 (FHQ Treap) 建笛卡尔树即可，因为数据随机，所以复杂度有保证。

#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,m,k,tot,root;
int ls[maxn],rs[maxn],val[maxn],siz[maxn];
ll ans;
ll key[maxn],sum[maxn];
vector<int> ve[maxn];
void pushup(int x)
{
    siz[x]=siz[ls[x]]+siz[rs[x]]+1;
    sum[x]=sum[ls[x]]+sum[rs[x]]+key[x]*(siz[ls[x]]+1)*(siz[rs[x]]+1);
}
void build(int l,int r,int &x)
{
    int mid=(l+r)>>1;
    x=++tot,siz[x]=1,val[x]=mid;
    if(l<mid) build(l,mid-1,ls[x]);
    if(r>mid) build(mid+1,r,rs[x]);
    pushup(x);
}
void merge(int &p,int x,int y)
{
    if(!x||!y)
    {   
        p=x+y;
        return;
    }
    if(key[x]>key[y]) p=x,merge(rs[p],rs[p],y);
    else p=y,merge(ls[p],x,ls[p]);
    pushup(p);
}
void split(int p,int k,int &x,int &y)
{
    if(!p)
    {
        x=y=0;
        return;
    }
    if(val[p]<=k) x=p,split(rs[p],k,rs[p],y);
    else y=p,split(ls[p],k,x,ls[p]);
    pushup(p);
}
void modify(int k,int v)
{
    int x,y,z;
    split(root,k,x,y),split(x,k-1,x,z);
    key[z]=v,pushup(z),merge(x,x,z),merge(root,x,y);
}
int main()
{
    read(n),read(m),read(k),build(1,m,root);
    for(int i=1;i<=k;++i)
    {
        int x,y;
        read(x),read(y),ve[x].push_back(y);
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<ve[i].size();++j) modify(ve[i][j],i);
        ans+=(ll)i*m*(m+1)/2-sum[root];
    }
    printf("%lld",(ll)n*(n+1)/2*m*(m+1)/2-ans);
    return 0;
}