样例不过求条
查看原帖
样例不过求条
730195
Little_Cabbage楼主2025/1/1 11:53
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 210;
const int M = 1000010;

int n;
struct node {
    int x1, x2, y1, y2, op;
    int z;
    bool operator < (const node &other) const {
        return z < other.z;
    }
} a[N];
int len;

struct SegmentTree {
    int x1, y1, x2, y2;
    int val;
    int lazy_add;
    int s1 = 0, s2 = 0, s3 = 0, s4 = 0;
} tr[M << 4];
int tot, root;

int son(int k, int op) {
    // return k * 4 + op - 2;
    if (op == 1) return tr[k].s1;
    else if (op == 2) return tr[k].s2;
    else if (op == 3) return tr[k].s3;
    else return tr[k].s4;
}

void up(int k, int op) {
    tr[k].val = tr[tr[k].s1].val + tr[tr[k].s2].val;
    if (!op) return ;
    tr[k].val += tr[tr[k].s3].val + tr[tr[k].s4].val;
}

void down(int k) {
    if (tr[k].lazy_add) {
        if (tr[k].x1 == tr[k].x2) {
            tr[tr[k].s1].val += tr[k].lazy_add * (tr[tr[k].s1].y2 - tr[tr[k].s1].y1 + 1) * (tr[tr[k].s1].x2 - tr[tr[k].s1].x1 + 1);
            tr[tr[k].s2].val += tr[k].lazy_add * (tr[tr[k].s2].y2 - tr[tr[k].s2].y1 + 1) * (tr[tr[k].s2].x2 - tr[tr[k].s2].x1 + 1);
            tr[tr[k].s1].lazy_add += tr[k].lazy_add;
            tr[tr[k].s2].lazy_add += tr[k].lazy_add;
        } else if (tr[k].y1 == tr[k].y2) {
            tr[tr[k].s1].val += tr[k].lazy_add * (tr[tr[k].s1].y2 - tr[tr[k].s1].y1 + 1) * (tr[tr[k].s1].x2 - tr[tr[k].s1].x1 + 1);
            tr[tr[k].s2].val += tr[k].lazy_add * (tr[tr[k].s2].y2 - tr[tr[k].s2].y1 + 1) * (tr[tr[k].s2].x2 - tr[tr[k].s2].x1 + 1);
            tr[tr[k].s1].lazy_add += tr[k].lazy_add;
            tr[tr[k].s2].lazy_add += tr[k].lazy_add;
        } else {
            tr[tr[k].s1].val += tr[k].lazy_add * (tr[tr[k].s1].y2 - tr[tr[k].s1].y1 + 1) * (tr[tr[k].s1].x2 - tr[tr[k].s1].x1 + 1);
            tr[tr[k].s2].val += tr[k].lazy_add * (tr[tr[k].s2].y2 - tr[tr[k].s2].y1 + 1) * (tr[tr[k].s2].x2 - tr[tr[k].s2].x1 + 1);
            tr[tr[k].s3].val += tr[k].lazy_add * (tr[tr[k].s3].y2 - tr[tr[k].s3].y1 + 1) * (tr[tr[k].s3].x2 - tr[tr[k].s3].x1 + 1);
            tr[tr[k].s4].val += tr[k].lazy_add * (tr[tr[k].s4].y2 - tr[tr[k].s4].y1 + 1) * (tr[tr[k].s4].x2 - tr[tr[k].s4].x1 + 1);
            tr[tr[k].s1].lazy_add += tr[k].lazy_add;
            tr[tr[k].s2].lazy_add += tr[k].lazy_add;
            tr[tr[k].s3].lazy_add += tr[k].lazy_add;
            tr[tr[k].s4].lazy_add += tr[k].lazy_add;
        }
        tr[k].lazy_add = 0;
    }
}

void Build(int &k, int x1, int y1, int x2, int y2) {
	if (!k) k = ++ tot;
	// cout << k << " " << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
    tr[k].x1 = x1, tr[k].y1 = y1, tr[k].x2 = x2, tr[k].y2 = y2;
    tr[k].val = tr[k].lazy_add = 0;
    if (x1 == x2 && y1 == y2) return ;
    int midx = floor((x1 + x2) / 2.0), midy = floor((y1 + y2) / 2.0);
    // cout << midx << " " << midy << "\n";
    // cout << "Yes\n"; 
    if (x1 == x2) {
        Build(tr[k].s1, x1, y1, x2, midy);
        Build(tr[k].s2, x1, midy + 1, x2, y2);
        up(k, 0);
    } else if (y1 == y2) {
        Build(tr[k].s1, x1, y1, midx, y2);
        Build(tr[k].s2, midx + 1, y1, x2, y2);
        up(k, 0);
    } else {
        Build(tr[k].s1, x1, y1, midx, midy);
        Build(tr[k].s2, x1, midy + 1, midx, y2);
        Build(tr[k].s3, midx + 1, y1, x2, midy);
        Build(tr[k].s4, midx + 1, midy + 1, x2, y2);
        up(k, 1);
    }
    // if (x1 < x2 && y1 < y2) {
    //     Build(tr[k].s1, x1, y1, midx, midy);
    //     Build(tr[k].s2, x1, midy + 1, midx, y2);
    //     Build(tr[k].s3, midx + 1, y1, x2, midy);
    //     Build(tr[k].s4, midx + 1, midy + 1, x2, y2);
    // } else if (x1 < x2) {
    //     Build(tr[k].s1, x1, y1, midx, y2);
    //     Build(tr[k].s2, midx + 1, y1, x2, y2);
    // } else if (y1 < y2) {
    //     Build(tr[k].s1, x1, y1, x2, midy);
    //     Build(tr[k].s2, x1, midy + 1, x2, y2);
    // }
}

void Updata(int k, int x1, int y1, int x2, int y2, int val) {
    // cout << tr[k].x1 << " " << tr[k].y1 << " " << tr[k].x2 << " " << tr[k].y2 << " " << val << "\n";
    // cout << "Updata " << k << " " << x1 << " " << y1 << " " << x2 << " " << y2 << " " << val << "\n";
    if (tr[k].x1 > x2 || tr[k].x2 < x1 || tr[k].y1 > y2 || tr[k].y2 < y1) return /*cout << "YYNN\n",*/ void();
    // cout << "No\n";
    if (tr[k].x1 >= x1 && tr[k].x2 <= x2 && tr[k].y1 >= y1 && tr[k].y2 <= y2) {
        tr[k].val += val * (tr[k].x2 - tr[k].x1 + 1) * (tr[k].y2 - tr[k].y1 + 1);
        tr[k].lazy_add += val;
        // cout << "--------------------\n";
        return ;
    }
    // cout << "Yes\n";
    down(k);
    if (tr[k].x1 == tr[k].x2) {
        Updata(tr[k].s1, x1, y1, x2, y2, val);
        Updata(tr[k].s2, x1, y1, x2, y2, val);
        up(k, 0);
    } else if (tr[k].y1 == tr[k].y2) {
        Updata(tr[k].s1, x1, y1, x2, y2, val);
        Updata(tr[k].s2, x1, y1, x2, y2, val);
        up(k, 0);
    } else {
        Updata(tr[k].s1, x1, y1, x2, y2, val);
        Updata(tr[k].s2, x1, y1, x2, y2, val);
        Updata(tr[k].s3, x1, y1, x2, y2, val);
        Updata(tr[k].s4, x1, y1, x2, y2, val);
        up(k, 1);
    }
}

int Query(int k, int x, int y) {
    if (tr[k].x1 > x || tr[k].x2 < x || tr[k].y1 > y || tr[k].y2 < y) return 0;
    if (x <= tr[k].x1 && tr[k].x2 <= x && y <= tr[k].y1 && tr[k].y2 <= y) return tr[k].val;
    down(k);
    int res = 0;
    if (tr[k].x1 == tr[k].x2) res += Query(tr[k].s1, x, y) + Query(tr[k].s2, x, y);
    else if (tr[k].y1 == tr[k].y2) res += Query(tr[k].s1, x, y) + Query(tr[k].s2, x, y);
    else res += Query(tr[k].s1, x, y) + Query(tr[k].s2, x, y) + Query(tr[k].s3, x, y) + Query(tr[k].s4, x, y);
    return res;
}

int Query(int k, int x1, int y1, int x2, int y2) {
    if (tr[k].x1 > x2 || tr[k].x2 < x1 || tr[k].y1 > y2 || tr[k].y2 < y1) return 0;
    if (x1 <= tr[k].x1 && tr[k].x2 <= x2 && y1 <= tr[k].y1 && tr[k].y2 <= y2) return tr[k].val;
    down(k);
    int res = 0;
    if (tr[k].x1 == tr[k].x2) res += Query(tr[k].s1, x1, y1, x2, y2) + Query(tr[k].s2, x1, y1, x2, y2);
    else if (tr[k].y1 == tr[k].y2) res += Query(tr[k].s1, x1, y1, x2, y2) + Query(tr[k].s2, x1, y1, x2, y2);
    else res += Query(tr[k].s1, x1, y1, x2, y2) + Query(tr[k].s2, x1, y1, x2, y2) + Query(tr[k].s3, x1, y1, x2, y2) + Query(tr[k].s4, x1, y1, x2, y2);
    return res;
}

signed main() {
    cin >> n;
    root = 0;
    tot = 0;
    // cout << (M << 4) << "\n";
    Build(root, -1200, -1200, 1200, 1200);
    // Build(root, -10, -10, 10, 10);
    // cout << root << "\n";
    // cout << "----------\n";
    for (int i = 1; i <= n; i ++ ) {
        int x, y, z, r;
        cin >> x >> y >> z >> r;
        a[ ++ len] = {z - r, y + r, y - r, z + r, 1, x - r};
        a[ ++ len] = {z - r, y + r, y - r, z + r, -1, x + r};
    }
    sort(a + 1, a + len + 1);
    int res = 0;
    for (int i = 1; i <= len; i ++ ) {
        res += tr[1].val * (a[i].z - a[i - 1].z);
        Updata(1, a[i].x1, a[i].y1, a[i].x2 - 1, a[i].y2 - 1, a[i].op);
        // cout << "----------\n";
    }
    cout << res << "\n";
    return 0;
}
2025/1/1 11:53
加载中...