#P5606. Sgu177 Square

    ID: 4607 传统题 1000ms 512MiB 尝试: 3 已通过: 1 难度: 5 上传者: 标签>难度分类普及+/提高-构造与建模逆向思考数据结构普通并查集路径压缩按大小合并模拟与实现技巧添加哨兵CF1700

Sgu177 Square

SGU177 Square

题目描述

一个 N×NN\times N 的方格板,左上格坐标为 (1,1)(1,1),右下格坐标为 (N,N)(N,N)。起初每格都是白色。

依次执行 MM 次涂色。每次给出两个对角格和一种颜色,把它们确定的矩形内所有格子涂成指定颜色,两个对角格及矩形边界上的格子也包含在内。再次涂色会覆盖原颜色。

输入格式

第一行两个整数 N,MN,M,满足 1≤N≤10001\le N\le1000、1≤M≤50001\le M\le5000。

接下来 MM 行每行五项 x1,y1,x2,y2,cx_1,y_1,x_2,y_2,c。四个坐标均为 [1,N][1,N] 内的整数,两个对角格可以按照任意顺序给出。字符 b 表示黑色,w 表示白色。

输出格式

输出一个整数,为全部涂色完成后白色格子的个数。

样例 1

9 6
2 2 4 6 b
4 3 3 3 w
6 2 8 6 b
5 3 6 9 w
8 3 9 9 w
1 5 3 5 w
63