「kuangbin带你飞」专题七 线段树

Posted by StandHR on August 3, 2018
View times

传送门

A.HDU1166 敌兵布阵

入门题。点修改、查询区间和。

#include <cstdio>
using namespace std;

const int maxn = 50050;
int Tree[maxn << 2];

void PushUp(int rt) {
    Tree[rt] = Tree[rt << 1] + Tree[rt << 1 | 1];
}

void Build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", &Tree[rt]);
    } else {
        int mid = l + r >> 1;
        Build(l, mid, rt << 1);
        Build(mid + 1, r, rt << 1 | 1);
        PushUp(rt);
    }
}

void Modify(int l, int r, int rt, int point, int num) {
    if (l == r) {
        Tree[rt] += num;
    } else {
        int mid = l + r >> 1;
        if (mid >= point) {
            Modify(l, mid, rt << 1, point, num);
        } else {
            Modify(mid + 1, r, rt << 1 | 1, point, num);
        }
        PushUp(rt);
    }
}

int Query(int l, int r, int rt, int L, int R) {
    if (l >= L && r <= R) {
        return Tree[rt];
    } else {
        int mid = l + r >> 1;
        int sum = 0;
        if (mid >= L) {
            sum += Query(l, mid, rt << 1, L, R);
        }
        if (mid < R) {
            sum += Query(mid + 1, r, rt << 1 | 1, L, R);
        }
        return sum;
    }
}

int main() {
    int T;
    scanf("%d", &T);
    int Case = 1;
    while (T--) {
        printf("Case %d:\n", Case++);
        int n;
        scanf("%d", &n);
        Build(1, n, 1);
        char s[50];
        while (scanf("%s", s)) {
            if (s[0] == 'E') {
                break;
            }
            int c, b;
            scanf("%d%d", &c, &b);
            if (s[0] == 'A') {
                Modify(1, n, 1, c, b);
            } else if (s[0] == 'S') {
                Modify(1, n, 1, c, -b);
            } else if (s[0] == 'Q') {
                printf("%d\n", Query(1, n, 1, c, b));
            }
        }
    }
    return 0;
}

B.HDU1754 I Hate It

和A题一样的入门题,点修改,查询区间最大值。

#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 200005;
int Tree[maxn << 2];

void PushUp(int rt) {
    Tree[rt] = max(Tree[rt << 1], Tree[rt << 1 | 1]);
}

void Build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", &Tree[rt]);
    } else {
        int mid = l + r >> 1;
        Build(l, mid, rt << 1);
        Build(mid + 1, r, rt << 1 | 1);
        PushUp(rt);
    }
}

void Modify(int l, int r, int rt, int point, int num) {
    if (l == r) {
        Tree[rt] = num;
    } else {
        int mid = l + r >> 1;
        if (mid >= point) {
            Modify(l, mid, rt << 1, point, num);
        } else {
            Modify(mid + 1, r, rt << 1 | 1, point, num);
        }
        PushUp(rt);
    }
}

int Query(int l, int r, int rt, int L, int R) {
    if (l >= L && r <= R) {
        return Tree[rt];
    } else {
        int mid = l + r >> 1;
        int sum = 0;
        if (mid >= L) {
            sum = max(sum, Query(l, mid, rt << 1, L, R));
        }
        if (mid < R) {
            sum = max(sum, Query(mid + 1, r, rt << 1 | 1, L, R));
        }
        return sum;
    }
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        Build(1, n, 1);
        while (m--) {
            char o[10];
            int c, b;
            scanf("%s%d%d", o, &c, &b);
            if (o[0] == 'U') {
                Modify(1, n, 1, c, b);
            } else {
                printf("%d\n", Query(1, n, 1, c, b));
            }
        }
    }
    return 0;
}

C.POJ3468 A Simple Problem with Integers

区间修改入门题。带lazy的区间修改、查询区间和。

#include <cstdio>
using namespace std;
typedef long long ll;

const int maxn = 100050;

struct node {
    ll sum, lazy;
} Tree[maxn << 2];

void PushUp(int rt) {
    Tree[rt].sum = Tree[rt << 1].sum + Tree[rt << 1 | 1].sum;
}

void Build(int l, int r, int rt) {
    if (l == r) {
        scanf("%lld", &Tree[rt].sum);
    } else {
        int mid = l + r >> 1;
        Build(l, mid, rt << 1);
        Build(mid + 1, r, rt << 1 | 1);
        PushUp(rt);
    }
}

void PushDown(int rt, int ln, int rn) {
    if (Tree[rt].lazy) {
        Tree[rt << 1].lazy += Tree[rt].lazy;
        Tree[rt << 1].sum += Tree[rt].lazy * ln;
        Tree[rt << 1 | 1].lazy += Tree[rt].lazy;
        Tree[rt << 1 | 1].sum += Tree[rt].lazy * rn;
        Tree[rt].lazy = 0;
    }
}

void Modify(int l, int r, int rt, int L, int R, int num) {
    if (l >= L && r <= R) {
        Tree[rt].sum += num * (r - l + 1);
        Tree[rt].lazy += num;
    } else {
        int mid = l + r >> 1;
        PushDown(rt, mid - l + 1, r - mid);
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, num);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R, num);
        }
        PushUp(rt);
    }
}

ll Query(int l, int r, int rt, int L, int R) {
    if (l >= L && r <= R) {
        return Tree[rt].sum;
    } else {
        int mid = l + r >> 1;
        PushDown(rt, mid - l + 1, r - mid);
        ll sum = 0;
        if (mid >= L) {
            sum += Query(l, mid, rt << 1, L, R);
        }
        if (mid < R) {
            sum += Query(mid + 1, r, rt << 1 | 1, L, R);
        }
        return sum;
    }
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    Build(1, n, 1);
    while (q--) {
        char o[5];
        int a, b, c;
        scanf("%s", o);
        if (o[0] == 'C') {
            scanf("%d%d%d", &a, &b, &c);
            Modify(1, n, 1, a, b, c);
        } else {
            scanf("%d%d", &a, &b);
            printf("%lld\n", Query(1, n ,1, a, b));
        }
    }
    return 0;
}

D.POJ2528 Mayor’s posters

离散化处理。

注意:离散化后在两相邻差值大于一的数后插入一个数,防止染色错误。

例如:[1, 10], [1, 3], [5, 10]。离散化后对应为[1, 4], [1, 2], [3, 4]。这种情况如果不处理,染色计数为2——正确答案应为3,所以在3后增加一个4,使离散化后对应为[1, 5], [1, 2], [4, 5],即可得到正确答案。

#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <set>
using namespace std;
typedef pair<int, int> PII;

const int maxn = 100005;

int a[maxn << 1];
PII node[maxn];
int Tree[maxn << 2];
set<int> S;

void PushDown(int rt) {
    if(Tree[rt]) {
        Tree[rt << 1] = Tree[rt << 1 | 1] = Tree[rt];
        Tree[rt] = 0;
    }
}

void Modify(int l, int r, int rt, int L, int R, int num) {
    if (l >= L && r <= R) {
        Tree[rt] = num;
    } else {
        int mid = l + r >> 1;
        PushDown(rt);
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, num);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R, num);
        }
    }
}

int Query(int l, int r, int rt, int point) {
    if (l == r) {
        return Tree[rt];
    } else {
        int mid = l + r >> 1;
        PushDown(rt);
        if (point <= mid) {
            return Query(l, mid, rt << 1, point);
        } else {
            return Query(mid + 1, r, rt << 1 | 1, point);
        }
    }
}

void Init() {
    memset(Tree, 0, sizeof(Tree));
    memset(a, 0,sizeof(a));
    S.clear();
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        Init();
        int n;
        scanf("%d", &n);
        int cnt = 1;
        for (int i = 1; i <= n; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            node[i].first = x;
            node[i].second = y;
            a[cnt++] = x;
            a[cnt++] = y;
        }
        sort(a + 1, a + cnt);
        int len = unique(a + 1, a + cnt) - a - 1;
        int t = len;
        for (int i = 2; i <= t; i++) {
            if (a[i] - a[i - 1] > 1) {
                a[++len] = a[i - 1] + 1;
            }
        }
        sort(a + 1, a + len + 1);
        for (int i = 1; i <= n; i++) {
            int x = lower_bound(a + 1, a + len + 1, node[i].first) - a;
            int y = lower_bound(a + 1, a + len + 1, node[i].second) - a;
            Modify(1, len, 1, x, y, i);
        }
        for (int i = 1; i <= len; i++) {
            int ans = Query(1, len, 1, i);
            if (ans) {
                S.insert(ans);
            }
        }
        printf("%d\n", (int)S.size());
    }
    return 0;
}

E.HDU1698 Just a Hook

区间求和,只需修改区间数据,最后返回根节点的值即可。

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 100010;

struct node {
    int sum, lazy;
} Tree[maxn << 2];

void PushDown(int rt, int ln, int rn) {
    if (Tree[rt].lazy) {
        Tree[rt << 1].lazy = Tree[rt << 1 | 1].lazy = Tree[rt].lazy;
        Tree[rt << 1].sum = ln * Tree[rt].lazy;
        Tree[rt << 1 | 1].sum = rn * Tree[rt].lazy;
        Tree[rt].lazy = 0;
    }
}

void PushUp(int rt) {
    Tree[rt].sum = Tree[rt << 1].sum + Tree[rt << 1 | 1].sum;
}

void Modify(int l, int r, int rt, int L, int R, int num) {
    if (l >= L && r <= R) {
        Tree[rt].sum = (r - l + 1) * num;
        Tree[rt].lazy = num;
    } else {
        int mid = l + r >> 1;
        PushDown(rt, mid - l + 1, r - mid);
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, num);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R, num);
        }
        PushUp(rt);
    }
}

void Init(int n) {
    memset(Tree, 0, sizeof(Tree));
    Modify(1, n, 1, 1, n, 1);
}

int main() {
    int T;
    scanf("%d", &T);
    int Case = 0;
    while (T--) {
        int n;
        scanf("%d", &n);
        Init(n);
        int q;
        scanf("%d", &q);
        while (q--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            Modify(1, n, 1, a, b, c);
        }
        printf("Case %d: The total value of the hook is %d.\n", ++Case, Tree[1].sum);
    }
    return 0;
}

F.ZOJ1610 Count the Colors

注意这题染的是区间而不是端点,前开后闭,前端点加1。修改完后,用一个数组把所有叶子转存,最后统计段数。

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 8000;
int Tree[maxn << 2];
int color[maxn + 10];
int vis[maxn + 10];

void PushDown(int rt) {
    if (Tree[rt] != -1) {
        Tree[rt << 1] = Tree[rt << 1 | 1] = Tree[rt];
        Tree[rt] = -1;
    }
}

void Modify(int l, int r, int rt, int L, int R, int num) {
    if (l >= L && r <= R) {
        Tree[rt] = num;
    } else {
        if (Tree[rt] == num) {
            return;
        }
        int mid = l + r >> 1;
        PushDown(rt);
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, num);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R, num);
        }
    }
}

void Query(int l, int r, int rt) {
    if (Tree[rt] != -1) {
        for (int i = l; i <= r; i++) {
            color[i] = Tree[rt];
        }
    } else {
        if (l != r && Tree[rt] == -1) {
            int mid = l + r >> 1;
            Query(l, mid, rt << 1);
            Query(mid + 1, r, rt << 1 | 1);
        }
    }
}

void Init() {
    memset(Tree, -1, sizeof(Tree));
    memset(color, -1, sizeof(color));
    memset(vis, 0, sizeof(vis));
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        Init();
        int t = n;
        while (t--) {
            int x, y, c;
            scanf("%d%d%d", &x, &y, &c);
            if (x >= y) {
                continue;
            }
            Modify(1, maxn, 1, x + 1, y, c);
        }
        Query(1, maxn, 1);
        for (int i = 2; i <= maxn + 1; i++) {
            if (color[i] != color[i - 1] && color[i - 1] != -1) {
                vis[color[i - 1]]++;
            }
        }
        for (int i = 0; i <= maxn; i++) {
            if (vis[i]) {
                printf("%d %d\n", i, vis[i]);
            }
        }
        putchar('\n');
    }
    return 0;
}

G.POJ3264 Balanced Lineup

只建树和查询,每次返回区间最大值最小值,返回时讨论下区间分布。

#include <cstdio>
#include <utility>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;

const int maxn = 50010;
PII Tree[maxn << 2];

void PushUp(int rt) {
    Tree[rt].first = min(Tree[rt << 1].first, Tree[rt << 1 | 1].first);
    Tree[rt].second = max(Tree[rt << 1].second, Tree[rt << 1 | 1].second);
}

void Build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", &Tree[rt].first);
        Tree[rt].second = Tree[rt].first;
    } else {
        int mid = l + r >> 1;
        Build(l, mid, rt << 1);
        Build(mid + 1, r, rt << 1 | 1);
        PushUp(rt);
    }
}

PII Query(int l, int r, int rt, int L, int R) {
    if (l >= L && r <= R) {
        return Tree[rt];
    } else {
        int mid = l + r >> 1;
        PII mL, mR;
        if (mid >= L) {
            mL = Query(l, mid, rt << 1, L, R);
        }
        if (mid < R) {
            mR = Query(mid + 1, r, rt << 1 | 1, L, R);
        }
        if (mL.first && mR.first) {
            return PII(min(mL.first, mR.first), max(mL.second, mR.second));
        } else if (mL.first) {
            return mL;
        } else if (mR.first) {
            return mR;
        }
    }
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    Build(1, n, 1);
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        PII ans = Query(1, n, 1, x, y);
        printf("%d\n", ans.second - ans.first);
    }
    return 0;
}

H.HDU4027 Can you answer these queries?

区间不等更新,得修改到点,由于是开方,所以一定次数为1后就不用再修改,在修改前区间判断是否都为1。数据中存在x>y的情况需要讨论,每组测试后有空行。

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;

const int maxn = 100010;
ll Tree[maxn << 2];

void PushUp(int rt) {
    Tree[rt] = Tree[rt << 1] + Tree[rt << 1 | 1];
}

void Build(int l, int r, int rt) {
    if(l == r) {
        scanf("%lld", &Tree[rt]);
    } else {
        int mid = (l + r) >> 1;
        Build(l, mid, rt << 1);
        Build(mid + 1, r, rt << 1 | 1);
        PushUp(rt);
    }
}

void Modify(int l, int r, int rt, int L, int R) {
    if (Tree[rt] == r - l + 1) {
        return;
    } else if (l == r) {
        Tree[rt] = sqrt(Tree[rt]);
    } else {
        int mid = (l + r) >> 1;
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R);
        }
        PushUp(rt);
    }
}

ll Query(int l, int r, int rt, int L, int R) {
    if (l >= L && r <= R) {
        return Tree[rt];
    } else {
        int mid = (l + r) >> 1;
        ll sum = 0;
        if (mid >= L) {
            sum += Query(l, mid, rt << 1, L, R);
        }
        if (mid < R) {
            sum += Query(mid + 1, r, rt << 1 | 1, L, R);
        }
        return sum;
    }
}

int main() {
    int n;
    int Case = 0;
    while (scanf("%d", &n) != EOF) {
        printf("Case #%d:\n", ++Case);
        Build(1, n, 1);
        int m;
        scanf("%d", &m);
        while (m--) {
            int t, x, y;
            scanf("%d%d%d", &t, &x, &y);
            if (y < x) {
                swap(x, y);
            }
            if (t) {
                printf("%lld\n", Query(1, n, 1, x, y));
            } else {
                Modify(1, n, 1, x, y);
            }
        }
        putchar('\n');
    }
    return 0;
}

I.HDU1540 Tunnel Warfare

注意:多组测试样例。

每个点记录区间最大长度len,左端最大长度lL,右端最大长度rL。
父亲节点len = max(左孩子len, 右孩子len, 左孩子rL + 右孩子lL)
父亲节点lL = 左孩子lL + (左孩子连续 ? 右孩子lL : 0)
父亲节点rL = 右孩子rL + (右孩子连续 ? 左孩子rL : 0)

#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;

const int maxn = 50010;

struct node {
    int len, lL, rL;
} Tree[maxn << 2];

void PushUp(int l, int r, int rt) {
    Tree[rt].len = max(Tree[rt << 1].len , Tree[rt << 1 | 1].len);
    Tree[rt].len = max(Tree[rt].len, Tree[rt << 1].rL + Tree[rt << 1 | 1].lL);

    int mid = l + r >> 1;
    Tree[rt].lL = Tree[rt << 1].lL;
    if (Tree[rt].lL == mid - l + 1) {
        Tree[rt].lL += Tree[rt << 1 | 1].lL;
    }

    Tree[rt].rL = Tree[rt << 1 | 1].rL;
    if (Tree[rt].rL == r - mid) {
        Tree[rt].rL += Tree[rt << 1].rL;
    }
}

void Build(int l, int r, int rt) {
    if (l == r) {
        Tree[rt].len = Tree[rt].lL = Tree[rt].rL = 1;
    } else {
        int mid = l + r >> 1;
        Build(l, mid, rt << 1);
        Build(mid + 1, r, rt << 1 | 1);
        PushUp(l, r, rt);
    }
}

void Modify(int l, int r, int rt, int point, int operate) {
    if (l == r) {
        Tree[rt].len = Tree[rt].lL = Tree[rt].rL = operate;
    } else {
        int mid = l + r >> 1;
        if (point <= mid) {
            Modify(l, mid, rt << 1, point, operate);
        } else {
            Modify(mid + 1, r, rt << 1 | 1, point, operate);
        }
        PushUp(l, r, rt);
    }
}

int Query(int l, int r, int rt, int point) {
    if(Tree[rt].len == 0 || Tree[rt].len == r - l + 1) {
        return Tree[rt].len;
    } else {
        int mid = l + r >> 1;
        if (point <= mid) {
            if (point > mid - Tree[rt << 1].rL) {
                return Tree[rt << 1].rL + Tree[rt << 1 | 1].lL;
            } else {
                return Query(l, mid, rt << 1, point);
            }
        } else {
            if (point <= mid + Tree[rt << 1 | 1].lL) {
                return Tree[rt << 1].rL + Tree[rt << 1 | 1].lL;
            } else {
                return Query(mid + 1, r, rt << 1 | 1, point);
            }
        }
    }
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        stack<int> S;
        Build(1, n, 1);
        while (m--) {
            char o[10];
            scanf("%s", o);
            int x;
            if (o[0] == 'D') {
                scanf("%d", &x);
                S.push(x);
                Modify(1, n, 1, x, 0);
            } else if (o[0] == 'R') {
                x = S.top();
                S.pop();
                Modify(1, n, 1, x, 1);
            } else {
                scanf("%d", &x);
                printf("%d\n", Query(1, n, 1, x));
            }
        }
    }
    return 0;
}

J.HDU3974 Assign the task

dfs从根节点扫一遍,确定节点的次序,记录下节点的区间。最后和普通的线段树一样更新和查询。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int maxn = 50010;

int Index;
vector<int> V[maxn];
bool isRoot[maxn];
struct node {
    int num, lazy;
} Tree[maxn << 2];

struct parent {
    int start, end;
} Parent[maxn];

void Init() {
    memset(Tree, -1, sizeof(Tree));
    memset(Parent, 0, sizeof(Parent));
    memset(isRoot, true, sizeof(isRoot));
    for (int i = 0; i < maxn; i++) {
        V[i].clear();
    }
}

void dfs(int rt) {
    Parent[rt].start = ++Index;
    for (int i = 0; i < (int)V[rt].size(); i++) {
        dfs(V[rt][i]);
    }
    Parent[rt].end = Index;
}

void PushDown(int rt) {
    if (Tree[rt].lazy != -1) {
        Tree[rt << 1].lazy = Tree[rt << 1 | 1].lazy = Tree[rt].lazy;
        Tree[rt << 1].num = Tree[rt << 1 | 1].num = Tree[rt].lazy;
        Tree[rt].lazy = -1;
    }
}

void Modify(int l, int r, int rt, int L, int R, int num) {
    if (l >= L && r <= R) {
        Tree[rt].num = num;
        Tree[rt].lazy = num;
    } else {
        int mid = l + r >> 1;
        PushDown(rt);
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, num);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R, num);
        }
    }
}

int Query(int l, int r, int rt, int point) {
    if (l == r) {
        return Tree[rt].num;
    } else {
        int mid = l + r >> 1;
        PushDown(rt);
        if (mid >= point) {
            return Query(l, mid, rt << 1, point);
        } else {
            return Query(mid + 1, r, rt << 1 | 1, point);
        }
    }
}

int main() {
    int T;
    scanf("%d", &T);
    int Case = 0;
    while (T--) {
        Init();
        printf("Case #%d:\n", ++Case);
        int n;
        scanf("%d", &n);
        for (int i = 1; i < n; i++) {
            int v, u;
            scanf("%d%d", &u, &v);
            isRoot[u] = false;
            V[v].push_back(u);
        }
        Index = 0;
        for (int i = 1; i <= n; i++) {
            if (isRoot[i]) {
                dfs(i);
                break;
            }
        }
        int M;
        scanf("%d", &M);
        while (M--) {
            char op[5];
            scanf("%s", op);
            if (op[0] == 'T') {
                int a, b;
                scanf("%d%d", &a, &b);
                Modify(1, n, 1, Parent[a].start, Parent[a].end, b);
            } else {
                int a;
                scanf("%d", &a);
                printf("%d\n", Query(1, n, 1, Parent[a].start));
            }
        }
    }
    return 0;
}

K.HDU4578 Transformation

线段树的裸题,但更新有3种,要分情况写。最后要查询q次幂之和,$1<=q<=3$,$q$只有三种情况直接用ans数组存,主要注意add操作,要利用二项展开式:
$ans[1]$区间和
$ans[2]$区间平方和
$ans[3]$区间立方和

#include <cstdio>
using namespace std;
const int mod = 10007;
const int maxn = 100010;

struct node {
    int ans[4], add, multiply, set;
} Tree[maxn << 2];

void Build(int l, int r, int rt) {
    Tree[rt].ans[1] = Tree[rt].ans[2] = Tree[rt].ans[3] = 0;
    Tree[rt].multiply = 1;
    Tree[rt].add = Tree[rt].set = 0;
    if (l == r) {
        return;
    }
    int mid = l + r >> 1;
    Build(l, mid, rt << 1);
    Build(mid + 1, r, rt << 1 | 1);
}

void valueSet(int l, int r, int rt, int c) {
    int len = r - l + 1;
    Tree[rt].add = 0;
    Tree[rt].multiply = 1;
    Tree[rt].set = c;
    Tree[rt].ans[1] = len * c % mod;
    Tree[rt].ans[2] = len * c % mod * c % mod;
    Tree[rt].ans[3] = len * c % mod * c % mod * c % mod;
}

void valueMultiply(int l, int r, int rt, int c) {
    Tree[rt].add = (Tree[rt].add * c) % mod;
    Tree[rt].multiply = (Tree[rt].multiply * c) % mod;
    Tree[rt].ans[1] = Tree[rt].ans[1] * c % mod;
    Tree[rt].ans[2] = Tree[rt].ans[2] * c % mod * c % mod;
    Tree[rt].ans[3] = Tree[rt].ans[3] * c % mod * c % mod * c % mod;
}

void valueAdd(int l, int r, int rt, int c) {
    int len = r - l +1;
    Tree[rt].add = (Tree[rt].add + c) % mod;
    Tree[rt].ans[3] = (Tree[rt].ans[3]
                    + 3 * Tree[rt].ans[2] % mod * c % mod
                    + 3 * Tree[rt].ans[1] % mod * c % mod * c % mod
                    + len * c % mod * c % mod * c % mod) % mod;

    Tree[rt].ans[2] = (Tree[rt].ans[2]
                    + 2 * Tree[rt].ans[1] % mod * c % mod
                    + len * c % mod * c % mod) % mod;

    Tree[rt].ans[1] = (Tree[rt].ans[1] + len * c % mod) % mod;
}

void value(int l, int r, int rt, int o, int c) {
    if (o == 1) {
        valueAdd(l, r, rt, c);
    } else if (o == 2) {
        valueMultiply(l, r, rt, c);
    } else {
        valueSet(l, r, rt, c);
    }
}

void PushDown(int l, int r, int rt) {
    int mid = l + r >> 1;
    if (Tree[rt].set) {
        valueSet(l, mid, rt << 1, Tree[rt].set);
        valueSet(mid + 1, r, rt << 1 | 1, Tree[rt].set);
        Tree[rt].set = 0;
    }
    if (Tree[rt].multiply != 1) {
        valueMultiply(l, mid, rt << 1, Tree[rt].multiply);
        valueMultiply(mid + 1, r, rt << 1 | 1, Tree[rt].multiply);
        Tree[rt].multiply = 1;
    }
    if (Tree[rt].add) {
        valueAdd(l, mid, rt << 1, Tree[rt].add);
        valueAdd(mid + 1, r, rt << 1 | 1, Tree[rt].add);
        Tree[rt].add = 0;
    }
}

void PushUp(int rt) {
    Tree[rt].ans[1] = (Tree[rt << 1].ans[1] + Tree[rt << 1 | 1].ans[1]) % mod;
    Tree[rt].ans[2] = (Tree[rt << 1].ans[2] + Tree[rt << 1 | 1].ans[2]) % mod;
    Tree[rt].ans[3] = (Tree[rt << 1].ans[3] + Tree[rt << 1 | 1].ans[3]) % mod;
}

void Modify(int l, int r, int rt, int L, int R, int o, int c) {
    if (l >= L && r <= R) {
        value(l, r, rt, o, c);
    } else {
        int mid = l + r >> 1;
        PushDown(l, r, rt);
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, o, c);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R, o, c);
        }
        PushUp(rt);
    }
}

int Query(int l, int r, int rt, int L, int R, int p) {
    if (l >= L && r <= R) {
        return Tree[rt].ans[p];
    } else {
        PushDown(l, r, rt);
        int mid = l + r >> 1;
        int sum = 0;
        if (mid >= L) {
            sum = (sum + Query(l, mid, rt << 1, L, R, p)) % mod;
        }
        if (mid < R) {
            sum = (sum + Query(mid + 1, r, rt << 1 | 1, L, R, p)) % mod;
        }
        return sum;
    }
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n == 0 && m == 0) {
            break;
        }
        Build(1, n, 1);
        while (m--) {
            int o, x, y, c;
            scanf("%d%d%d%d", &o, &x, &y, &c);
            if (o == 4) {
                printf("%d\n", Query(1, n, 1, x, y, c));
            } else {
                Modify(1, n, 1, x, y, o, c);
            }
        }
    }
    return 0;
}

L.HDU4614 Vases and Flowers

线段树进行区间修改来维护区间和sum,表示区间已经插了多少花,利用sum和区间长度来计算还需要放多少花。二分找出开头空位和最后的空位。

#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 50010;

struct node {
    int sum, lazy;
} Tree[maxn << 2];

void Build(int l, int r, int rt) {
    Tree[rt].sum = 0;
    Tree[rt].lazy = -1;
    if (l == r) {
        return;
    }
    int mid = l + r >> 1;
    Build(l, mid, rt << 1);
    Build(mid + 1, r, rt << 1 | 1);
}

void PushDown(int l, int r, int rt) {
    if (Tree[rt].lazy != -1) {
        int mid = l + r >> 1;
        Tree[rt << 1].lazy = Tree[rt << 1 | 1].lazy = Tree[rt].lazy;
        Tree[rt << 1].sum = (mid - l + 1) * Tree[rt].lazy;
        Tree[rt << 1 | 1].sum = (r - mid) * Tree[rt].lazy;
        Tree[rt].lazy = -1;
    }
}

void PushUp(int rt) {
    Tree[rt].sum = Tree[rt << 1].sum + Tree[rt << 1 | 1].sum;
}

void Modify(int l, int r, int rt, int L, int R, int num) {
    if (l >= L && r <= R) {
        Tree[rt].lazy = num;
        Tree[rt].sum = num * (r - l + 1);
    } else {
        if (Tree[rt].sum == num * (r - l + 1)) {
            return;
        }
        PushDown(l, r, rt);
        int mid = l + r >> 1;
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, num);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R, num);
        }
        PushUp(rt);
    }
}

int Query(int l, int r, int rt, int L, int R) {
    if (l >= L && r <= R) {
        return Tree[rt].sum;
    } else {
        PushDown(l, r, rt);
        int mid = l + r >> 1;
        int sum = 0;
        if (mid >= L) {
            sum += Query(l, mid, rt << 1, L, R);
        }
        if (mid < R) {
            sum += Query(mid + 1, r, rt << 1 | 1, L, R);
        }
        return sum;
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        Build(1, n, 1);
        while (m--) {
            int k, a, b;
            scanf("%d%d%d", &k, &a, &b);
            if (k == 2) {
                printf("%d\n", Query(1, n, 1, a + 1, b + 1));
                Modify(1, n, 1, a + 1, b + 1, 0);
            } else {
                if (Query(1, n, 1, a + 1, n) == n - a) {
                    printf("Can not put any one.\n");
                } else {
                    int l = a + 1, r = n;
                    while (l < r) {
                        int mid = l + r >> 1;
                        if (Query(1, n, 1, l, mid) == mid - l + 1) {
                            l = mid + 1;
                        } else {
                            r = mid;
                        }
                    }
                    printf("%d ", l - 1);
                    l = a + 1, r = n;
                    int left = min(n - a - Query(1, n, 1, a + 1, n), b);
                    while (l < r) {
                        int mid = l + r >> 1;
                        if (mid - a - Query(1, n, 1, a + 1, mid) >= left) {
                            r = mid;
                        } else {
                            l = mid + 1;
                        }
                    }
                    printf("%d\n", r - 1);
                    Modify(1, n, 1, a + 1, l, 1);
                }
            }
        }
        putchar('\n');
    }
    return 0;
}

M.HDU4553 约会安排

线段树区间合并,用两个线段树分别维护屌丝和女神的预定状态:区间最长空闲时间maxLen、区间左端连续空闲时间left、区间右端连续空闲时间right。屌丝预定时只在屌丝区间查询和更新,女神预定时先在屌丝区间查询,如果没有再在女神区间查询,最后两个区间都要更新。

#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 100010;

struct SegTree {
    struct node {
        int left, right, maxLen;
    } Tree[maxn << 2];

    void Build(int l, int r, int rt) {
        Tree[rt].left = Tree[rt].right = Tree[rt].maxLen = r - l + 1;
        if (l == r) {
            return;
        } else {
            int mid = l + r >> 1;
            Build(l, mid, rt << 1);
            Build(mid + 1, r, rt << 1 | 1);
        }
    }

    void PushDown(int l, int r, int rt) {
        if (l == r) {
            return;
        }
        int mid = l + r >> 1;
        if (Tree[rt].maxLen == 0) {
            Tree[rt << 1].maxLen = Tree[rt << 1].left = Tree[rt << 1].right = 0;
            Tree[rt << 1 | 1].maxLen = Tree[rt << 1 | 1].left = Tree[rt << 1 | 1].right = 0;
        } else if (Tree[rt].maxLen == r - l + 1) {
            Tree[rt << 1].maxLen = Tree[rt << 1].left = Tree[rt << 1].right = mid - l + 1;
            Tree[rt << 1 | 1].maxLen = Tree[rt << 1 | 1].left = Tree[rt << 1 | 1].right = r - mid;
        }
    }

    void PushUp(int l, int r, int rt) {
        if (l == r) {
            return;
        }
        Tree[rt].maxLen = max(Tree[rt << 1].maxLen, Tree[rt << 1 | 1].maxLen);
        Tree[rt].maxLen = max(Tree[rt].maxLen, Tree[rt << 1].right + Tree[rt << 1 | 1].left);
        int mid = l + r >> 1;
        Tree[rt].left = Tree[rt << 1].left;
        if (Tree[rt << 1].left == mid - l + 1) {
            Tree[rt].left += Tree[rt << 1 | 1].left;
        }
        Tree[rt].right = Tree[rt << 1 | 1].right;
        if (Tree[rt << 1 | 1].right == r - mid) {
            Tree[rt].right += Tree[rt << 1].right;
        }
    }

    void Modify(int l, int r, int rt, int L, int R, int num) {
        if (l >= L && r <= R) {
            Tree[rt].left = Tree[rt].right = Tree[rt].maxLen = num * (r - l + 1);
        } else {
            int mid = l + r >> 1;
            PushDown(l, r, rt);
            if (mid >= L) {
                Modify(l, mid, rt << 1, L, R, num);
            }
            if (mid < R) {
                Modify(mid + 1, r, rt << 1 | 1, L, R, num);
            }
            PushUp(l, r, rt);
        }
    }

    int Query(int l, int r, int rt, int len) {
        int mid = l + r >> 1;
        if (Tree[rt].maxLen < len) {
            return 0;
        }
        if (Tree[rt].left >= len) {
            return l;
        }
        if (Tree[rt << 1].maxLen >= len) {
            return Query(l, mid, rt << 1, len);
        }
        if (Tree[rt << 1].right + Tree[rt << 1 | 1].left >= len) {
            return mid - Tree[rt << 1].right + 1;
        }
        return Query(mid + 1, r, rt << 1 | 1, len);
    }
} DS, NS;

int main() {
    int Cas;
    int Case = 0;
    scanf("%d", &Cas);
    while (Cas--) {
        printf("Case %d:\n", ++Case);
        int t, n;
        scanf("%d%d", &t, &n);
        DS.Build(1, t, 1);
        NS.Build(1, t, 1);
        while (n--) {
            char op[10];
            int x, y;
            scanf("%s", op);
            if (op[0] == 'S') {
                scanf("%d%d", &x, &y);
                printf("I am the hope of chinese chengxuyuan!!\n");
                DS.Modify(1, t, 1, x, y, 1);
                NS.Modify(1, t, 1, x, y, 1);
            } else if (op[0] == 'D') {
                scanf("%d", &x);
                int ans = DS.Query(1, t, 1, x);
                if (ans == 0) {
                    printf("fly with yourself\n");
                } else {
                    printf("%d,let's fly\n", ans);
                    DS.Modify(1, t, 1, ans, ans + x - 1, 0);
                }
            } else {
                scanf("%d", &x);
                int ans1 = DS.Query(1, t, 1, x);
                if (ans1 == 0) {
                    int ans2 = NS.Query(1, t, 1, x);
                    if (ans2 == 0) {
                        printf("wait for me\n");
                    } else {
                        printf("%d,don't put my gezi\n", ans2);
                        NS.Modify(1, t, 1, ans2, ans2 + x - 1, 0);
                        DS.Modify(1, t, 1, ans2, ans2 + x - 1, 0);
                    }
                } else {
                    printf("%d,don't put my gezi\n", ans1);
                    NS.Modify(1, t, 1, ans1, ans1 + x - 1, 0);
                    DS.Modify(1, t, 1, ans1, ans1 + x - 1, 0);
                }
            }
        }
    }
    return 0;
}

N.POJ1177 Picture

离散化后,两个方向两次扫描线,将答案相加。
cnt数组表示当前区间矩形个数。

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1e4 + 10;
struct Seg {
    int x1, x2, y, v;
    Seg() {}
    Seg(int x1, int x2, int y, int v) : x1(x1), x2(x2), y(y), v(v) {}
    bool operator < (const Seg &r) const {
        return y < r.y;
    }
} Tree[2][maxn];
int x[2][maxn], sum[maxn << 2], cnt[maxn << 2], m[2];

void PushUp(int l, int r, int rt, int w) {
    if (cnt[rt]) {
        sum[rt] = x[w][r + 1] - x[w][l];
    } else if (l == r) {
        sum[rt] = 0;
    } else {
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
}

void Modify(int l, int r, int rt, int L, int R, int v, int w) {
    if (l >= L && r <= R) {
        cnt[rt] += v;
    } else {
        int mid = l + r >> 1;
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, v, w);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R, v, w);
        }
    }
    PushUp(l, r, rt, w);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

        Tree[0][i] = Seg(x1, x2, y1, 1);
        Tree[0][i + n] = Seg(x1, x2, y2, -1);
        x[0][i] = x1;
        x[0][i + n] = x2;

        Tree[1][i] = Seg(y1, y2, x1, 1);
        Tree[1][i + n] = Seg(y1, y2, x2, -1);
        x[1][i] = y1;
        x[1][i + n] = y2;
    }
    n <<= 1;
    for (int i = 0; i < 2; i++) {
        sort(Tree[i] + 1, Tree[i] + n + 1);
        sort(x[i] + 1, x[i] + n + 1);
        m[i] = unique(x[i] + 1, x[i] + n + 1) - x[i] - 1;
    }
    int ans = 0;
    for (int i = 0; i < 2; i++) {
        int t = 0, last = 0;
        for (int j = 1; j <= n; j++) {
            int l = lower_bound(x[i] + 1, x[i] + m[i] + 1, Tree[i][j].x1) - x[i];
            int r = lower_bound(x[i] + 1, x[i] + m[i] + 1, Tree[i][j].x2) - x[i];
            Modify(1, m[i], 1, l, r - 1, Tree[i][j].v, i);
            t += abs(sum[1] - last);
            last = sum[1];
        }
        ans += t;
    }
    printf("%d\n", ans);
    return 0;
}

O.HDU1542 覆盖的面积

用one数组代表至少一次覆盖,two数组代表至少两次覆盖。
cnt表示当前区间矩形个数。
当$cnt=1$时,one数组更新,two数组等于左右孩子one数组的值。
当$cnt>1$时,两数组一起更新。
当$cnt=0$时,两数组都等于左右孩子值之和。

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 2010;
struct Seg {
    double x1, x2, y;
    int v;
    Seg() {}
    Seg(double x1, double x2, double y, int v) : x1(x1), x2(x2), y(y), v(v) {}
    bool operator < (const Seg &r) const {
        return y < r.y;
    }
} Tree[maxn];
double x[maxn], one[maxn << 2], two[maxn << 2];
int cnt[maxn << 2];

void PushUp(int l, int r, int rt) {
    if (cnt[rt] == 1) {
        one[rt] = x[r + 1] - x[l];
        if (l == r) {
            two[rt] = 0;
        } else {
            two[rt] = one[rt << 1] + one[rt << 1 | 1];
        }
    } else if (cnt[rt] > 1) {
        two[rt] = one[rt] = x[r + 1] - x[l];
    } else {
        if (l == r) {
            two[rt] = one[rt] = 0;
        } else {
            one[rt] = one[rt << 1] + one[rt << 1 | 1];
            two[rt] = two[rt << 1] + two[rt << 1 | 1];
        }
    }
}

void Modify(int l, int r, int rt, int L, int R, int v) {
    if (l >= L && r <= R) {
        cnt[rt] += v;
    } else {
        int mid = l + r >> 1;
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, v);
        }
        if (mid < R) {
            Modify(mid + 1, r , rt << 1 | 1, L, R, v);
        }
    }
    PushUp(l, r, rt);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            Tree[i] = Seg(x1, x2, y1, 1);
            Tree[i + n] = Seg(x1, x2, y2, -1);
            x[i] = x1;
            x[i + n] = x2;
        }
        n <<= 1;
        sort(Tree + 1, Tree + n + 1);
        sort(x + 1, x + n + 1);
        int m = unique(x + 1, x + n + 1) - x - 1;

        double ans = 0;
        for (int i = 1; i <= n; i++) {
            int l = lower_bound(x + 1, x + m + 1, Tree[i].x1) - x;
            int r = lower_bound(x + 1, x + m + 1, Tree[i].x2) - x;
            Modify(1, m, 1, l, r - 1, Tree[i].v);
            ans += two[1] * (Tree[i + 1].y - Tree[i].y);
        }
        printf("%.2f\n", ans);
    }
    return 0;
}

P.HDU1542 Atlantis

cnt表示当前区间矩形个数。扫描线扫出每段的面积加起来。

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 210;

struct Seg {
    double x1, x2, y;
    int v;
    Seg() {}
    Seg(double x1, double x2, double y, int v) : x1(x1), x2(x2), y(y), v(v) {}
    bool operator < (const Seg &r) const {
        return y < r.y;
    }
} Tree[maxn];

double x[maxn], sum[maxn << 2];
int cnt[maxn << 2];

void PushUp(int l, int r, int rt) {
    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 Modify(int l, int r, int rt, int L, int R, int v) {
    if (l >= L && r <= R) {
        cnt[rt] += v;
    } else {
        int mid = l + r >> 1;
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, v);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R, v);
        }
    }
    PushUp(l, r, rt);
}

int main() {
    int n;
    int Case = 0;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }
        for (int i = 1; i <= n; i++) {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            Tree[i] = Seg(x1, x2, y1, 1);
            Tree[i + n] = Seg(x1, x2, y2, -1);
            x[i] = x1;
            x[i + n] = x2;
        }
        n <<= 1;
        sort(Tree + 1, Tree + n + 1);
        sort(x + 1, x + n + 1);
        int m = unique(x + 1, x + n + 1) - x - 1;

        double ans = 0;
        for (int i = 1; i <= n; i++) {
            int l = lower_bound(x + 1, x + m + 1, Tree[i].x1) - x;
            int r = lower_bound(x + 1, x + m + 1, Tree[i].x2) - x;
            Modify(1, m, 1, l, r - 1, Tree[i].v);
            ans += sum[1] * (Tree[i + 1].y - Tree[i].y);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n", ++Case, ans);
    }
    return 0;
}

Q.HDU3642 Get The Treasury

三维的重叠。将x、z轴坐标离散化,然后用扫描线扫z轴区间,每个区间做二维的面积重叠计算。要想判断立方体是否在z轴的区间上,只要立方体z轴下坐标小于等于z[i],上坐标大于z[i]。

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;

const int maxn = 2010;
struct Seg {
    int x1, x2, y, v;
    Seg() {}
    Seg(int x1, int x2, int y, int v) : x1(x1), x2(x2), y(y), v(v) {}
    bool operator < (const Seg &r) const {
        return y < r.y;
    }
} Tree[maxn];
int x[maxn], z[maxn];
int cnt[maxn << 2], one[maxn << 2], two[maxn << 2], three[maxn << 2];

struct Point {
    int x, y, z;
    void init() {
        scanf("%d%d%d", &x, &y, &z);
    }
};

struct Cube{
    Point a, b;
} cube[maxn];

void PushUp(int l, int r, int rt) {
    if (cnt[rt] == 1) {
        one[rt] = x[r + 1] - x[l];
        if (l == r) {
            two[rt] = three[rt] = 0;
        } else {
            two[rt] = one[rt << 1] + one[rt << 1 | 1];
            three[rt] = two[rt << 1] + two[rt << 1 | 1];
        }
    } else if (cnt[rt] == 2) {
        one[rt] = two[rt] = x[r + 1] - x[l];
        if (l == r) {
            three[rt] = 0;
        } else {
            three[rt] = one[rt << 1] + one[rt << 1 | 1];
        }
    } else if (cnt[rt] > 2) {
        one[rt] = two[rt] = three[rt] = x[r + 1] - x[l];
    } else {
        if (l == r) {
            one[rt] = two[rt] = three[rt] = 0;
        } else {
            three[rt] = three[rt << 1] + three[rt << 1 | 1];
            two[rt] = two[rt << 1] + two[rt << 1 | 1];
            one[rt] = one[rt << 1] + one[rt << 1 | 1];
        }
    }
}

void Modify(int l, int r, int rt, int L, int R, int v) {
    if (l >= L && r <= R) {
        cnt[rt] += v;
    } else {
        int mid = l + r >> 1;
        if (mid >= L) {
            Modify(l, mid, rt << 1, L, R, v);
        }
        if (mid < R) {
            Modify(mid + 1, r, rt << 1 | 1, L, R, v);
        }
    }
    PushUp(l, r, rt);
}

int main() {
    int T;
    scanf("%d", &T);
    int Case = 0;
    while (T--) {
        printf("Case %d: ", ++Case);
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            cube[i].a.init();
            cube[i].b.init();
            x[i] = cube[i].a.x;
            x[i + n] = cube[i].b.x;
            z[i] = cube[i].a.z;
            z[i + n] = cube[i].b.z;
        }
        if (n < 3) {
            printf("0\n");
            continue;
        }
        n <<= 1;
        sort(x + 1, x + n + 1);
        int mx = unique(x + 1, x + n + 1) - x - 1;
        sort(z + 1, z + n + 1);
        int mz = unique(z + 1, z + n + 1) - z;

        ll ans = 0;
        for (int i = 1; i < mz; i++) {
            int cntNum = 1;
            for (int j = 1; j <= n >> 1; j++) {
                if (cube[j].a.z <= z[i] && cube[j].b.z > z[i]) {
                    Tree[cntNum++] = Seg(cube[j].a.x, cube[j].b.x, cube[j].a.y, 1);
                    Tree[cntNum++] = Seg(cube[j].a.x, cube[j].b.x, cube[j].b.y, -1);
                }
            }
            sort(Tree + 1, Tree + cntNum);
            ll t = 0;
            for (int j = 1; j < cntNum; j++) {
                int l = lower_bound(x + 1, x + mx + 1, Tree[j].x1) - x;
                int r = lower_bound(x + 1, x + mx + 1, Tree[j].x2) - x;
                Modify(1, mx, 1, l, r - 1, Tree[j].v);
                t += (ll)three[1] * (Tree[j + 1].y - Tree[j].y);
            }
            ans += t * (z[i + 1] - z[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}