ECNU OJ 3353 涂黑板(线段树离散化)

我就是我 2022-05-29 13:29 231阅读 0赞

# 3353. 涂黑板 #

[DESCRIPTION][] [STATISTICS][] [DISCUSSION][]

**Time limit per test:** 3.0 seconds

**Memory limit:** 256 megabytes

林吉吉是一位富有艺术气息的绅士，读论文之余他最喜欢做的事情就是涂教室里的黑板。  
黑板可以看作一块二维平面，林吉吉想要在黑板上涂黑 n 个矩形，  
第 i 个矩形利用其左下角坐标 (li,di) 和右上角坐标 (ri,ui) 表示。

在涂黑了所有之后，林吉吉想要知道黑板上被涂黑的面积究竟有多少。

### Input ###

第一行为数据组数 T

每组数据第一行为矩阵数目 n，接下来 n 行为 li,di,ri,ui

数据约束：  
对于 40% 的数据保证 n≤1020≤li≤ri≤1020≤di≤ui≤102  
对于 70% 的数据保证 n≤1020≤li≤ri≤1090≤di≤ui≤109  
对于所有数据保证 T≤100n≤1030≤li≤ri≤1090≤di≤ui≤109 坐标为整数

### Output ###

每组数据输出一行整数，黑板被涂黑的面积

### Examples ###

input

2
    2
    1 1 10 10
    5 5 15 15
    2
    1 1 5 5
    10 10 15 15

output

156
    41

偷的HDU 1542的代码，直接改了改输入输出，double变ll。

浮点数先要离散化;然后把矩形分成两条边,上边和下边,对横轴建树,然后从下到上扫描上去,

用cnt表示该区间下边比上边多几个。

#include<bits/stdc++.h>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MAXN 100010
    #include <cstdio>
    #include <cstring>
    #include <cctype>
    #include <algorithm>
    #define lson l , m , rt << 1
    #define rson m + 1 , r , rt << 1 | 1
    const int maxn = 2222;
    int cnt[maxn << 2];
    long long sum[maxn << 2];
    long long X[maxn];
    struct Seg
    {
        long long h, l, r;
        int s;
        Seg() {}
        Seg(long long a,long long b,long long c,int d) : l(a), r(b), h(c), s(d) {}
        bool operator < (const Seg &cmp) const
        {
            return h < cmp.h;
        }
    } ss[maxn];
    void PushUp(int rt,int l,int r)
    {
        if (cnt[rt]) sum[rt] = X[r+1] - X[l];
        else if (l == r) sum[rt] = 0;
        else sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    }
    void update(int L,int R,int c,int l,int r,int rt)
    {
        if (L <= l && r <= R)
        {
            cnt[rt] += c;
            PushUp(rt, l, r);
            return ;
        }
        int m = (l + r) >> 1;
        if (L <= m) update(L, R, c, lson);
        if (m < R) update(L, R, c, rson);
        PushUp(rt, l, r);
    }
    int Bin(long long key,int n,long long X[])
    {
        int l = 0, r = n - 1;
        while (l <= r)
        {
            int m = (l + r) >> 1;
            if (X[m] == key) return m;
            if (X[m] < key) l = m + 1;
            else r = m - 1;
        }
        return -1;
    }
    int main()
    {
        #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
    //freopen("F:/cb/out.txt","w",stdout);
    #endif
        /*ios::sync_with_stdio(false);
        cin.tie(0);*/
        int n, cas = 1;
        int ca;
        scanf("%d",&ca);
        while(ca--)
        {
            scanf("%d",&n);
            int m = 0;
            while (n --)
            {
                long long a, b, c, d;
                scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
                X[m] = a;
                ss[m++] = Seg(a, c, b, 1);
                X[m] = c;
                ss[m++] = Seg(a, c, d, -1);
            }
            sort(X, X + m);
            sort(ss, ss + m);
            int k = 1;
            for (int i = 1 ; i < m ; i ++)
            {
                if (X[i] != X[i-1]) X[k++] = X[i];
            }
            memset(cnt, 0, sizeof(cnt));
            memset(sum, 0, sizeof(sum));
            long long ret = 0;
            for (int i = 0 ; i < m - 1 ; i ++)
            {
                int l = Bin(ss[i].l, k, X);
                int r = Bin(ss[i].r, k, X) - 1;
                if (l <= r) update(l, r, ss[i].s, 0, k - 1, 1);
                ret += sum[1] * (ss[i+1].h - ss[i].h);
            }
            printf("%lld\n",ret);
        }
        return 0;
    }

[DESCRIPTION]: https://acm.ecnu.edu.cn/problem/3353/
[STATISTICS]: https://acm.ecnu.edu.cn/problem/3353/statistics/
[DISCUSSION]: https://acm.ecnu.edu.cn/problem/3353/discussion/