覆盖的面积 线段树+理解转换

这个代码只是理解一下每个node存的东西是什么
(以点来代指区间)

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
typedef long long ll;
typedef pair<int, int > PII;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const double DINF = 1e20;
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e4 + 50;

struct Segment
{
    double x, y1, y2;
    int flag;

    bool operator < (const Segment &other) const { 
        return x < other.x;

    }
}seg[N * 2];

struct node
{
    int l, r, cnt;
    double len;
}tree[N * 8];

double scatter[N * 2];
int m;

inline void Push_up(int root)
{
    if (tree[root].cnt)
        tree[root].len = scatter[tree[root].r + 1]-scatter[tree[root].l];
    
    else {
        if (tree[root].l == tree[root].r) tree[root].len = 0;

        else tree[root].len = tree[root << 1].len 
            + tree[root << 1 | 1].len; 
            // 这一个地方其实就是为什么把点看成区间
            // 因为 1 - 4 二分成 1 - 2和 3 - 4 如果看成区间,则 1 - 3的区间
            //的距离等于 1 - 2 加上 3-4, 里面包含了 坐标意义下的(2 - 3),
            //如果把点看成是点,那么在求1 - 3 的区间距离的时候如果咱们相加
            // 则求到的是(坐标意义下的)1 - 2 和 3 - 4 的距离,并没有
            // 2 - 3 的区间距离

    }
}

inline void Buildtree(int l, int r, int root)
{
    tree[root] = {l, r, 0, 0};
    if (l == r) {
        return ;
    }
    int mid = l + r >> 1;

    Buildtree(l, mid, root << 1), Buildtree(mid + 1, r, root << 1 | 1);

    Push_up(root);

}

inline void Modify(int root, int L, int R, int val)
{
    if (tree[root].l >= L && tree[root].r <= R) {
        tree[root].cnt += val;
        Push_up(root);

    } else {
        int mid = tree[root].l + tree[root].r >> 1;

        if (L <= mid) Modify(root << 1, L, R, val);
        if (R > mid) Modify(root << 1 | 1, L, R, val);

        Push_up(root);

    }
}

inline int Get(double x)
{
    return lower_bound(scatter, scatter + m, x) - scatter;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n, cas = 1;

    while (cin >> n && n) {

        for (int i = 0, j = 0; i < n; i++) {
            double x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;

            scatter[j] = y1, seg[j++] = {x1, y1, y2, 1};
            scatter[j] = y2, seg[j++] = {x2, y1, y2, -1};

        }

        sort(seg, seg + n * 2);

        sort(scatter, scatter + n * 2);

        m = unique(scatter, scatter + n * 2) - scatter;

        Buildtree(0, m, 1); // 从0到m-1建立线段树
                             // 每一个点代表的是一个区间 

        double ans = 0;
        for (int i = 0; i < n * 2; i++) {
            if (i > 0) ans += (seg[i].x - seg[i - 1].x) * tree[1].len;

            Modify(1, Get(seg[i].y1), Get(seg[i].y2) - 1, seg[i].flag);

            // 为什么-1呢 ? 其实咱们在建立线段树的时候是建立了以点为区间,那么从y1 到 y2之间的距离其实是 y1的映射的点到(y2映射的点的前一个),
            // 此时有人就问, 为什么要用点来代表区间呢? 见上面的push_up
        }

        cout << "Test case #" << cas++ << endl;
        cout << "Total explored area: ";
        cout << fixed << setprecision(2) << ans << endl << endl;

    }

    return  0;
}   
上一篇:用Python实现武侠小说中的武打动作残影特效


下一篇:51单片机0-9数字LED灯循环输出