题解：P5476 [CCO 2015] 挖掘

fzitb7912 · 2026-07-21 09:02:56 · 题解

分析

先考虑维护出所有 k \times k 矩阵的颜色数量（价值），再维护出它第一次包含某个蛋的时间。

对于颜色数量，枚举出现了哪几个，容斥系数为 (-1)^{cnt-1}。然后差分加。时间复杂度 O(m2^{s}s+n^2)。

对于第一次包含某个蛋的时间，维护出每个点第一次有蛋的时间。然后滑动窗口跑两遍。时间复杂度 O(t + n^2)。

最后树状树组一下做到 O(m2^ss+n^2+t+t\log(n^2))。

代码

const int N = 2505, M = 1e5 + 10;
int n, k, m, t;
vector<pii> c;
int delt[N][N], val[N][N];
int mn[N][N], mn_[N][N];
int tim[N][N];
struct node{
    int op, x, y;
} q[M];
int qu[N], hh, tt;
vector<int> vec[M];
int tr[N * N];

il void add(int x, int y){
    ++ x;
    while(x) tr[x] += y, x -= x & (-x);
    return ;
}
il int qry(int x){
    ++ x; int res = 0;
    while(x < N * N) res += tr[x], x += x & (-x);
    return res;
}
il void solve(){ 
    n = rd, k = rd, m = rd;
    U(i, 1, m){
        int x = rd; c.clear();
        U(j, 1, x) c.push_back({rd, rd});
        for(auto [x, y]: c) assert(x <= n && y <= n);
        U(s, 1, (1 << x) - 1){
            int xmi = n + 1, ymi = n + 1, xmx = 0, ymx = 0;
            UU(j, 0, x) if((s >> j) & 1){
                xmi = min(xmi, c[j].x);
                xmx = max(xmx, c[j].x);
                ymi = min(ymi, c[j].y);
                ymx = max(ymx, c[j].y);             
            }
            if(xmx - xmi > k - 1|| ymx - ymi > k - 1) continue;
            int cnt = __builtin_popcount(s) - 1, v = 1;
            if(cnt & 1) v = -1;
            xmx = max(1, xmx - k + 1), ymx = max(1, ymx - k + 1);
            delt[xmx][ymx] += v;
            delt[xmx][ymi + 1] -= v;
            delt[xmi + 1][ymx] -= v;
            delt[xmi + 1][ymi + 1] += v;
        }
    }
    t = rd;
    U(i, 1, n) U(j, 1, n){
        delt[i][j] += delt[i - 1][j] + delt[i][j - 1] - delt[i - 1][j - 1];
        val[i][j] = delt[i][j];
        mn[i][j] = t + 1;
    }
    U(i, 1, t){
        q[i].op = rd, q[i].x = rd;
        if(q[i].op == 1){
            q[i].y = rd;
            mn[q[i].x][q[i].y] = min(mn[q[i].x][q[i].y], i);
        }
    }
    U(i, 1, n){
        hh = 0, tt = 1;
        U(j, 1, n){
            while(hh <= tt && mn[i][qu[tt]] >= mn[i][j]) -- tt;
            qu[++ tt] = j;
            while(hh <= tt && qu[hh] < j - k + 1) ++ hh;
            mn_[i][j] = mn[i][qu[hh]];
        }
    }
    U(j, k, n){
        hh = 0, tt = 1;
        U(i, 1, n){
            while(hh <= tt && mn_[qu[tt]][j] >= mn_[i][j]) -- tt;
            qu[++ tt] = i;
            while(hh <= tt && qu[hh] < i - k + 1) ++ hh;
            if(i >= k) tim[i - k + 1][j - k + 1] = mn_[qu[hh]][j];
        }
    }
    int cnt = 0;
    U(i, 1, n - k  + 1) U(j, 1, n - k + 1){
        vec[tim[i][j]].push_back(val[i][j]);
        ++ cnt;
        add(val[i][j], 1);
    }
    U(i, 1, t){
        for(auto x: vec[i]){
            add(x, -1);
        }
        if(q[i].op == 2){
            int cnt_ = qry(q[i].x);
            printf("%.12lf\n", (double)(cnt_ * 1.0 / cnt));
        }
    }
    return ;
}