hdu6681 Rikka with Cake(主席树)

题目链接
大意：给你一个矩形区域， $((0, 0) - (n, m))$ ，现在有k条直线，每条直线都是从一个点出发到上下左右四个方向之一。
问你这个区域被分成了多少块。
思路：稍微观察即可发现，分成的区域等于直线交点个数+1。
我们对 $L, R$ 方向的对纵坐标分开离散化建立主席树（横坐标放一起离散化），然后每次遍历 $U, D$ 方向的直线来在主席树上查询。
设当前横坐标为x
方向是U的话，那么L方向上横坐标x大于等于x的都为有效贡献，小于等于x的R方向都有贡献（纵坐标在范围内）。
方向的D的话，那么L方向上横坐标x大于等于x的都为有效贡献，小于等于x的R方向都有贡献（纵坐标在范围内）。
我们查询的时候分别对两个主席树进行查询，每次查询一个合法的纵坐标区间即可。
细节见代码

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 3e5 +11;
int t;
int n,m,k;
struct uzi
{
    int a,b;
    char c;
}p[N];
int a[N],b[N];
char c[N];
int cmp(uzi l,uzi r){
    return l.b<r.b;
}
struct fak{
    LL sum;
    int l,r;    
}T1[N*40],T2[N*40];
int n1,n2;
int t1[N],t2[N];
void up1(int l,int r,int &x,int y,int pos){
    T1[++n1]=T1[y];if(pos)T1[n1].sum++;x=n1;
    if(l==r)return ;
    int mid=l+r>>1;
    if(mid>=pos)up1(l,mid,T1[x].l,T1[y].l,pos);
    else up1(mid+1,r,T1[x].r,T1[y].r,pos);
}
void up2(int l,int r,int &x,int y,int pos){
    T2[++n2]=T2[y];if(pos)T2[n2].sum++;x=n2;
    if(l==r)return ;
    int mid=l+r>>1;
    if(mid>=pos)up2(l,mid,T2[x].l,T2[y].l,pos);
    else up2(mid+1,r,T2[x].r,T2[y].r,pos);
}
LL g1(int l,int r,int x,int y,int k){
    if(!x&&!y)return 0;
    if(r<k)return 0;
    if(l>=k)return T1[y].sum-T1[x].sum;;
    int mid=l+r>>1;
    return g1(l,mid,T1[x].l,T1[y].l,k)+g1(mid+1,r,T1[x].r,T1[y].r,k);
}
LL g2(int l,int r,int x,int y,int k){
    if(!x&&!y)return 0;
    if(l>k)return 0;
    if(r<=k)return (T2[y].sum-T2[x].sum);
    int mid=l+r>>1;
    return g2(l,mid,T2[x].l,T2[y].l,k)+g2(mid+1,r,T2[x].r,T2[y].r,k);
}
int PA[N],PB[N],La,Lb;
int main(){
    ios::sync_with_stdio(false);
    for(cin>>t;t;t--){
        cin>>n>>m>>k;
        n1=n2=0;
        La=0;Lb=0;
        for(int i=1;i<=k;i++){
            cin>>a[i]>>b[i]>>c[i];
            p[i]={a[i],b[i],c[i]};
            if(c[i]=='L')PA[++La]=b[i];
            if(c[i]=='R')PB[++Lb]=b[i];
        }
        sort(a+1,a+1+k);
        int r=unique(a+1,a+1+k)-a-1;
        sort(PA+1,PA+1+La);
        sort(PB+1,PB+1+Lb);
        La=unique(PA+1,PA+1+La)-PA-1;
        Lb=unique(PB+1,PB+1+Lb)-PB-1;
        for(int i=1;i<=k;i++){
            if(c[i]=='L'){
                p[i].b=lower_bound(PA+1,PA+1+La,p[i].b)-PA;
            }else if(c[i]=='R'){
                p[i].b=lower_bound(PB+1,PB+1+Lb,p[i].b)-PB;
            }
        }
        for(int i=1;i<=k;i++)p[i].a=lower_bound(a+1,a+1+r,p[i].a)-a;
        sort(p+1,p+1+k,cmp);
        for(int i=1;i<=k;i++){
            if(p[i].c=='L'){
                up1(0,r+1,t1[p[i].b],t1[p[i].b-1],p[i].a);
            }else if(p[i].c=='R'){
                up2(0,r+1,t2[p[i].b],t2[p[i].b-1],p[i].a);
            }
        }
        up1(0,r+1,t1[La+1],t1[La],0);
        up2(0,r+1,t2[Lb+1],t2[Lb],0);
        LL A=0;
        for(int i=1;i<=k;i++){
            if(p[i].c=='U'){
                int quL=lower_bound(PA+1,PA+1+La,p[i].b)-PA;
                int quR=lower_bound(PB+1,PB+1+Lb,p[i].b)-PB;
                A+=g1(0,r+1,t1[quL-1],t1[La+1],p[i].a);
                A+=g2(0,r+1,t2[quR-1],t2[Lb+1],p[i].a);
            }else if(p[i].c=='D'){
                int quL=upper_bound(PA+1,PA+1+La,p[i].b)-PA;
                int quR=upper_bound(PB+1,PB+1+Lb,p[i].b)-PB;    
                quL--;
                quR--;
                A+=g1(0,r+1,0,t1[quL],p[i].a);
                A+=g2(0,r+1,0,t2[quR],p[i].a);
            }
        }
        cout<<A+1<<endl;
    }
    return 0;
}