BAPC 2019 G. Gluttonous Goop 线段树扫描线

逃离我推掉我的手 2023-07-18 04:51 2阅读 0赞

题目链接：https://nanti.jisuanke.com/t/44323  
题意：有若干个小方块，每秒会往八个方向扩展，问k秒后有多少个区域被覆盖  
思路：k秒后每个格子都扩展成了一个矩形，所以也就是求矩形面积并，用扫描线很好解决。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define fi first
    #define se second
    #define ls rt << 1
    #define rs rt << 1|1
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    #define pll pair<ll, ll>
    #define pii pair<int, int>
    #define ull unsigned long long
    #define pdd pair<double, double>
    const int mod = 1e9 + 7;
    const int maxn = 1e4 + 10;
    const int inf = 0x3f3f3f3f;
    struct node
    {
        int x, y1, y2, k;
        bool operator < (const node &r) const
        {
            return x < r.x;
        }
    }a[maxn << 3];
    int cnt[maxn << 3], len[maxn << 3];
    vector<int> v;
    char s[30][30];
    
    int getid(int x)
    {
        return lower_bound(v.begin(), v.end(), x) - v.begin();
    }
    void push_down(int l, int r, int rt)
    {   //例如[4, 4]这种情况，就要v[5] - v[4]，所以要r+1
        if(cnt[rt]) len[rt] = v[r + 1] - v[l]; //被覆盖的话该节点的长度就为两个端点间的长度
        else len[rt] = len[ls] + len[rs]; //否则就统计子区间的长度
    }
    void update(int ql, int qr, int val, int l, int r, int rt)
    {
        //cout << ql << " " << qr << endl;
        if(ql <= l && r <= qr)
        {
            cnt[rt] += val;
            push_down(l, r, rt);
            return;
        }
        int mid = (l + r) >> 1;
        if(ql <= mid) update(ql, qr, val, lson);
        if(qr > mid) update(ql, qr, val, rson);
        push_down(l, r, rt);
    }
    
    int main()
    {
        int r, c, k, tot = 0;
        scanf("%d%d%d", &r, &c, &k);
        for(int i = r; i >= 1; --i)
        {
            scanf("%s", s[i] + 1);
            for(int j = 1; j <= c; ++j)
            {
                if(s[i][j] == '#')
                {
                    int x1 = i - k, y1 = j - k, x2 = i + k + 1, y2 = j + k + 1;
                    a[++tot].x = x1, a[tot].y1 = y1, a[tot].y2 = y2, a[tot].k = 1;
                    a[++tot].x = x2, a[tot].y1 = y1, a[tot].y2 = y2, a[tot].k = -1;
                    v.push_back(y1), v.push_back(y2);
                }
            }
        }
        sort(a + 1, a + tot + 1);
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        ll ans = 0;
        int sz = v.size(); //这才是线段树的范围
        for(int i = 1; i < tot; ++i)
        {
            int l = getid(a[i].y1), r = getid(a[i].y2) - 1; //区间[l, r);
            //cout << l << " " << r << endl;
            update(l, r, a[i].k, 0, sz - 1, 1);
            // cout << l << " " << r << endl;
            ans += 1ll * len[1] * (a[i + 1].x - a[i].x);
        }
        printf("%lld\n", ans);
        return 0;
    }