uvalive4108

题意

按顺序给出 n 个矩形，每给出一个矩形，统计它在多长的部分是最高的，并把这个长度称为该矩形的覆盖度，求最后总的覆盖度（每次得到的矩形的覆盖度之和）

分析

线段树。用两个数组分别统计区间最小值和最大值，再用一个数组来存 lazy 标记，向下传递。只有大于等于区间最大值，才能把当前区间的长度加入到答案中，如果小于区间最小值直接 return。

code

#include<bits/stdc++.h>

#define lson l, m, rt << 1

#define rson m + 1, r, rt << 1 | 1

using namespace std;

const int MAXN = 1e5 + 10;

int a[MAXN << 2], b[MAXN << 2], all[MAXN << 2];

int res;

void update(int L, int R, int val, int l, int r, int rt) {

    if(L <= l && r <= R) {

        if(a[rt] <= val) {

            a[rt] = b[rt] = all[rt] = val;

            res += r - l + 1;

            return;

        }

        if(b[rt] > val) return;

    }

    int m = (l + r) / 2;

    if(all[rt] > 0) {

        all[rt << 1] = a[rt << 1] = b[rt << 1] = all[rt];

        all[rt << 1 | 1] = a[rt << 1 | 1] = b[rt << 1 | 1] = all[rt];

        all[rt] = 0;

    }

    if(L <= m) update(L, R, val, lson);

    if(R > m) update(L, R, val, rson);

    a[rt] = max(a[rt << 1 | 1], a[rt << 1]);

    b[rt] = min(b[rt << 1 | 1], b[rt << 1]);

}

int main() {

    int T;

    while(scanf("%d", &T) && T) {

        while(T--) {

            memset(a, 0, sizeof a);

            memset(b, 0, sizeof b);

            memset(all, 0, sizeof all);

            int n;

            scanf("%d", &n);

            int ans = 0;

            while(n--) {

                int l, r, h;

                scanf("%d%d%d", &l, &r, &h);

                res = 0;

                update(l, r - 1, h, 1, MAXN, 1);

                ans += res;

            }

            printf("%d\n", ans);

        }

    }

    return 0;

}