#P6877. c

    ID: 6708 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-连续区间压缩二叉堆懒删除离线查询事件排序树状数组

c

题目描述

给定一个 NN 行 MM 列的棋盘,初始时所有格子的颜色编号为 00。按输入顺序执行 KK 次染色。每次选定一段连续的行或列,将这些行或列中的全部格子刷成指定颜色。后执行的操作覆盖先前的颜色。

求全部染色完成后,符合要求且颜色相同的无序格子对数。若 q=1q=1,共边或只共角的两个格子都纳入统计。若 q=0q=0,只统计共边的两个格子。

输入格式

第一行四个整数 N,M,K,qN,M,K,q。

接下来 KK 行,每行四个整数 Typei,Li,Ri,CiType_i,L_i,R_i,C_i。若 Typei=0Type_i=0,则把第 LiL_i 至第 RiR_i 行全部刷成颜色 CiC_i。若 Typei=1Type_i=1,则把第 LiL_i 至第 RiR_i 列全部刷成颜色 CiC_i。行和列从 11 开始编号,区间包含两个端点。

输出格式

输出一行一个整数,表示符合要求的格子对数。

样例

3 4 3 1
0 2 3 2
1 3 3 0
1 2 2 1
8

数据范围

原 PDF 将数据范围列在单独的附件中。现有 20 组评测数据中,N,M,KN,M,K 最大均为 10510^5,颜色编号在 [0,105][0,10^5] 内,Typei,q∈{0,1}Type_i,q\in\{0,1\}。行操作满足 1≤Li≤Ri≤N1\le L_i\le R_i\le N,列操作满足 1≤Li≤Ri≤M1\le L_i\le R_i\le M。

by 杨景钦

原 PDF 题面