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

题目链接：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;
}