[Codeforces Round #337 (Div. 2) pD][Segment Tree] Vika and Segments

原題連結
這題我寫的過程還是有點坎坷的

一開始突發奇想想用二維線段樹配合copy on write技巧去做，但是經過大神同學的教誨才發現我所實現的區間維護是做錯的.....而且二維的區間感覺非常難做。看來我對樹套樹的資料結構還是感受不夠深刻啊......

後來就換成掃描線的思路，可以發現這題非常趨近於經典的矩形覆蓋問題，只是長度和點數的計算上會有差別。

說說我的作法，使用copy on write對-1000000000~1000000000開線段樹，紀錄這裡面非0的節點有幾個（要實現這個要求還是有點技巧的，可以參考code）。
然後把每個線段拆成兩個事件，一個是進入線段樹，一個是出線段樹。具體該怎麼做也是需要思考一下。

還有一個有趣的點是，如果對y離散化然後用普通線段樹去做的話理論上也是可行的。只是我沒有深入想，有興趣可以自行實做看看。

時間複雜度：O(nlogc),c是值域大小

#define LL long long
#include<cstdio>
#include<algorithm>
using namespace std;
const LL maxn=100000+5;
const LL maxc=1000000000;
struct Line
{
    LL x,flag,y[2];
    Line(LL a,LL b,LL c,LL d) {x=a,flag=b,y[0]=c,y[1]=d;}
    Line() {}
    bool operator < (const Line& rhs) const {return x<rhs.x;}
}line[maxn*2];
struct Node
{
    Node *lc,*rc;
    LL tag,nz;
    Node() {tag=nz=0;lc=rc=NULL;}
}*root;
void modify(Node*& now,LL L,LL R,LL flag,LL y0,LL y1)
{
    if(!now) now=new Node();
    LL M=L+(R-L)/2;
    if(y0<= L && R<=y1) now->tag+=flag;
    else
    {
        if(y0<=M) modify(now->lc,L,M,flag,y0,y1);
        if(y1> M) modify(now->rc,M+1,R,flag,y0,y1);
    }
    if(now->tag) now->nz=R-L+1;
    else if(L!=R) now->nz=(now->lc?now->lc->nz:0)+(now->rc?now->rc->nz:0);
    else now->nz=0;
}
int main()
{
    LL N;
    scanf("%I64d",&N);
    for(LL i=0,x[2],y[2];i<N;i++)
    {
        scanf("%I64d%I64d%I64d%I64d",x,y,x+1,y+1);
        if(x[0]>x[1]) swap(x[0],x[1]);
        if(y[0]>y[1]) swap(y[0],y[1]);
        line[i*2]=Line(x[0],1,y[0],y[1]);
        line[i*2+1]=Line(x[1]+1,-1,y[0],y[1]);
    }
    sort(line,line+N*2);
    LL ans=0,x=0,val=0;
    for(LL i=0;i<N*2;i++)
    {
        ans+= (line[i].x-x)*val;
        while(i+1<N*2 && line[i+1].x==line[i].x)
        {
            modify(root,-maxc,maxc,line[i].flag,line[i].y[0],line[i].y[1]);
            i++;
        }
        modify(root,-maxc,maxc,line[i].flag,line[i].y[0],line[i].y[1]);
        x=line[i].x;
        val=root->nz;
    }
    printf("%I64d\n",ans);
}