猴子課堂-----------掃描線+離散化+線段樹

給出題目！ "題目界面" 那麼，大家一看一般是一臉矇蔽因為這確實聽刁鑽，許多人不會打二維線段樹，卻一直在想線段樹怎麼打，可悲~~（大佬：花了5分鐘打出二維線段樹，好難！）~~，那摸，大家，這道題怎麼做？接下來會涉及到離散化與線段樹，請自學，抱歉⊙﹏⊙ 那麼，這道題呢，重要的是掃描線（如圖）：那 ...

給出題目！
題目界面
那麼，大家一看一般是一臉矇蔽
這裡寫圖片描述

因為這確實聽刁鑽，許多人不會打二維線段樹，卻一直在想線段樹怎麼打，可悲~~（大佬：花了5分鐘打出二維線段樹，好難！）~~，那摸，大家，這道題怎麼做？

接下來會涉及到離散化與線段樹，請自學，抱歉⊙﹏⊙

那麼，這道題呢，重要的是掃描線（如圖）：
這裡寫圖片描述

那一根根藍或紅線就叫線（矩陣左右的線為紅，上下為藍，為什麼這樣分色，後面講），每根線其實都是某個矩陣上的一條邊。（註意，掃描線比較適合用於在矩陣的每條邊嚴格與X軸或Y軸平行或重合的矩陣問題上）

現在，把與X軸平行的線和與Y軸平行分開來。

同時，我們
規定，代表矩陣下麵和左邊的邊，為入邊，這些線權值為1，同時規定矩陣上面和右邊的邊，為出邊，這些線權值為-1，那麼代表一個矩陣的四根線權值加起來就為1了！

那麼，我們再定一條更厲害的動態線，叫掃描線，我們每次只用掃描線處理一種顏色的線，先掃紅色：
這裡寫圖片描述

這條掃描線上也被Y坐標分成一個個小格，每個格子一開始值為0。
每經過一條紅線，就將這條紅線與掃描線重疊部分加上這條線的權值。
如圖：
這裡寫圖片描述
現在，前面的權值就有用了（掃描線全部掃完後身上所有的格的值都為0）

當掃描線掃過出邊的時候，就把入邊的值給抵消了！

這裡寫圖片描述

然後在將藍線掃一遍就可以將全局的線用兩次掃描就掃完了！

那麼，怎麼統計答案呢？
暴力的話只需要統計當這個格子裡加為1和減為0的時，給答案加上這個格子離散前的長度（離散後長度為1）。（想想為什麼，很關鍵！）
但是，這樣暴力仍然為O（n^2）

於是，我們用線段樹讓他變為O（nlogn）

許多人就開始想lazy使時間變短，但是，其實，根本沒有lazy，只不過統計答案的方式與暴力不同而已！

給出代碼（離散化可以根據個人愛好改變）：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using  namespace  std;

const  int  cc=300000;//範圍 

struct  ndoe
{
    int  l,r,lc,rc,c,ss;//ss代表當前這個範圍被完整覆蓋了幾次 
}a[cc];int  len;//線段樹 

struct  caozuo
{
    int  x,l,r,k;//l與r為範圍，k為權值，x為用於排列的坐標
}tot1[cc],tot2[cc];//記錄線的信息，tot1為藍線,tot2為紅線 

struct  LSnode
{
    int  x,y;
}A[cc],B[cc];//離散值 

int  n,kk1,kk2,ys1[cc],ys2[cc];
//ys1[i]代表離散後編號為i的點與離散後編號為0的點離散前的長度是多少？ys2也一樣。
bool  cmp1(LSnode  x,LSnode  y){return  x.x<y.x;}//離散化的排列 

bool  cmp2(caozuo  x,caozuo  y){return  x.x!=y.x?x.x<y.x:x.k>y.k;}//將線按順序排起來，一個個改變掃描線的值，來模擬掃描線掃過去的場景 

void  bt(int  l,int  r)
{
    len++;int  now=len;
    a[now].l=l;a[now].r=r;a[now].c=a[now].lc=a[now].rc=0;
    if(l+1<r)//因為掃描線上每個格子長度為1，只有大於1才可以申請左右兒子來幫忙 
    {
        int  mid=(l+r)/2;
        a[now].lc=len+1;bt(l,mid);
        a[now].rc=len+1;bt(mid,r);//左兒子與右兒子 
    }
}//建樹 

void  update(int  x)
{
    if(a[x].ss!=0)a[x].c=ys1[a[x].r]-ys1[a[x].l];//離散前的長度
    else  a[x].c=a[a[x].lc].c+a[a[x].rc].c;//不行就繼承
}//統計答案的重點，註意，不用+=

void  change(int  now,int  l,int  r,int  k)
{
    if(a[now].l==l  &&  a[now].r==r){a[now].ss+=k;update(now);return  ;}//完全覆蓋直接統計 
    int  lc=a[now].lc,rc=a[now].rc,mid=(a[now].l+a[now].r)/2;
    if(r<=mid)change(lc,l,r,k);
    else  if(mid<=l)change(rc,l,r,k);
    else  change(lc,l,mid,k),change(rc,mid,r,k);//否則只能扔給左右兒子處理 
    //因為mid代表的坐標的是，所以不需要加一 
    update(now);//統計 
}

int  main()
{
    scanf("%d",&n);
    for(int  i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&A[i*2-1].x,&B[i*2-1].x,&A[i*2].x,&B[i*2].x);
        
        tot1[i*2-1].x=B[i*2-1].x;tot1[i*2].x=B[i*2].x;
        tot2[i*2-1].x=A[i*2-1].x;tot2[i*2].x=A[i*2].x;//給每條線的坐標(為什麼只給一個，因為另外的一個坐標是當作範圍來用的) 
        
        tot1[i*2-1].k=tot2[i*2-1].k=1;tot1[i*2].k=tot2[i*2].k=-1;//出邊與入邊 
        
        A[i*2-1].y=B[i*2-1].y=i*2-1;A[i*2].y=B[i*2].y=i*2;//離散化，A為tot1離散範圍，B為tot2離散。 
    }
    sort(A+1,A+n*2+1,cmp1);sort(B+1,B+n*2+1,cmp1);//排序 
    A[0].x=A[1].x-1,B[0].x=B[1].x-1; 
    
    for(int  i=1;i<=n*2;i++)
    {
        if(A[i].x!=A[i-1].x)
        {
            kk1++;
            ys1[kk1]=ys1[kk1-1]+A[i].x-A[i-1].x;
        }
        
        if(B[i].x!=B[i-1].x)
        {
            kk2++;
            ys2[kk2]=ys2[kk2-1]+B[i].x-B[i-1].x;//首碼和方便後面處理 
        }
        
        int  kkk_c1=A[i].y,kkk_c2=B[i].y;//分清這是範圍內的l還是r 
        
        if(kkk_c1%2==1)tot1[kkk_c1].l=tot1[kkk_c1+1].l=kk1;
        else  tot1[kkk_c1].r=tot1[kkk_c1-1].r=kk1;
        
        if(kkk_c2%2==1)tot2[kkk_c2].l=tot2[kkk_c2+1].l=kk2;
        else  tot2[kkk_c2].r=tot2[kkk_c2-1].r=kk2;
    }
    
    sort(tot1+1,tot1+2*n+1,cmp2);sort(tot2+1,tot2+2*n+1,cmp2);//將線掃一遍 
    
    int  ans=0,lastt=0;//關鍵！ 
    
    len=0;bt(1,kk1);//建樹 
    for(int  i=1;i<=n*2;i++)
    {
        lastt=a[1].c;//統計上次的答案 
        if(tot1[i].l!=tot1[i].r)change(1,tot1[i].l,tot1[i].r,tot1[i].k);//掃藍線 
        ans+=abs(a[1].c-lastt);//加個abs因為出邊會使答案變小，ans只記錄這次該變了什麼 
    }
    
    for(int  i=1;i<=kk2;i++)ys1[i]=ys2[i];//其實可以搞兩顆線段時，為了簡潔，只好這樣 
    
    len=0;bt(1,kk2);//建樹 
    for(int  i=1;i<=n*2;i++)
    {
        lastt=a[1].c;//統計上次的答案 
        if(tot2[i].l!=tot2[i].r)change(1,tot2[i].l,tot2[i].r,tot2[i].k);//掃紅線 
        ans+=abs(a[1].c-lastt);//加個abs因為出邊會使答案變小，ans只記錄這次該變了什麼
    }
    printf("%d\n",ans);//輸出 
    return  0;
}

大家是不是對

void  update(int  x)
{
    if(a[x].ss!=0)a[x].c=ys1[a[x].r]-ys1[a[x].l];//離散前的長度
    else  a[x].c=a[a[x].lc].c+a[a[x].rc].c;//不行就繼承
}//統計答案的重點 

——————————————————————————————————————————————————————————

int  ans=0,lastt=0;//關鍵！ 
    
len=0;bt(1,kk1);//建樹 
for(int  i=1;i<=n*2;i++)
{
    lastt=a[1].c;//統計上次的答案 
    if(tot1[i].l!=tot1[i].r)change(1,tot1[i].l,tot1[i].r,tot1[i].k);//掃藍線 
    ans+=abs(a[1].c-lastt);//加個abs因為出邊會使答案變小，ans只記錄這次該變了什麼
}

for(int  i=1;i<=kk2;i++)ys1[i]=ys2[i];//其實可以搞兩棵線段時，為了簡潔，只好這樣 

len=0;bt(1,kk2);//建樹 
for(int  i=1;i<=n*2;i++)
{
    lastt=a[1].c;//統計上次的答案 
    if(tot2[i].l!=tot2[i].r)change(1,tot2[i].l,tot2[i].r,tot2[i].k);//掃紅線 
    ans+=abs(a[1].c-lastt);//加個abs因為出邊會使答案變小，ans只記錄這次該變了什麼
}

不理解？
線段樹里的c代表這個線段樹節點所管理的掃描線範圍里有值的格子的長度（長度為離散前的長度）。
那麼，如果父親節點的ss!=0並且兒子節點的ss!=0，不就重覆了嗎，但是，我們仍然只算父親節點的區間，因為他包括了兒子節點的範圍，所以才加了個else。

因為有\[ans+=abs(a[1].c-lastt);\]這一句，和

void  update(int  x)
{
    if(a[x].ss!=0)a[x].c=ys1[a[x].r]-ys1[a[x].l];//離散前的長度
    else  a[x].c=a[a[x].lc].c+a[a[x].rc].c;//不行就繼承
}//統計答案的重點

所以，我們仔細觀察能發現一下結論。

如果一個掃描線的區間多次經過入邊，c值不變。
由於lastt記錄了上一次的根節點的值，所以沒變的c值不會被ans再次加入。
若某個掃描線的區間被出邊更改為0，繼承左右兒子的c值後，由於lastt值上一次幾錄了他是整個區間都被覆蓋的c值，這一次利用abs可以加到這次操作中由有值被減為0的區間值。
一次更改中，所有區間不會出現那邊減這邊加的情況，頂多某個加，或某個減（線的權值要麼為正，要麼為服，所以會出現這種情況！）
ss值一直為非負數！

那麼，根據1跟2結論，重覆計算不會出現，根據3跟4結論，出邊也有可能有影響。

那麼，大家會發現：
這裡寫圖片描述
這張圖上有一條出邊與入邊重合了，如果不判斷的話可能會出現中間這一條線的長度被計算兩次，那麼我們將入邊優先，出邊靠後就可以解決了！

bool  cmp2(caozuo  x,caozuo  y){return  x.x!=y.x?x.x<y.x:x.k>y.k;}
//x值不一樣按先後排序，不一樣按出入邊排序，但因為入邊權值大於出邊，所以可以這樣寫

由於計算這兩條線的時候這個區間的ss值一直大於0，所以c值也不變，ans值也不會記錄。

羅里吧嗦這麼一大堆，那麼這個為什麼對？，因為ans只在某個區間的ss值在變化為0或1時記錄答案，根本與暴力也是十分像的！
（ ·_·逃

這裡寫圖片描述