610D - Vika and Segments（线段树+扫描线+离散化）

扫描线：http://www.cnblogs.com/scau20110726/archive/2013/04/12/3016765.html

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

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

代码：

#include<bits/stdc++.h>
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<t.h;}
};
vector<line>l;
vector<int>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]<val)l=m+1;else r=m-1;}return -1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,x1,x2,y1,y2;cin>>n;for(int i=0;i<n;i++){cin>>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<l.size()-1;i++){int L=binasrh(l[i].x1,0,w.size()-1);int R=binasrh(l[i].x2,0,w.size()-1);if(L<R)Update(L,R-1,l[i].cover,1,0,w.size()-1);ans+=(ll)tree[1].sum*(l[i+1].h-l[i].h);}cout<<ans<<endl;return 0; 
}