题意:

在一个封闭的n*m的矩形内，有k条射线，有四个方向，上下左右，射线，射线的端点不重合，该矩形内有多少个封闭的区域
1 ≤ n , m ≤ 1 e 9 , 1 ≤ k ≤ 1 e 5 1\le n,m \le 1e9 ,1\le k \le 1e5 1≤n,m≤1e9,1≤k≤1e5
没有任意两个个端点的x坐标 或 y坐标相同

题解：

看图不难观察到 当横向的线与纵向的线产生一个交点的时候,封闭的区域就会增加1
于是我们只需要求交点有多少
我的做法是
先离散化x坐标和y坐标
将所有点按y坐标从小到大排序
从小到大，然后对于横向的线根据方向进行对相应的区间加1 然后对于纵向向下的射线对其所在的x坐标，进行单点查询，我们就可以知道这条纵向的线一共贡献了多少个交点
再建一次线段树，从大到小，再进行区间更新，对于纵向向上的射线进行查询即可
交点的个数为c，答案就是c+1

AC_code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define maxn 100005
int n, m, k;
struct ss {
	int x, y;
	char fx;
} point[maxn];
bool cmp(ss aa, ss bb) {
	return aa.y < bb.y;
}

/*线段数模板*/

struct node {
	int l,r;
	ll lazy;
} tree[maxn * 4]; // 开四倍大小

void push_up(int root) {
	tree[root].sum = tree[root << 1].sum + tree[(root << 1) | 1].sum;
}   // 儿子的值相加为父亲的值

void push_down(int root) {
	if(tree[root].lazy) { //有懒惰值
		tree[root << 1].lazy += tree[root].lazy;
		tree[(root << 1) | 1].lazy += tree[root].lazy;//向下传递懒惰值
		tree[root << 1].sum += tree[root].lazy * (tree[root << 1].r - tree[root << 1].l + 1);
		tree[(root << 1) | 1].sum += tree[root].lazy * (tree[(root << 1) | 1].r - tree[(root << 1) | 1].l + 1); //根据题目要求处理
		tree[root].lazy = 0;
	}
}

}

void build_tree(int l,int r,int root) {
	tree[root].lazy = 0;
	tree[root].l = l;
	tree[root].r = r;
	if(l == r) {
		tree[root].sum = 0; // 这里给一个初始值
		return ;
	}
	int mid = (l + r) >> 1;
	build_tree(l,mid,root << 1);
	build_tree(mid + 1,r,(root << 1) | 1);
	push_up(root); //向上更新值
}

void update_interval(int l,int r,int v,int root) { //区间更新
	if(l <= tree[root].l && r >= tree[root].r) {
		tree[root].lazy += v; // 保存懒惰值
		tree[root].sum += v;
		return ;
	}
	if(tree[root].lazy)
		push_down(root);
	int mid = (tree[root].l + tree[root].r) >> 1;
	if(l <= mid)
		update_interval(l,r,v,root << 1);
	if(r > mid)
		update_interval(l,r,v,(root << 1) | 1);
	push_up(root);
}

int query_single(int p,int root) { //单点查询
	if(tree[root].l == tree[root].r && tree[root].r == p) {
		return tree[root].sum;
	}
	if(tree[root].lazy)
		push_down(root);
	int mid = (tree[root].l + tree[root].r) >> 1;
	if(p <= mid)
		query_single(p,root << 1);
	else
		query_single(p,(root << 1) | 1);
}
int a[maxn], b[maxn];
int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		int cnta = 0, cntb = 0;
		scanf("%d %d %d", &n, &m, &k);
		for(int i = 0; i < k; i++) {
			scanf("%d %d %c",&point[i].x, &point[i].y, &point[i].fx);
			a[++cnta] = point[i].x;
			b[++cntb] = point[i].y;
		}
		sort(a+1, a+cnta+1);
		sort(b+1, b+cntb+1);
		int lena = unique(a+1, a+cnta+1) - a + 1;
		int lenb = unique(b+1, b+cntb+1) - b + 1;
		for(int i = 0; i < k; i++) {
			point[i].x = lower_bound(a+1, a+cnta+1, point[i].x) - a;
			point[i].y = lower_bound(b+1, b+cntb+1, point[i].y) - b;
		}
		sort(point, point+k, cmp);
		build_tree(0, lena+1, 1);
		ll ans = 1;
		for(int i = 0; i < k; i++) {
			if(point[i].fx == 'L') {
				update_interval(0, point[i].x, 1, 1);
			} else if(point[i].fx == 'R') {
				update_interval(point[i].x, lena+1, 1, 1);
			} else if(point[i].fx == 'D') {
				ans += query_single(point[i].x, 1);
			}
		}
		build_tree(0, lena+1, 1);
		for(int i = k-1; i >= 0; i--) {
			if(point[i].fx == 'L') {
				update_interval(0, point[i].x, 1, 1);
			} else if(point[i].fx == 'R') {
				update_interval(point[i].x, lena+1, 1, 1);
			} else if(point[i].fx == 'U') {
				ans += query_single(point[i].x, 1);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}