P6137 题解

daniEl_lElE · 2023-12-02 14:33:13 · 题解

考虑把贡献拆开，计算两个位置横向走的步数和纵向走的步数分别是多少。

考虑这样有什么好处，对于 (i,j),(i+1,j),(i,j+1),(i+1,j+1) 都是区块，计算横向走的步数时，我们可以断掉 (i,j) 和 (i,j+1) 之间的边，这样计算出来的答案是一样的。

这样断边以后，我们发现原图变为了树。于是我们只需要对于每个横向边记录左右两边的子树大小，乘积求和即可。

总复杂度 O(N\log N)，加边要用 map 维护一下。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9;
int x[100005],y[100005],siz[100005],ans,n;
map<pair<int,int>,int> mp; 
vector<pair<int,int>> vc[100005];
void dfs(int now,int fa){
    siz[now]=1;
    for(auto v:vc[now]){
        if(v.first==fa) continue;
        dfs(v.first,now);
        (ans+=siz[v.first]*(n-siz[v.first])*v.second)%=mod;
        siz[now]+=siz[v.first];
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    for(int j=0;j<=1;j++){
        mp.clear();
        for(int i=1;i<=n;i++) vc[i].clear();
        for(int i=1;i<=n;i++){
            swap(x[i],y[i]);
            mp[make_pair(x[i],y[i])]=i; 
        }
        for(int i=1;i<=n;i++){
            int v=mp[make_pair(x[i]+1,y[i])];
            if(v){
                vc[v].push_back(make_pair(i,0));
                vc[i].push_back(make_pair(v,0));
            }
            v=mp[make_pair(x[i],y[i]+1)];
            if(v){
                if(!(mp[make_pair(x[i]-1,y[i])]&&mp[make_pair(x[i]-1,y[i]+1)])){
                    vc[v].push_back(make_pair(i,1));
                    vc[i].push_back(make_pair(v,1));
                }
            }
        }
        dfs(1,0);
    }
    cout<<ans;
    return 0;
}