题意：给定一个n*m的平面，有k条垂直或平行的直线，问将平面分成了几个互不联通的部分

n，m<=1e9，k<=1e5

思路：

刻在DNA里的二维数点

#include
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair PII;
typedef pair Pll;
typedef vector VI;
typedef vector VII;
#define N 410000
#define M 4100000
#define fi first
#define se second
#define MP make_pair
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1

const ll MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int INF=1e9;
int da[]={-,,,};
int db[]={,,-,};

char ch[N][];
int t[N<<],x[N],y[N],c[N],p;

struct arr1
{
int t,x,y;
}a[N];

bool cmp1(arr1 a,arr1 b)
{
return a.t<b.t;
}

struct arr2
{
int x1,x2,y;
}b[N];

bool cmp2(arr2 a,arr2 b)
{
return a.y<b.y;
}

int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
}

int lisan(int x)
{
int l=,r=p,last=;
while(l<=r) { int mid=(l+r)>>;
if(c[mid]>x) r=mid-;
if(c[mid]==x){last=mid; r=mid-;}
if(c[mid]<x) l=mid+;
}
return last;
}

void build(int l,int r,int p)
{
t[p]=;
if(l==r) return;
int mid=(l+r)>>;
build(l,mid,ls);
build(mid+,r,rs);
}

int query(int l,int r,int x,int y,int p)
{
if(x<=l&&r<=y) return t[p]; int mid=(l+r)>>;
int s=;
if(x<=mid) s+=query(l,mid,x,y,ls); if(y>mid) s+=query(mid+,r,x,y,rs);
return s;
}

void update(int l,int r,int x,int v,int p)
{
if(l==r)
{
t[p]+=v;
return;
}
int mid=(l+r)>>;
if(x<=mid) update(l,mid,x,v,ls);
else update(mid+,r,x,v,rs);
t[p]=t[ls]+t[rs];
}

int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);

 int cas;  
 scanf("%d",&cas);

 while(cas--)  
 {  
     int n=read(),m=read(),K=read();  
     ll ans=;  
     int m1=,m2=;  
     p=;  
     rep(i,,K)  
     {  
         x\[i\]=read(),y\[i\]=read();  
         scanf("%s",ch\[i\]+);  
         //if(ch\[i\]\[1\]=='U'&&y\[i\]==) ans++;  
         //if(ch\[i\]\[1\]=='R'&&x\[i\]==1) ans++;  
         c\[++p\]=x\[i\];  
         c\[++p\]=y\[i\];  
     }  
     //printf("ans=%I64d\\n",ans);  
     c\[++p\]=n;  
     c\[++p\]=m;  
     c\[++p\]=;  
     sort(c+,c+p+);  
     rep(i,,K)  
     {  
         x\[i\]=lisan(x\[i\]);  
         y\[i\]=lisan(y\[i\]);  
     }  
     n=lisan(n),m=lisan(m);  
     rep(i,,K)  
     {  
         if(ch\[i\]\[\]=='U')  
         {  
             m1++;  
             a\[m1\].t=y\[i\];  
             a\[m1\].x=x\[i\];  
             a\[m1\].y=;  
             //a\[m1\].x=x\[i\];  
             //a\[m1\].y1=y\[i\];  
             //a\[m1\].y2=m;  
         }  
         if(ch\[i\]\[\]=='D')  
         {  
             m1++;  
             a\[m1\].t=;  
             a\[m1\].x=x\[i\];  
             a\[m1\].y=;

             m1++;  
             a\[m1\].t=y\[i\]+;  
             a\[m1\].x=x\[i\];  
             a\[m1\].y=-;  
             //a\[m1\].x=x\[i\];  
             //a\[m1\].y1=1;  
             //a\[m1\].y2=y\[i\];  
         }  
         if(ch\[i\]\[\]=='L')  
         {  
             m2++;  
             b\[m2\].x1=;  
             b\[m2\].x2=x\[i\];  
             b\[m2\].y=y\[i\];  
         }  
         if(ch\[i\]\[\]=='R')  
         {  
             m2++;  
             b\[m2\].x1=x\[i\];  
             b\[m2\].x2=n;  
             b\[m2\].y=y\[i\];  
         }  
     }  
     sort(a+,a+m1+,cmp1);  
     sort(b+,b+m2+,cmp2);  
     build(,p,);  
     int j1=,j2=;  
     rep(i,,p)  
     {  
         while(j1<=m1&&a\[j1\].t==i)  
         {  
             update(,p,a\[j1\].x,a\[j1\].y,);  
             j1++;  
         }  
         while(j2<=m2&&b\[j2\].y==i)  
         {  
             ans+=query(,p,b\[j2\].x1,b\[j2\].x2,);  
             j2++;  
         }  
     }  
     printf("%I64d\\n",ans+);

 }

 return ;  

}