4004번: 쿠나이

https://www.acmicpc.net/problem/4004

풀이는 아래 링크로 대체한다.
https://algospot.com/wiki/old/232/APIO2012

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define idx(u,v) (gd[(u)/2][0]*x[v]+gd[(u)/2][1]*y[v])
#define pos(u) (2*x[u]-y[u])
#define dis(u,v) (abs(x[u]-x[v])+abs(y[u]-y[v]))
const int MXN = 1e5, dx[] = { 0,-1,0,1 }, dy[] = { 1,0,-1,0 }, fd[][3] = { { 0,7,11 },{ 1,3,9 },{ 2,5,10 },{ 4,6,8 } }, gd[][2] = { { 1,-1 },{ 1,1 },{ 1,-1 },{ 1,1 },{ 0,1 },{ 1,0 } };
map<int, map<int, int> > mc[12];
priority_queue<pair<int, pair<int, int> > > pq;
int x[MXN], y[MXN], d[MXN], w, h, n, ev[MXN], lt[MXN * 8], ct[MXN * 8];
long long res;
struct st { int l, r, p, c; };
vector<st> line;
vector<int> cd;
int find(int u, int v) {
    auto &mp = mc[u ^ 1][idx(u, v)];
    auto it = mp.upper_bound(pos(v));
    if (u & 1) {
        if (it == mp.begin()) return -1;
        return (--it)->second;
    }
    return it == mp.end() ? -1 : it->second;
}
void add(int t, int i) {
    if (!~i || t == ev[i]) return;
    ev[i] = t;
    int sx = x[i], sy = y[i], ex = sx + t / 2 * dx[d[i]], ey = sy + t / 2 * dy[d[i]];
    if (sx > ex) swap(sx, ex);
    if (sy > ey) swap(sy, ey);
    sx = max(sx, 1);
    sy = max(sy, 1);
    ex = min(ex, h) + 1;
    ey = min(ey, w) + 1;
    line.push_back({ sx,ex,sy,1 });
    line.push_back({ sx,ex,ey,-1 });
    cd.push_back(sx);
    cd.push_back(ex);
    for (int it : fd[d[i]]) {
        int h = find(it, i), t;
        if (~h) {
            mc[it][idx(it, i)].erase(pos(i));
            t = find(it ^ 1, h);
            if (~t) pq.push({ -dis(h, t), make_pair(h, t) });
        }
    }
}
void update(int h, int l, int r, int gl, int gr, int c) {
    if (r < gl || gr < l) return;
    if (gl <= l&&r <= gr) ct[h] += c;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, c);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, c);
    }
    lt[h] = ct[h] ? cd[r + 1] - cd[l] : l^r ? lt[h * 2 + 1] + lt[h * 2 + 2] : 0;
}
int main() {
    scanf("%d%d%d", &w, &h, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", y + i, x + i, d + i);
        pq.push({ -2e9, make_pair(i,-1) });
        ev[i] = 2e9 + 1;
    }
    for (int i = 0; i < n; i++) for (int it : fd[d[i]]) {
        int t = find(it, i);
        if (~t) pq.push({ -dis(i,t), make_pair(i,t) });
        mc[it][idx(it, i)][pos(i)] = i;
    }
    while (!pq.empty()) {
        int t = -pq.top().first;
        pair<int, int> p = pq.top().second;
        pq.pop();
        if (ev[p.first] < t || ~p.second && ev[p.second] < t) continue;
        add(t, p.first);
        add(t, p.second);
    }
    sort(cd.begin(), cd.end());
    cd.erase(unique(cd.begin(), cd.end()), cd.end());
    sort(line.begin(), line.end(), [](st u, st v) {return u.p < v.p; });
    for (int i = 0; i < line.size(); i++) {
        if (i) res += 1LL * (line[i].p - line[i - 1].p)*lt[0];
        update(0, 0, cd.size() - 1, lower_bound(cd.begin(), cd.end(), line[i].l) - cd.begin(),
            lower_bound(cd.begin(), cd.end(), line[i].r) - cd.begin() - 1, line[i].c);
    }
    printf("%lld", res);
    return 0;
}