扫描线：

 

看图，图中的数字是横坐标离散后对应的下标，计算时左端点不变，右端点加1，所以总的更新的区间是l到r-1。

也可以理解为1代表的是（1到2这一段），2代表的是（2到3这一段），3代表的是（3到4这一段）。。。

 

代码：

#include
     
      using namespace std;#define ll long long#define pb push_back#define ls rt<<1,l,m#define rs rt<<1|1,m+1,r#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;struct line{    int x1,x2;    int h;    int cover;    bool operator < (const line &t)    {        return h
      
       l;vector
       
        w;struct Tree{    int l,r;    int sum;    int cover;}tree[N*8];void push_up(int rt){    if(tree[rt].cover)    {        tree[rt].sum=w[tree[rt].r+1]-w[tree[rt].l];    }    else    {        if(tree[rt].l==tree[rt].r)tree[rt].sum=0;        else tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;    }}void build(int rt,int l,int r){    tree[rt].sum=tree[rt].cover=0;    tree[rt].l=l,tree[rt].r=r;    if(l==r)return ;    int m=(l+r)>>1;    build(ls);    build(rs);}void Update(int L,int R,int delta,int rt,int l,int r){    if(L<=l&&r<=R)    {        tree[rt].cover+=delta;        push_up(rt);        return ;    }    int m=(l+r)>>1;    if(L<=m)Update(L,R,delta,ls);    if(R>m)Update(L,R,delta,rs);    push_up(rt);}int binasrh(int val,int l,int r){    int m;    while(l<=r)    {         m=(l+r)>>1;         if(w[m]==val)return m;         else if(w[m]
        
         >n;    for(int i=0;i
         
          >x1>>y1>>x2>>y2;        if(x1>x2||y1>y2)        {            swap(x1,x2);            swap(y1,y2);         }        x2++;        y2++;        l.pb(line{x1,x2,y1,1});        l.pb(line{x1,x2,y2,-1});        w.pb(x1);        w.pb(x2);    }     sort(w.begin(),w.end());    sort(l.begin(),l.end());    w.erase(unique(w.begin(),w.end()),w.end());        ll ans=0;    build(1,0,w.size()-1);    for(int i=0;i