P2611 Solution

流水行船CCD · 2024-01-02 21:52:24 · 题解

其他题解的思路都有点看不懂，而且很多图片崩了，来发一发蒟蒻认为比较清晰的思路。

Part1 基本框架

求至少有一个点的矩形很麻烦，但是求一个点都没有的矩形就比较清晰，考虑正难则反，最后用总矩形数做差即可得到答案。
直接算矩形不好算，这里定一求一，因此枚举矩形下边界，快速计算合法矩形个数，让后就变成了如图问题。

没有资源点的列可以看作在第 0 行有一个资源点，同一列有多个资源点的可以看作仅有最下方的哪一个点。

可以看到，如果将这些二维点连起来，可以得到一颗笛卡尔树，而矩形计数问题，就可以转换为经典问题树上计数，即计算每个点下方没有任何资源点，且下边界在枚举位置的矩形个数。

由于从上往下建树会导致修改下边界时需要更新每一个点的答案，考虑从下往上进行建树，即根在最下方的那个点。然后对于一个点，其儿子贡献的矩形个数为，这里以右儿子为例，左儿子同理，具体可以结合图片绿色方框理解。

\Delta Ans=C^{2}_{sz_{ls}} \times (high_x - high_ls)

而后，由于朴素笛卡尔树不支持删除，所以对于每一个横坐标，重新建笛卡尔树求解，注意根到当前扫描下边界的矩形个数需要单独计算，复杂度 O(R \times C)，无法通过。

优化

考虑优化，瓶颈在于删除操作，想到 fhq-Treap 也是一种笛卡尔树，且支持删除，考虑把原本随机赋值的堆性质变量换成每一个点的横坐标，即可动态维护，使用 pushup 统计答案。

由于题目保证点随机，期望 O(R \log_2 C)，可以通过。

AC Code

小技巧：可以在初始化时把没有资源点看作是在第零行有一个资源点，这样会避免讨论边界。

#include<bits/stdc++.h>

#define ll long long
#define int long long
#define ull unsigned long long
#define mp make_pair
#define pb emplace_back
#define sort stable_sort
#define REP(i,l,r) for(int i=l;i<=r;++i)
#define PER(i,r,l) for(int i=r;i>=l;--i)

using namespace std;

const int inf=1e9+7;
const ll INF=1e18+7;

random_device R;
mt19937 G(R());
inline int rd(int l,int r){return uniform_int_distribution<int>(l,r)(G);}

char buf[1<<19],*p1=buf,*p2=buf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<19,stdin),p1==p2)?EOF:*p1++)
static inline int read() {
    register int x=0;
    register char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gc();
    return x;
}

 //奇怪的缺省源

namespace Code{
    const int N=1e5+7;
    int R,C,n;  
    struct dot{int x,y;}wiki[N];
    inline bool cmp(dot a,dot b){return a.x==b.x?a.y<b.y:a.x<b.x;}
    struct box{
        int son[2];
        int pri,val,sz;
        int ans;
    }tr[N];
    int rt;
#define ls tr[x].son[0]
#define rs tr[x].son[1]
    inline int js(int r,int c){return r*((c*(c+1))>>1ll);}
    inline void pu(int x){
        tr[x].sz=1+tr[ls].sz+tr[rs].sz;
        tr[x].ans= tr[ls].ans+js(tr[x].pri-tr[ls].pri,tr[ls].sz);
        tr[x].ans+=tr[rs].ans+js(tr[x].pri-tr[rs].pri,tr[rs].sz);
        // if(x==2){cout<<tr[rs].sz<<"DEBUG\n";}
    }
    int build(int l,int r){
        if(l>r)return 0;
        int mid=(l+r)>>1;
        tr[mid].son[0]=build(l,mid-1);
        tr[mid].son[1]=build(mid+1,r);
        pu(mid);return mid;
    }
    void split(int x,int &l,int &r,int key){
        if(!x){l=r=0;return;}
        if(tr[x].val<=key)l=x,split(rs,tr[l].son[1],r,key),pu(l);
        else              r=x,split(ls,l,tr[r].son[0],key),pu(r);
    }
    void merge(int &x,int l,int r){
        if(!l||!r){x=l|r;return;}
        if(tr[l].pri>tr[r].pri)x=l,merge(rs,tr[l].son[1],r),pu(x);
        else                   x=r,merge(ls,l,tr[r].son[0]),pu(x);
    }
    void change(dot node){
        int l,tmp,r;
        split(rt,l,r,node.y),split(l,l,tmp,node.y-1);
        tr[tmp].pri=node.x;
        // cout<<node.y<<'C'<<node.x<<'\n';
        merge(l,l,tmp),merge(rt,l,r);
    }   
    // void Print()
    signed main(){
        R=read(),C=read(),n=read();
        REP(i,1,n)wiki[i].x=read(),wiki[i].y=read();
        sort(wiki+1,wiki+n+1,cmp);
        REP(i,1,C)tr[i].val=i,tr[i].pri=0,tr[i].sz=1,tr[i].ans=0;
        rt=build(1,C);
        register int tot=0,Ans=0;
        REP(i,1,R){
            while(tot<n&&wiki[tot+1].x==i)change(wiki[tot+1]),++tot;
            Ans+=tr[rt].ans+js(i-tr[rt].pri,tr[rt].sz);
            // cout<<i<<":"<<rt<<' '<<tr[rt].ans<<' '<<js(i-tr[rt].pri,tr[rt].sz)<<'\n';
            // int x=rt;
            // cout<<"mmp:"<<tr[ls].sz<<' '<<tr[rs].sz<<' '<<js(tr[x].pri-tr[rs].pri,tr[rs].sz)<<'\n';
        }
        cout<<((R*(R+1)>>1ll)*(C*(C+1)>>1ll))-Ans<<'\n';
        return 0;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    Code::main();
    return 0;
}