题解：P3415 祭坛

ssy666666 · 2026-08-06 09:42:23 · 题解

考虑二分答案。我们设一个点 (x,y) 左侧水晶柱的数量为 l_{(x,y)}，右侧为 r_{(x,y)}，上方为 u_{(x,y)}，下方为 d_{(x,y)}。

考虑扫描线，维护扫到当前的 x，有哪些 y 满足 \min(l_{(x,y)},r_{(x,y)}) 大于等于当前二分的值，然后枚举这一列上没有水晶柱的区间，这些区间中 \min(u_{x,y},d_{x,y}) 是恒定的，对于这个值大于等于二分的值的部分，我们区间查询有哪些 y 满足条件。修改就是判一下当前这一列的点 (x,y) 移到扫描线左边后会不会对 y 行产生影响，如果产生影响就单点修。

这个扫描线用树状数组维护即可，时间复杂度 O(n \log^2 n)，常数很小。

AC Code

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x & (-x))
using namespace std ;
const int MAXN = 1e5 + 7 ;

struct BIT {
    int tr[MAXN] ;

    void add(int u , int num) {
        u ++ ;
        while (u <= 100001) {
            tr[u] += num ;
            u += lowbit(u) ;
        }
        return ;
    }

    int query(int u) {
        u ++ ;
        int ans = 0 ;
        while (u > 0) {
            ans += tr[u] ;
            u -= lowbit(u) ;
        }
        return ans ;
    }

    void init() {
        memset(tr , 0 , sizeof(tr)) ;
    }
}o;

vector<int> g[MAXN] ;
int p[MAXN] ;
bool w[MAXN] ;
int all[MAXN] ;
int check(int num) {
    memset(w , 0 , sizeof(w)) ;
    memset(all , 0 , sizeof(all)) ;

    int cnt = 0 ;

    o.init() ;
    for (int r = 0 ; r <= 100000 ; r ++) {
        int h = g[r].size() ;
        for (int i = 0 ; i < h - 1 ; i ++) {
            if (min(i + 1 , h - i - 1) >= num) {
                cnt += o.query(g[r][i + 1] - 1) - o.query(g[r][i]) ;
            }
        }

        for (int i = 0 ; i < h ; i ++) {
            int& u = g[r][i] ;
            all[u] ++ ;
            if (!w[u] and min(all[u] , p[u] - all[u]) >= num) {
                o.add(u , 1) ;
                w[u] = 1 ;
            }
            if (w[u] and min(all[u] , p[u] - all[u]) < num) {
                o.add(u , -1) ;
                w[u] = 0 ;
            }
        }
    }

    return cnt ;
}

signed main() {
    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int n ;
    cin >> n ;

    for (int i = 1 ; i <= n ; i ++) {
        int x , y ;
        cin >> x >> y ;
        g[x].push_back(y) ;
        p[y] ++ ;
    }

    for (int i = 0 ; i <= n ; i ++) {
        sort(g[i].begin() , g[i].end()) ;
    }

    int l = 1 , r = n , mid , ans = 0 , sz ;
    int e ;
    while (l <= r) {
        mid = (l + r) >> 1 ;
        e = check(mid) ;
        if (e) {
            l = mid + 1 ;
            ans = mid ;
            sz = e ;
        }
        else {
            r = mid - 1 ;
        }
    }

    cout << ans << "\n" << sz ;

    return 0 ;
}