Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct SegTree {
- struct Node {
- int cnt = 0;
- int dp[2] = {0, 0};
- bool l_flip = false;
- int l_add = 0;
- int min = 0;
- };
- int n;
- vector<int> all;
- vector<Node> data;
- SegTree(vector<int> all) :
- n(all.size()), all(all), data(4 * n) {
- init(1, 0, n - 2);
- }
- void init(int node, int b, int e) {
- if (b == e) {
- data[node].dp[0] = all[b + 1] - all[b];
- data[node].cnt = all[b + 1] - all[b];
- } else {
- int m = (b + e) / 2;
- init(node * 2, b, m);
- init(node * 2 + 1, m + 1, e);
- pull(node);
- }
- }
- int norm(int x) {
- return lower_bound(all.begin(), all.end(), x) - all.begin();
- }
- void push(int node, int b, int e) {
- if (data[node].l_flip) {
- swap(data[node].dp[0], data[node].dp[1]);
- if (b < e) {
- data[node * 2].l_flip ^= 1;
- data[node * 2 + 1].l_flip ^= 1;
- }
- data[node].l_flip = 0;
- }
- if (data[node].l_add) {
- data[node].min += data[node].l_add;
- if (b < e) {
- data[node * 2].l_add += data[node].l_add;
- data[node * 2 + 1].l_add += data[node].l_add;
- }
- data[node].l_add = 0;
- }
- }
- void pull(int node) {
- data[node].dp[0] = data[node * 2].dp[0] + data[node * 2 + 1].dp[0];
- data[node].dp[1] = data[node * 2].dp[1] + data[node * 2 + 1].dp[1];
- data[node].min = min(data[node * 2].min, data[node * 2 + 1].min);
- data[node].cnt = 0;
- if (data[node].min == data[node * 2].min)
- data[node].cnt += data[node * 2].cnt;
- if (data[node].min == data[node * 2 + 1].min)
- data[node].cnt += data[node * 2 + 1].cnt;
- }
- void update(int node, int b, int e, int l, int r, int val) {
- push(node, b, e);
- l = max(l, b); r = min(e, r);
- if (l > r) return;
- if (b == l && e == r) {
- data[node].l_flip ^= 1;
- data[node].l_add += val;
- push(node, b, e);
- return;
- }
- int m = (b + e) / 2;
- update(node * 2, b, m, l, r, val);
- update(node * 2 + 1, m + 1, e, l, r, val);
- pull(node);
- }
- void Update(int l, int r, int val) {
- l = norm(l); r = norm(r) - 1;
- if (l > r) return;
- update(1, 0, n - 2, l, r, val);
- }
- int Get() {
- int ret = all.back() - all.front();
- if (data[1].min == 0) {
- ret -= data[1].cnt;
- }
- ret -= data[1].dp[1];
- return ret;
- }
- };
- int main() {
- int n; cin >> n;
- vector<tuple<int, int, int, int>> events;
- events.reserve(2 * n);
- vector<int> all;
- all.reserve(2 * n);
- for (int i = 0; i < n; ++i) {
- int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
- if (x1 > x2) swap(x1, x2);
- if (y1 > y2) swap(y1, y2);
- all.push_back(y1); all.push_back(y2);
- events.emplace_back(x1, y1, y2, +1);
- events.emplace_back(x2, y1, y2, -1);
- }
- sort(events.begin(), events.end());
- sort(all.begin(), all.end());
- all.erase(unique(all.begin(), all.end()), all.end());
- SegTree st(all);
- int last = -1;
- long long total = 0;
- for (int i = 0; i < 2 * n; ++i) {
- int x, y1, y2, val;
- tie(x, y1, y2, val) = events[i];
- total += 1LL * st.Get() * (x - last);
- // cerr << "x=" << x << "total=" << total << endl;
- st.Update(y1, y2, val);
- last = x;
- }
- cout << total << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement