hdu 6681 Rikka with Cake(扫描线)

题意：给你一个n*m的的矩形框 现在又k条射线 问这个矩形框会被分为多少个区域

思路：之前的想法是枚举边界然后线段树扫一遍计算一下矩形个数 复杂度果断不行 后面发现其实答案就是交点数+1 然后就用线段树上下扫两边

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const int N = 1e5+7;
const int inf = 0x3f3f3f3f;
typedef long long ll;
const ll mod = 1e7+9;
struct tree{
    int l,r,v;
};
tree t[N<<2];
struct node{
    int x,y,z;
}up[N],down[N];
int xx[N]; 
bool cmp1(node a,node b){
    return a.y<b.y; //升
}
bool cmp2(node a,node b){
    return a.y>b.y; //降 
}
void build(int p,int l,int r){
    t[p].l=l; t[p].r=r; t[p].v=0;
    if(l==r){
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    t[p].v=t[p<<1].v+t[p<<1|1].v;
    
}
void update(int p,int x,int v){
    if(t[p].l==t[p].r&&t[p].l==x){
        t[p].v+=v;
        return ;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid) update(p<<1,x,v);
    else update(p<<1|1,x,v);
    t[p].v=t[p<<1].v+t[p<<1|1].v;
}
ll query(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].v;
    }
    int mid=(t[p].l+t[p].r)>>1;
    ll res=0;
    if(l<=mid) res+=query(p<<1,l,r);
    if(r>mid) res+=query(p<<1|1,l,r);
    return res;
}
int getpo(int x,int n){
    int po=lower_bound(xx,xx+n,x)-xx+1;
    return po;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; cin>>t;
    while(t--){
        int n,m,k; cin>>n>>m>>k;
        int cnt=0; int cntup=0; int cntdown=0;
        xx[cnt++]=1; xx[cnt++]=n-1;
        for(int i=1;i<=k;i++){
            int x,y; char ty;
            cin>>x>>y>>ty;
            xx[cnt++]=x;
            if(ty=='U'){
                up[cntup++]=node{x,y,1};
            }else if(ty=='D'){
                down[cntdown++]=node{x,y,1};
            }else if(ty=='L'){
                up[cntup++]=node{x,y,0};
                down[cntdown++]=node{x,y,0};
            }else{
                up[cntup++]=node{x,y,3};
                down[cntdown++]=node{x,y,3};
            }
        }
        sort(xx,xx+cnt);
        cnt=unique(xx,xx+cnt)-xx;
        sort(up,up+cntup,cmp1);
        sort(down,down+cntdown,cmp2);
        build(1,1,cnt);
        ll ans=1;
        for(int i=0;i<cntup;i++){
            if(up[i].z==1){
                int po=getpo(up[i].x,cnt);
                update(1,po,1);
            }else if(up[i].z==0){
                int l=getpo(1,cnt); int r=getpo(up[i].x,cnt);
                ans+=query(1,l,r);
            }else{
                int l=getpo(up[i].x,cnt); int r=getpo(n-1,cnt);
                ans+=query(1,l,r);
            }
        }
        build(1,1,cnt);
        for(int i=0;i<cntdown;i++){
            if(down[i].z==1){
                int po=getpo(down[i].x,cnt);
                update(1,po,1);
            }else if(down[i].z==0){
                int l=getpo(1,cnt); int r=getpo(down[i].x,cnt);
                ans+=query(1,l,r);
            }else{
                int l=getpo(down[i].x,cnt); int r=getpo(n-1,cnt);
                ans+=query(1,l,r);
            }
        }
        cout<<ans<<endl;
    }
}