Codeforces 1401 E. Divide Square —— 線段樹

This way

題意：

有一個矩形在平面上，它的左下右上角是(0,0)，(1e6,1e6)

現在給你一些水準或者豎直的線段，在這個矩形内部并且至少有一端和這個矩形相交，問你這些線段将這個矩形分成多少個部分

題解：

我們枚舉每個豎直的線段，然後檢視它和多少個水準的線段相交，由于每個線段一定都和矩形相交，那麼這個線段在内部的相交數就是它的貢獻（這道題應該去年做到過）

并且兩端都與矩形相交的線段，它的貢獻會增加1.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5,M=1e6;
int sum[N*4];
unordered_map<int,vector<int> >sta,en;
struct node{
    int p,x,y;
    bool operator< (const node& a)const {
        return p<a.p;
    }
}h[N/10+5],v[N/10+5];
int b[N];
void update(int l,int r,int root,int p,int v){
    if(l==r){
        sum[root]+=v;
        return ;
    }
    int mid=l+r>>1;
    if(mid>=p)
        update(l,mid,root<<1,p,v);
    else
        update(mid+1,r,root<<1|1,p,v);
    sum[root]=sum[root<<1]+sum[root<<1|1];
}
int query(int l,int r,int root,int ql,int qr){
    if(l>=ql&&r<=qr)
        return sum[root];
    int mid=l+r>>1,ans=0;
    if(mid>=ql)
        ans=query(l,mid,root<<1,ql,qr);
    if(mid<qr)
        ans+=query(mid+1,r,root<<1|1,ql,qr);
    return ans;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&h[i].p,&h[i].x,&h[i].y);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&v[i].p,&v[i].x,&v[i].y);
        b[i]=v[i].p;
    }
    m++;
    v[m]={M,0,M};
    b[m]=1e6;
    sort(b+1,b+1+m);
    update(0,M,1,0,1),update(0,M,1,M,1);
    for(int i=1;i<=n;i++){
        if(h[i].x==0){
            h[i].x=1;
            h[i].y=upper_bound(b+1,b+1+m,h[i].y)-b-1;
        }

        else{
            h[i].x=lower_bound(b+1,b+1+m,h[i].x)-b;
            h[i].y=m-1;
        }


        //if(h[i].p==0||h[i].p==(int)1e6)continue;
        if(h[i].x<=h[i].y)
            sta[h[i].x].push_back(h[i].p),en[h[i].y].push_back(h[i].p);
    }
    sort(v+1,v+1+m);
    ll ans=0;
    for(int i=1;i<=m;i++){
        //if(n==100000&&i==m)break;
        for(auto j:sta[i])
            update(0,M,1,j,1);
        ans+=1ll*query(0,M,1,v[i].x,v[i].y)-1;
        for(auto j:en[i])
            update(0,M,1,j,-1);
    }
    printf("%lld\n",ans);
    return 0;
}