[TIOJ 1224][HOJ 12] 矩形覆蓋面積計算 / 矩形面積覆蓋

作法：

原本以為會蠻好寫的就一直沒來寫這個，想說反正就掃描線+線段樹嘛~應該沒甚麼困難的，結果真正要寫的時後發現線段樹的部分好難想OAO 參考了這篇然後想了很久之後才知道線段樹怎麼作的。

掃描線的部分就不再多講，可以參考上面的網站XD，重點是線段樹的地方，這會等價於我們需要對一個陣列作「區間加(減)一個值」和「區間查詢有幾個值非0」，並且初使時整個陣列都是0。

用到區間加值當然可以想到懶人標記，但這時候會發現如果 ST[id] 直接存這個區間的答案的話會杯具，例如在對這個區間減值的時候，減完就不知道這個區間到底剩幾個非0的數了，必須遞回下去把左子樹根右子樹重算一遍，這樣如果考慮一直對同一個線段 +1 -1 +1 -1 ...... 的話，會讓單次修改的時間高達O(n)。

所以線段樹上不能直接存這個區間的答案。根據我對上面那篇連結裡的 code 的理解，想像現在有個線段樹，有好幾個區間有 tag ，把ST[ id ] 代表的區間叫作 [ L,R ] 好了，那麼 ST[ id ] 存的就是「考慮 id 的子孫們(不含 id 本身)的所有 tag 值，想像有另一個陣列 b[ L ] ~ b[ R ]，他們只有被剛才那些 tag 作用過，那麼  b[ L ] ~ b[ R ] 之間有幾個數非0」。這樣就能成功對區間加減值並且維護好線段樹上的值了，真是太神奇了OAO，然後每次修改之後 ST[ 1 ] 就是所求的答案了。詳細維護 ST[ id ] 作法就看 code 吧。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
struct P
{
    int x,d,u,val ;
    bool operator < (const P &rhs) const
    {
        return x<rhs.x ;
    }
}a[200000+10];
 
int ST[5*maxn],tag[5*maxn] ;
 
void modify(int l,int r,int L,int R,int id,int val)
{
    if(l==L && r==R) { tag[id]+=val ; return ; }
    int mid=(L+R)/2 ;
    if(r<=mid) modify(l,r,L,mid,2*id,val) ;
    else if(l>mid) modify(l,r,mid+1,R,2*id+1,val) ;
    else
        modify(l,mid,L,mid,2*id,val) ,
        modify(mid+1,r,mid+1,R,2*id+1,val) ;
    ST[id]= (tag[2*id] ? mid-L+1 : ST[2*id]) +
            (tag[2*id+1] ? R-mid : ST[2*id+1]) ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=0;i<n;i++)
    {
        int x1,y1,x2,y2 ;
        scanf("%d%d%d%d",&x1,&x2,&y1,&y2) ;
        a[2*i]=(P){x1,y1,y2-1,1} ;
        a[2*i+1]=(P){x2,y1,y2-1,-1} ;
    }
    sort(a,a+2*n) ;
 
    int x=0 , val=0 ;
    LL ans=0LL ;
    for(int i=0;i<2*n;i++)
    {
        ans+= (LL) (a[i].x-x)*val ;
        modify(a[i].d,a[i].u,0,maxn-1,1,a[i].val) ;
        x=a[i].x ;
        val=ST[1] ;
    }
    printf("%lld\n",ans) ;
}