[Codeforces 610D]Vika and Segments

這題可以看做給你一堆寬度為$1$的長方形 (由於寬度只有$1$，以下稱「線段」，但請注意這條線是有寬度的)，求總覆蓋面積

我們可以先處理平行重疊的線段
以水平線段為例
對於$y$座標相同的線段，以左端點的$x$座標進行排序
這樣就可以找出對於某個$x$ (新線段的左端點)，沿著這些線段最遠可以到多遠 (新線段的右端點) 了
於是，我們以一堆互不相交的水平線段取代了原本的，而不影響覆蓋面積

垂直線段也是一樣作法
實作請參考void MergeSegments(vector<pair<int,int> >&s)

現在同方向的線段重疊情形處理好了，來考慮水平和垂直方向線段的相交情形
可以發現，現在同一個點最多被覆蓋兩次 (水平線段+垂直線段)
因此可以直接套用「水平線段覆蓋面積+垂直線段覆蓋面積-兩者相交面積」

我們可以考慮對$y$離散化，然後掃描線從左到右掃
對於每個$x$座標
我們可以輕易地用$BIT$ ($Binary\ Indexed\ Tree$) 算出對於任何一個$x$的截面，水平線段的覆蓋數

對於每個存在垂直線段的$x$截面，我們只要將答案扣掉垂直線段覆蓋到的水平線段覆蓋數 ($BIT$裡面的一段區間)，然後加上垂直線段的長度就好

可以套用大量的STL來實現上述過程，小心不要被一堆$first$和$second$搞混亂就好XD

時間複雜度：$O(N\log N)$

code:

#include<cstdio>
#include<cassert>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef __int64 LL;
const int INF=2147483647;
void getmin(int &a,const int b){if(b<a)a=b;}
void getmax(int &a,const int b){if(b>a)a=b;}
int N;
void MergeSegments(vector<pair<int,int> >&s)
{
    assert(!s.empty());
    sort(s.begin(),s.end());
    pair<int,int>now=s[0];
    vector<pair<int,int> >ans;
    for(const pair<int,int>&p:s)
    {
        if(now.second<p.first)ans.push_back(now),now=p;
        else getmax(now.second,p.second);
    }
    ans.push_back(now);
    s.clear(),ans.swap(s);
}
struct Bit
{
    int n;
    vector<int>s;
    vector<LL>cnt;
    void clear(const int _n){n=_n;s.clear(),cnt.clear();s.resize(n,0),cnt.resize(n,0LL);}
    void Add(int i,const int v,const int ratio)
    {
        if(!ratio)return;
        assert(i<n&&(cnt[i]+=ratio)>=0);
        if(ratio<0){if(cnt[i])return;}
        if(ratio>0){if(cnt[i]>ratio)return;}
        while(i<n)s[i]+=(ratio<0?-v:v),i+=(i&(-i));
    }
    int Query(int i)
    {
        int ans=0;
        while(i)ans+=s[i],i-=(i&(-i));
        return ans;
    }
}BIT;
int Id(const vector<int>&y,const int val)
{
    const int ans=lower_bound(y.begin(),y.end(),val)-y.begin();
    assert(y[ans]==val);
    return ans;
}
LL Solve(const map<int,vector<pair<int,int> > >&mv,const map<int,vector<pair<int,int> > >&mh)
{
    map<int,map<int,int> >endpoints;
    vector<int>y;
    for(const auto &it:mh)
    {
        y.push_back(it.first),y.push_back(it.first+1);
        for(const pair<int,int>&p:it.second)
        {
            endpoints[p.first][it.first]++,endpoints[p.second][it.first]--;
        }
    }
    for(const auto &it:mv)for(const pair<int,int>&p:it.second)
    {
        y.push_back(p.first),y.push_back(p.second);
    }
    sort(y.begin(),y.end()),y.resize(unique(y.begin(),y.end())-y.begin());
    BIT.clear(y.size());
    int ynow=-1000000000;
    LL ans=0LL;
    auto eps=endpoints.begin();
    for(const auto &vsegs:mv)
    {
        for(;eps!=endpoints.end()&&eps->first<=vsegs.first;eps++)
        {
            ans+=(LL)((eps->first)-ynow)*BIT.Query((int)y.size()-1);
            ynow=eps->first;
            for(const auto &ep:eps->second)BIT.Add(Id(y,ep.first)+1,1,ep.second);
        }
        for(const pair<int,int>&vseg:vsegs.second)
        {
            ans-=BIT.Query(Id(y,vseg.second))-BIT.Query(Id(y,vseg.first));
            ans+=vseg.second-vseg.first;
        }
    }
    for(;eps!=endpoints.end();eps++)
    {
        ans+=(LL)((eps->first)-ynow)*BIT.Query((int)y.size()-1);
        ynow=eps->first;
        for(const auto &ep:eps->second)BIT.Add(Id(y,ep.first)+1,1,ep.second);
    }
    assert(y.empty()||BIT.Query((int)y.size()-1)==0);
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        map<int,vector<pair<int,int> > >mv,mh;
        for(int i=0,x1,y1,x2,y2;i<N;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x1==x2)mv[x1].push_back(make_pair(min(y1,y2),max(y1,y2)+1));
            else assert(y1==y2),mh[y1].push_back(make_pair(min(x1,x2),max(x1,x2)+1));
        }
        for(auto &it:mv)MergeSegments(it.second);
        for(auto &it:mh)MergeSegments(it.second);
        printf("%I64d\n",Solve(mv,mh));
    }
    return 0;
}