CF243D Cubes 题解

首先由于都是平视，因此我们将这个东西分层考虑，每层分别考虑能看到几个。

由于最多有 个格子，因此这个只会变化 次。

将这个东西转一下，使得光线永远是从右上方照射过来，并且 坐标不为 。

考察什么时候会照到一个光线。实际上我们只关心垂直光线方向的投影。因此我们考虑将一个方块转化成经过右上方顶点的一条直线。

因此，我们就把这个问题转化成了一个线段覆盖问题，每次询问能看到几种颜色不同的线段。

不妨考虑没有修改的时候这么做。区间覆盖倒着做，考虑从优先级高到低加入，每次查询区间是否有空的，如果有就能看到，否则不能看到。

但是，带修改的情况就会破坏这个从小到大加入的情况，你发现直接考虑并不是很好维护。

我们换个角度，每次加入的区间持续范围是一个后缀。我们线段树维护的是 ，在这里看来是十分浪费的。

实际上，我们要求的就是这样一个问题，每次在 ， 覆盖一个优先级为 的矩形。基于后缀性质，我们可以有一个更优秀的做法。

考虑从高到底加入矩形，每次查询 的最大值是否比 小，如果小，则在任何时候都看不到。否则就存在一些时候能看到，并且时间就是最大值 。然后将区间所有位置对 取 即可。

一个方块的优先级是经过右上角定点的，斜率和光线法向量一样的直线的 轴截距。区间就是经过左上定点的，方向和光线方向相同的直线的 轴截距和经过右下定点的方向和光线方向相同的直线的 轴截距。

▶

INFO 参考代码

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>
 
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
 
namespace data_structure {
template <class info_t, class tag_t, class merge_info_op = std::plus<info_t>,
          class apply_op = std::multiplies<void>,
          class merge_tag_op = std::plus<tag_t>>
class lazy_segtree {
  public:
    const merge_info_op merge_info;
    const apply_op apply_to_info;
    const merge_tag_op merge_tag;
    const info_t id_info;
    const tag_t id_tag;
    const size_t npos = static_cast<size_t>(-1);
 
    struct node {
        info_t info;
        tag_t tag;
 
        size_t l, r;
 
        size_t mid() const { return (l + r) / 2; }
    };
 
    std::vector<node> t;
 
  private:
    size_t lc(const size_t &p) const { return 2 * p; }
    size_t rc(const size_t &p) const { return 2 * p + 1; }
    void update(size_t p) {
        t[p].info = merge_info(t[lc(p)].info, t[rc(p)].info);
        return;
    }
 
    void apply_to_node(size_t p, const tag_t &tag) {
        t[p].tag = merge_tag(tag, t[p].tag);
        t[p].info = apply_to_info(tag, t[p].info);
    }
 
    void spread(size_t p) {
        apply_to_node(lc(p), t[p].tag);
        apply_to_node(rc(p), t[p].tag);
        t[p].tag = id_tag;
        return;
    }
 
    void build(size_t l, size_t r, const std::vector<info_t> &init_val,
               size_t p = 1) {
        t[p].l = l;
        t[p].r = r;
        t[p].info = id_info;
        t[p].tag = id_tag;
        if (l + 1 == r) {
            t[p].info = init_val[l];
            return;
        }
        size_t mid = t[p].mid();
        build(l, mid, init_val, lc(p));
        build(mid, r, init_val, rc(p));
        update(p);
        return;
    }
 
  public:
    lazy_segtree()
        : merge_info(), apply_to_info(), merge_tag(), id_info(), id_tag(), t() {
    }
 
    lazy_segtree(size_t n, const merge_info_op &_merge_info = merge_info_op(),
                 const apply_op &_apply = apply_op(),
                 const merge_tag_op &_merge_tag = merge_tag_op(),
                 const info_t &_info_id = info_t(),
                 const tag_t &_tag_id = tag_t())
        : merge_info(_merge_info), apply_to_info(_apply), merge_tag(_merge_tag),
          id_info(_info_id), id_tag(_tag_id), t(n * 4) {
        build(0, n, std::vector<info_t>(n, id_info));
    }
 
    template <class iter>
    void assign(iter iter_begin, iter iter_end) {
        size_t n = std::distance(iter_begin, iter_end);
        build(0, n, std::vector<info_t>(iter_begin, iter_end));
    }
 
    template <class iter>
    lazy_segtree(iter iter_begin, iter iter_end,
                 const merge_info_op &_merge_info = merge_info_op(),
                 const apply_op &_apply = apply_op(),
                 const merge_tag_op &_merge_tag = merge_tag_op(),
                 const info_t &_info_id = info_t(),
                 const tag_t &_tag_id = tag_t())
        : merge_info(_merge_info), apply_to_info(_apply), merge_tag(_merge_tag),
          id_info(_info_id), id_tag(_tag_id),
          t(std::distance(iter_begin, iter_end) * 4) {
        assign(iter_begin, iter_end);
    }
 
    void apply(size_t l, size_t r, const tag_t &tag, size_t p = 1) {
        if (l <= t[p].l && t[p].r <= r) {
            apply_to_node(p, tag);
            return;
        }
        size_t mid = t[p].mid();
        spread(p);
        if (l < mid) {
            apply(l, r, tag, lc(p));
        }
        if (mid < r) {
            apply(l, r, tag, rc(p));
        }
        update(p);
        return;
    }
 
    info_t query(size_t l, size_t r, size_t p = 1) {
        if (l <= t[p].l && t[p].r <= r) {
            return t[p].info;
        }
        size_t mid = t[p].mid();
        spread(p);
        info_t ret = id_info;
        if (l < mid) {
            ret = merge_info(query(l, r, lc(p)), ret);
        }
        if (mid < r) {
            ret = merge_info(ret, query(l, r, rc(p)));
        }
        update(p);
        return ret;
    }
 
    void set(size_t pos, const info_t &info, size_t p = 1) {
        if (t[p].l + 1 == t[p].r) {
            t[p].info = info;
            return;
        }
        size_t mid = t[p].mid();
        spread(p);
        if (pos < mid) {
            set(pos, info, lc(p));
        }
        else {
            set(pos, info, rc(p));
        }
        update(p);
        return;
    }
};
} // namespace data_structure
 
namespace numbers {
template <typename T>
T inf() {
    assert(false);
}
 
template <>
int inf<int>() {
    return 0x3f3f3f3f;
}
 
template <>
uint inf<uint>() {
    return 0x3f3f3f3f;
}
 
template <>
ll inf<ll>() {
    return 0x3f3f3f3f3f3f3f3f;
}
 
template <>
ull inf<ull>() {
    return 0x3f3f3f3f3f3f3f3f;
}
} // namespace numbers
 
namespace solve {
struct info_t {
    uint val;
 
    info_t(uint _val = 0) : val(_val) {}
 
    friend info_t operator+(const info_t &lhs, const info_t &rhs) {
        return std::max(lhs.val, rhs.val);
    }
};
 
struct tag_t {
    uint val;
 
    tag_t(uint _val = numbers::inf<uint>()) : val(_val) {}
 
    friend tag_t operator+(const tag_t &lhs, const tag_t &rhs) {
        return std::min(lhs.val, rhs.val);
    }
 
    friend info_t operator*(const tag_t &lhs, const info_t &rhs) {
        return std::min(lhs.val, rhs.val);
    }
};
 
/**
 * 请注意数组的第一维其实是 y 坐标。
 */
 
std::vector<std::vector<uint>> height;
uint n;
int x, y;
 
void process_map() {
    x = -x;
    y = -y;
 
    height.assign(n, std::vector<uint>(n));
 
    {
        bool rhor = false, rvert = false;
 
        if (x < 0) {
            x = -x;
            rvert = true;
        }
 
        if (y < 0) {
            y = -y;
            rhor = true;
        }
 
        bool flip = false;
 
        if (y == 0) {
            std::swap(x, y);
            flip = true; // 需要保证 y 不是 0 map to 才能正确。
        }
 
        for (size_t i = 0; i < n; i++) {
            for (size_t j = 0; j < n; j++) {
                uint ri = rvert ? n - i - 1 : i;
                uint rj = rhor ? n - j - 1 : j;
 
                if (flip) {
                    std::swap(ri, rj);
                }
 
                std::cin >> height[rj][ri];
            }
        }
    }
 
    {
        ull g = std::gcd(x, y);
        x /= g, y /= g;
    }
 
    x = -x;
    y = -y;
}
 
struct cube {
    int l, r;
    int h; // 优先级。
};
 
std::vector<int> pos;
std::vector<std::vector<cube>> cb;
 
int map_to(int a, int b) { return a * -y + b * x; }
 
int priority(int a, int b) {
    // 请注意此时保证 y 非 0，交换之后就是 x 非零了。
 
    int cx = y, cy = -x;
 
    return b * -cx + a * cy;
}
 
void process_cube() {
    cb.assign(n, std::vector<cube>(n));
 
    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < n; j++) {
            /**
             * 这里的交点是，
             *
             * (i, j + 1)
             *
             * 和
             *
             * (i + 1, j)
             *
             * 考虑 formalize，映射到 x 轴上，y 坐标为 0。
             *
             * 需要同时除掉 y。比较难办啊。那你把横坐标乘上 y 即可。
             */
 
            cb[i][j].l = map_to(j, i + 1);
            cb[i][j].r = map_to(j + 1, i);
            cb[i][j].h = priority(j + 1, i + 1); // 越大越高。
 
            pos.push_back(map_to(j, i + 1));
            pos.push_back(map_to(j + 1, i));
        }
    }
 
    /**
     * 优先级，采用直线截距。靠。这傻逼题目真他妈难写。
     */
 
    std::sort(pos.begin(), pos.end());
    pos.resize(std::unique(pos.begin(), pos.end()) - pos.begin());
}
 
std::vector<std::pair<cube, uint>> query;
uint maxn = 0;
 
void process_queries() {
    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < n; j++) {
            maxn = std::max(height[i][j], maxn);
        }
    }
 
    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < n; j++) {
            height[i][j] = maxn - height[i][j];
        }
    }
 
    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < n; j++) {
            query.emplace_back(cb[i][j], height[i][j]);
        }
    }
 
    std::sort(
        query.begin(), query.end(),
        [](const std::pair<cube, uint> &lhs, const std::pair<cube, uint> &rhs) {
            return lhs.first.h > rhs.first.h;
        });
 
    return;
}
 
void solve() {
    std::cin >> n >> x >> y;
 
    process_map();
 
    process_cube();
 
    process_queries();
 
    std::vector<info_t> init_val(pos.size() - 1, info_t(maxn));
    data_structure::lazy_segtree<info_t, tag_t> segtree(init_val.begin(),
                                                        init_val.end());
 
    ull ans = 0;
 
    auto find_pos = [](int val) {
        return std::lower_bound(pos.begin(), pos.end(), val) - pos.begin();
    };
 
    for (size_t i = 0; i < n * n; i++) {
        auto cur = query[i];
 
        auto rl = find_pos(cur.first.l), rr = find_pos(cur.first.r);
 
        auto cur_maxn = segtree.query(rl, rr);
 
        if (cur_maxn.val <= cur.second) {
            continue;
        }
 
        ans += cur_maxn.val - cur.second;
 
        segtree.apply(rl, rr, tag_t{cur.second});
    }
 
    std::cout << ans << "\n";
}
} // namespace solve
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve::solve();
    std::cout << std::flush;
    return 0;
}