sweep line fudida com segtree priquitin

#include <bits/stdc++.h>
#define MAX 1000000007

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;

template<typename T>
void trace(T a) { cout << a << "\n";}
template<typename T, typename... Args>
void trace(T a, Args... args) { cout << a << " "; trace(args...);}

struct Q{
    ll x, l, r;
    bool end;
    Q(ll _x, ll _l, ll _r, bool _end): x(_x), l(_l), r(_r), end(_end){}
};

struct node;
node *newNode();

struct node{
  ll value;
  bool lazy;
  node *l, *r;

  node():value(0), l(NULL), r(NULL), lazy(0){}

  void expand(int a, int b){
      if(!l) l = newNode();
      if(!r) r = newNode();
      if(lazy){
          int mid = (a+b)/2;
          l->doLazy(abs(mid-a+1-l->value));
          r->doLazy(abs(mid-b-r->value));
          lazy = lazy^1;
      }
  }

  void doLazy(int value){
        lazy = lazy^1;
        this->value = value;
  }

  ll query(int a, int b, ll i, ll j){
      if(i > b || j < a) return 0;
      if(a >= i && b <= j) return value;
      expand(a, b);
      int mid = (a+b)/2;
      return l->query(a, mid, i, j) + r->query(mid+1, b, i, j);
  }

  void update(int a, int b, ll i, ll j){
      if(i > b || j < a) return;
      if(a >= i && b <= j) {
          doLazy(abs(b-a+1-value));
      }else{
        expand(a, b);
        int mid = (a+b)/2;
        l->update(a, mid, i, j);
        r->update(mid+1, b, i, j);

        value = l->value + r->value;
      }
  }
};

node *newNode(){
    static int bufSize = 1e7;
    static node buf[(int)1e7];
    assert(bufSize);
    return &buf[--bufSize];
}
bool compare(Q a, Q b){
    if(a.x == b.x) return a.end < b.end;
    return a.x < b.x;
}

int main(){
    node *root = newNode();
    int n; scanf("%d", &n);
    vector<Q> que;

    for(int i = 0; i < n; i++){
        int a, b, c, d;scanf("%d %d %d %d", &a, &b, &c, &d);
        que.push_back(Q(a, b, d, false));
        que.push_back(Q(c, b, d, true));
    }

    sort(que.begin(), que.end(), compare);
    ll ans = 0;
    ll last = 0;
    for(int i = 0; i < que.size();){
        Q ac = que[i];
        if(i) ans += last*(ac.x-que[i-1].x);

        ll past = que[i].x;
        //trace("chegou ", ans, "-", root->value);
        while(ac.x == past && !ac.end){
            root->update(0, MAX, ac.l, ac.r-1);
            past = ac.x;
            ac = que[++i];
        }
        //ans += root->value;
        while(ac.x == past){
            root->update(0, MAX, ac.l, ac.r-1);
            past = ac.x;
            ac = que[++i];
        }
        //trace("saiu ", root->value);
        last = root->value;
    }
    printf("%lld\n", ans);

    return 0;
}