CCF计算机软件能力认证第29次考试求助

模拟考试链接：http://118.190.20.162/home.html

T1——田地丈量(100)

矩阵求交

问题描述

西西艾弗岛上散落着n块田地。每块田地可视为平面直角坐标系下的一块矩形区域，由左下角坐标 (x1,y1) 和右上角坐标 (x2,y2) 唯一确定，且满足 x1<x2、y1<y2。这n块田地中，任意两块的交集面积均为0，仅边界处可能有所重叠。
最近，顿顿想要在南山脚下开垦出一块面积为 a×b 矩形田地，其左下角坐标为 (0,0)、右上角坐标为 (a,b)。试计算顿顿选定区域内已经存在的田地面积。

输入格式

从标准输入读入数据。
输入共 n+1 行。
输入的第一行包含空格分隔的三个正整数 n、a 和 b，分别表示西西艾弗岛上田地块数和顿顿选定区域的右上角坐标。
接下来 n 行，每行包含空格分隔的四个整数 x1、y1、x2 和 y2，表示一块田地的位置。

输出格式

输出到标准输出。
输出一个整数，表示顿顿选定区域内的田地面积。

样例输入

4 10 10
0 0 5 5
5 -2 15 3
8 8 15 15
-2 10 3 15

样例输出

44

样例解释

如图所示，选定区域内田地（绿色区域）面积为 44。

子任务

全部的测试数据满足 n≤100，且所有输入坐标的绝对值均不超过 10**4。

def main():
    n, a, b = list(map(int, input().split()))
    ans = 0
    for _ in range(n):
        x1, y1, x2, y2 = list(map(int, input().split()))
        ans += intersection(x1, y1, x2, y2,a,b)
    print(ans)

def intersection(x1, y1, x2, y2,a,b):  # 和(0,0),(a,b)的交集
    w = max(min(a, x2) - max(0, x1), 0)
    h = max(min(b, y2) - max(0, y1), 0)
    return w * h

if __name__=='__main__':
    main()

# input:
# 4 10 10
# 0 0 5 5
# 5 -2 15 3
# 8 8 15 15
# -2 10 3 15

# output:
# 44

T2——垦田计划

二分法

问题描述

顿顿总共选中了n块区域准备开垦田地，由于各块区域大小不一，开垦所需时间也不尽相同。据估算，其中第 i 块（1≤i≤n）区域的开垦耗时为 t_i 天。这 n 块区域可以同时开垦，所以总耗时t_total 取决于耗时最长的区域，即：t_total =max{t_1,t_2,⋯,t_n}
为了加快开垦进度，顿顿准备在部分区域投入额外资源来缩短开垦时间。具体来说：

在第 i 块区域每投入 c_i 单位资源，便可将其开垦耗时缩短 1 天；

耗时缩短天数以整数记，即第 i 块区域投入资源数量必须是 c_i 的整数倍；

在第 i 块区域最多可投入 c_i ×(t_i−k) 单位资源，将其开垦耗时缩短为 k 天；

这里的 k 表示开垦一块区域的最少天数，满足 0<k≤min{t_1,t_2,⋯,t_n}；换言之，如果无限制地投入资源，所有区域都可以用k天完成开垦。

现在顿顿手中共有m单位资源可供使用，试计算开垦n块区域最少需要多少天？

输入格式

从标准输入读入数据。
输入共 n+1 行。
输入的第一行包含空格分隔的三个正整数 n、m 和 k，分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。
接下来 n 行，每行包含空格分隔的两个正整数 t_i 和 c_i，分别表示第 i块区域开垦耗时和将耗时缩短 1 天所需资源数量。

输出格式

输出到标准输出。
输出一个整数，表示开垦 n 块区域的最少耗时。

样例输入1

4 9 2
6 1
5 1
6 2
7 1

样例输出1

5

样例解释

如下表所示，投入 5 单位资源即可将总耗时缩短至 5 天。此时顿顿手中还剩余 4 单位资源，但无论如何安排，也无法使总耗时进一步缩短。

i	基础耗时t_i	缩减 1 天所需资源c_i	c_i投入资源数量	实际耗时
1	6	1	1	5
2	5	1	0	5
3	6	2	2	5
4	7	1	2	5

子任务

70% 的测试数据满足：0<n,t_i,c_i<=100 且 0<m<=106；
全部的测试数据满足：0<n,t_i,c_i≤10**5 且 0<m<=109。

def main():
    n, m, k = list(map(int, input().split()))

    time, source = [], []
    for _ in range(n):
        t, c = list(map(int, input().split()))
        time.append(t)
        source.append(c)
    left, right = k, max(time) #最少天数和最大天数

    def check(x):
        need = 0
        for t, c in zip(time, source):
            if t < x: continue
            need += (t - x) * c
        return need <= m
    ans = k
    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    print(ans)

if __name__ == '__main__':
    main()

# input:
# 4 9 2
# 6 1
# 5 1
# 6 2
# 7 1

# output:
# 5

T3——LDAP(100)

大模拟+BNF文法+hash

题目背景

西西艾弗岛运营公司是一家负责维护和运营岛上基础设施的大型企业，拥有数千名员工。公司内有很多 IT 系统。为了能够实现这些 IT 系统的统一认证登录，公司 IT 部门决定引入一套 LDAP 系统来管理公司内的用户信息。轻型目录访问协议（Lightweight Directory Access Protocol，LDAP）是一种用于访问和维护目录服务的应用层协议，基于它的数据库可以用树形结构来组织和存储数据。每一笔数据，都包含了一个唯一的标识符（DN，Distinguished Name），以及一系列的属性（Attribute）。
不同的 IT 系统，允许访问的用户是不相同的。每个信息系统都有一个表达式，用来描述允许访问的用户。
这个表达式可以按照某一个属性的值作为条件来匹配用户，也可以用多个条件的逻辑组合来匹配用户。
小 C 被安排来实现这样一个算法，给定一个 IT 系统的匹配表达式，找到所有与之匹配的用户的 DN。

问题描述

为了简化该问题，我们约定，每个用户的 DN 是一个正整数，且不会重复。有若干种用户的属性，用正整数编号。每个用户可以具有这些属性中的若干个，且每个属性只能有一个值。每个属性的值也是一个正整数。例如，假定有两个用户：用户 1 和用户 2，他们的 DN 分别是 1 和 2。一共有 3 种属性。用户 1 具有属性 1 和属性 2，且属性 1 的值为 2，属性 2 的值为 3；但不具有属性 3。用户 2 具有属性 2 和属性 3，且属性 2 的值为 3，属性 3 的值为 1；但不具有属性 1。如下表所示：

DN	属性 1	属性 2	属性 3
1	2	3	N/A
2	N/A	3	1

一个匹配表达式可以是一个属性的值，也可以是多个匹配表达式的逻辑组合。只匹配一个属性的值的表达式称为原子表达式，原子表达式的形式为 <属性编号><操作符><属性值>。其中操作符有两种：断言与反断言。断言操作符为 :，表示匹配具有该属性且值与之相等的用户；反断言操作符为 ~，表示匹配具有该属性且值与之不等的用户。例如，表达式 1:2 可以与上述用户 1 相匹配，但不能与用户 2 相匹配；而表达式 3~1则不能与任何一个用户相匹配。
表达式可以进行逻辑组合，其语法是：<操作符>(表达式 1)(表达式 2)。其中操作符有两种：与（&）和或（|）。如果操作符为与，则当且仅当两个表达式都与某一用户相匹配时，该表达式与该用户相匹配；如果操作符为或，则当且仅当两个表达式中至少有一个与某一用户相匹配时，该表达式与该用户相匹配。例如，表达式 &(1:2)(2:3) 可以与用户 1 相匹配，但不能与用户 2 相匹配；而表达式 |(1:2)(3:1) 则可以与两个用户都相匹配。
形式化地，上述语法用 BNF 范式表示如下：

NON_ZERO_DIGIT =  "1" / "2" / "3" / "4" / 
                  "5" / "6" / "7" / "8" / "9"
DIGIT          =  "0" / NON_ZERO_DIGIT
NUMBER         =  NON_ZERO_DIGIT / (NON_ZERO_DIGIT DIGIT*)
ATTRIBUTE      =  NUMBER
VALUE          =  NUMBER
OPERATOR       =  ":" / "~"
BASE_EXPR      =  ATTRIBUTE OPERATOR VALUE
LOGIC          =  "&" / "|"
EXPR           =  BASE_EXPR / (LOGIC "(" EXPR ")" "(" EXPR ")")

EASY_EXPR      =  BASE_EXPR / 
                  (LOGIC "(" BASE_EXPR ")" "(" BASE_EXPR ")")

输入格式

从标准输入读入数据。
输入的第一行包含一个正整数n，表示用户的数目。
接下来n行，每行包含空格分隔的若干个正整数，第一个正整数表示该用户的DN，第二个正整数表示该用户具有的属性个数，此后的每两个正整数表示该用户具有的一个属性及其值。这些属性按照属性编号从小到大的顺序给出。
接下来一行包含一个正整数m，表示匹配表达式的数目。
接下来m行，每行包含一个匹配表达式。

输出格式

输出到标准输出。
输出m行，每行包含零个或多个正整数，用空格分隔，表示与对应的匹配表达式相匹配的用户的 DN，由小到大排序。

样例输入1

2
1 2 1 2 2 3
2 2 2 3 3 1
4
1:2
3~1
&(1:2)(2:3)
|(1:2)(3:1)

样例输出1

1

1
1 2

样例解释

本组输入是题目描述中的例子。

子任务

对于 20% 的输入，有 1≤n≤100，1≤m≤10，每个用户的属性个数不超过 10，全部属性编号不超过 100，且表达式是原子表达式，即符合 BNF 语法 BASE_EXPR。
对于 40% 的输入，有 1≤n≤100，每个用户的属性个数不超过 10，全部属性编号不超过 100，且表达式中至多含有两个原子表达式的逻辑组合，即符合 BNF 语法 EASY_EXPR。
对于 70% 的输入，有全部属性编号不超过 500。
对于全部输入，有 1≤n≤2500，1≤m≤500，每个用户的属性个数不超过 500，全部属性编号、属性值和 DN 均不超过 109，每个表达式语句都符合题设语法，且语句字符长度不超过 2000。

class people:
    def __init__(self, id, attribute_num, attribute):
        self.id = id
        self.attribute_num = attribute_num
        self.attribute = attribute

def parse_non_zero_digit(s, i):
    if i < len(s) and s[i] in "123456789":
        return s[i], i + 1
    else:
        raise ValueError("Expected a non-zero digit")

def parse_digit(s, i):
    if i < len(s) and s[i].isdigit():
        return s[i], i + 1
    else:
        raise ValueError("Expected a digit")

def parse_number(s, i):
    digit, i = parse_non_zero_digit(s, i)
    number = digit
    while True:
        try:
            digit, i = parse_digit(s, i)
            number += digit
        except ValueError:
            break
    return int(number), i

def parse_attribute(s, i):
    return parse_number(s, i)

def parse_value(s, i):
    return parse_number(s, i)

def parse_operator(s, i):
    if i < len(s) and s[i] in ":~":
        return s[i], i + 1
    else:
        raise ValueError("Expected an operator")

def parse_base_expr(s, i):
    attribute, i = parse_attribute(s, i)
    operator, i = parse_operator(s, i)
    value, i = parse_value(s, i)
    return (attribute, operator, value), i

def parse_logic(s, i):
    if i < len(s) and s[i] in "&|":
        return s[i], i + 1
    else:
        raise ValueError("Expected a logic operator")

def parse_expr(s, i):
    if i < len(s) and s[i] in "123456789":
        return parse_base_expr(s, i)
    elif i < len(s) and s[i] in "&|":
        logic, i = parse_logic(s, i)
        if s[i] != '(':
            raise ValueError("Expected '('")
        i += 1
        left, i = parse_expr(s, i)
        if s[i] != ')':
            raise ValueError("Expected ')'")
        i += 1
        if s[i] != '(':
            raise ValueError("Expected '('")
        i += 1
        right, i = parse_expr(s, i)
        if s[i] != ')':
            raise ValueError("Expected ')'")
        i += 1
        return (logic, left, right), i
    else:
        raise ValueError("Expected an expression")

def parse_expression(s): # s分解为前缀表达式的树：operator, first_expr, second_expr这种结构
    expression, i = parse_expr(s, 0)
    if i != len(s):
        raise ValueError("Unexpected characters at the end of the string")
    return expression

def evaluate_expression(expression, person):
    if isinstance(expression[0], str):
        operator, first_expr, second_expr = expression
        result1 = evaluate_expression(first_expr, person)
        result2 = evaluate_expression(second_expr, person)
        if operator == '&':
            return result1 and result2
        elif operator == '|':
            return result1 or result2
    else:
        attribute, operator, value = expression
        attribute = attribute
        value = value
        if operator == ':':
            return attribute in person.attribute and person.attribute[attribute] == value
        elif operator == '~':
            return attribute in person.attribute and person.attribute[attribute] != value

def main():
    n = int(input())
    people_list = []
    for _ in range(n):
        ss = list(map(int, input().split()))
        id = ss[0]
        attribute_num = ss[1]
        nums = ss[2:]
        attribute = {}
        for i in range(0, len(nums), 2):
            attribute[nums[i]] = nums[i + 1]
        people_list.append(people(id, attribute_num, attribute))
    m = int(input())
    for i in range(m):
        expression = input()
        parsed_expression = parse_expression(expression)
        matching_users = sorted([person.id for person in people_list if evaluate_expression(parsed_expression, person)])
        print(*matching_users)

if __name__ == '__main__':
    main()

# input:
# 2
# 1 2 1 2 2 3
# 2 2 2 3 3 1
# 4
# 1:2
# 3~1
# &(&(1:2)(2:3))(|(1:2)(3:1))
# |(1:2)(3:1)

# output
# 1
#
# 1
# 1 2

T4——星际网络II (45)

模拟+区间分配+区间合并

问题描述

随着星际网络的进一步建设和规模的增大，一个新的问题出现在网络工程师面前——地址空间不够用了！原来，星际网络采用了传统的IPv6协议，虽然有 2**128 级别的可用地址数量，但面对广袤无垠的宇宙和爆炸式增长的网络用户数，如此庞大的地址空间也面临了用尽的那一天。
新的通信协议的研发工作交给了著名的网络科技圣地——西西艾弗星。最终，经过2333年的不懈努力，西西艾弗星的工程师们设计出了一种新的协议——“西西艾弗IP协议”，又称IPxxaf。
在IPxxaf协议中，一个地址由 n 位二进制位组成，其中 n 是 16 的倍数。日常表示一个地址时，采用类似IPv6协议的十六进制表示法，每 4 位用 : 隔开。如 n=32 时，地址为 2a00:0001 ，即表示一个二进制为 0010 1010 0000 0000 0000 0000 0000 0001 的地址。注意不会出现IPv6中省略每组的前导 0 或用 :: 省略一段 0 的情况。
为方便起见，记 num(s) 为地址 s 按高位在前、低位在后组成的n位二进制数，称一段“连续的地址“为 num(s) 成一段连续区间的一系列地址。
西西艾弗星的网络管理员负责地址的分配与管理。最开始，整个地址空间都是未分配的。用户可以随时向管理员申请一些地址：
1 id l r：表示用户 id 申请地址在 l∼r 范围内（包含 l 和 r，下同）的一段连续地址块。
在地址申请操作中，管理员需要先检查地址是否可用。如果用户申请的地址全部未被分配，则检查通过；若地址中存在已经分配给其他用户的地址，则检查失败。
但有一种特殊情况：申请的地址中没有已经分配给其他用户的地址，但含有一些先前已分配给该用户本人的地址。此时可以认为检查通过，但若申请的地址先前已全部分配给该用户则检查失败。
如果上述检查通过，则管理员向用户返回 YES，并将申请的地址分配给该用户；若不通过，则向用户返回 NO，同时不改变现有的地址分配。
网络管理员要定期检查地址的分配情况，具体而言有如下两种操作：
2 s：检查地址 s 被分配给了哪个用户。若未被分配，则结果为 0。
3 l r：检查 l∼r 范围内的所有地址是否完整地分配给了某个用户。若是，回答该用户的编号；若否，回答 0。
在整个网络的运行过程中，共出现了 q 次申请地址和检查地址分配的操作。作为西西艾弗星的一名重要的网络技术顾问，你要帮网络管理员依次处理每个操作，并回答相应的结果。

输入格式

从标准输入读入数据。
第一行，2 个正整数 n,q。
接下来 q 行，每行一个操作，格式如上所述，其中的 id 为正整数，l,r,s 均为IPxxaf地址串，其中十六进制均用数字和小写字母表示。

输出格式

输出到标准输出。
输出 q 行，每行一个非负整数或字符串，表示此次操作的结果。
其中，对于操作 1 ，输出 YES 或 NO；对于操作 2,3，输出一个非负整数。

样例输入1

32 12
1 1 0001:8000 0001:ffff
2 0001:a000
3 0001:c000 0001:ffff
1 2 0000:0000 000f:ffff
2 0000:1000
1 1 0001:8000 0001:8fff
1 2 0000:0000 0000:ffff
2 0000:1000
1 1 0002:8000 0002:ffff
3 0001:8000 0002:ffff
1 1 0001:c000 0003:ffff
3 0001:8000 0002:ffff

样例输出1

YES
1
1
NO
0
NO
YES
2
YES
0
YES
1

样例解释

第 4 个操作时，由于用户 2 申请的部分地址已被分配给用户 1，因此申请不通过；
第 6 个操作时，由于用户 1 申请的全部地址已被分配给用户 1，因此申请不通过；
第 11 个操作时，用户 1 申请的部分地址已被分配给用户 1，其余地址尚未被分配，申请通过；

数据范围

对于所有数据，n≤512, q≤5×10**4，n 为 16 的倍数，id≤q，对于操作 1,3 保证 num(l)<=num®。

测试点编号	n≤	q≤	特殊性质
1∼4	16	200	无
5∼6	64	200	无
7∼9	512	200	无
10∼11	16	20000	无
12∼13	64	50000	无
14∼16	512	50000	所有操作 1 的 id 互不相同
17∼20	512	50000	无

代码

from collections import defaultdict


def main():
    n, q = list(map(int, input().split()))

    address = defaultdict(list)

    address[0] = [(0, pow(2, n) - 1)]  # id为0的地址段,表示空闲地址

    for i in range(q):
        s = input().split()
        if s[0] == '1':  # 分配地址
            id = int(s[1])
            l, r = num(s[2]), num(s[3])
            ans = alloc(id, l, r,address)
            if ans:
                print('YES')
            else:
                print('NO')
        elif s[0] == '2':  # 检查单个地址分配
            print(check1(num(s[1]),address))
        elif s[0] == '3':  # 检查一段地址分配
            print(check2(num(s[1]), num(s[2]),address))
        else:
            raise Exception('error')


def num(s):
    ans = 0
    for x in s.split(':'):
        ans = ans * pow(2, 16) + int(x, 16)
    return ans


def merge(intervals):
    intervals.sort(key=lambda x: x[0])  # 这里是按照开始端点排序
    merged = []
    for l, r in intervals:
        if not merged or merged[-1][1] < l:
            merged.append([l, r])
        else:
            merged[-1][1] = max(merged[-1][1], r)
    return merged


def alloc(id, l, r,address):
    for key, add in address.items():
        if key == 0:  # 空闲地址
            newFree = []
            flag = False
            for start, end in add:
                if start <= l <= r <= end:
                    flag = True  # 空闲地址可分配
                    if start < l:
                        newFree.append((start, l - 1))
                    if r < end:
                        newFree.append((r + 1, end))
                else:
                    newFree.append((start, end))
            if flag:
                address[0] = merge(newFree)
                address[id].append((l, r))
                address[id] = merge(address[id])
                return True
        elif key == id:  # 重复分配
            for start, end in add:
                if start <= l <= r <= end:
                    return False
        else:  # 与其他地址段冲突
            for start, end in add:
                if start <= l <= r <= end or start <= l <= end <= r or l <= start <= r <= end or l <= start <= end <= r:
                    return False
    # 剩下这个是特殊情况,就是申请的地址中没有已经分配给其他用户的地址，但含有一些先前已分配给该用户本人的地址。
    # 这种情况下，我们需要将该用户的地址段进行合并，然后再进行判断。
    address[id].append((l, r))
    address[id] = merge(address[id])

    # 从addrees[0]中分配(l,r),不可能被完全包含
    newFree = []

    for start, end in address[0]:
        if start <= l <= r <= end:  # 不可能发生
            continue
        elif start <= l <= end <= r:
            if start < l:
                newFree.append((start, l - 1))
        elif l <= start <= r <= end:
            if r < end:
                newFree.append((r + 1, end))
        elif l <= start <= end <= r:
            continue
        else:  # 两个区间没有交集
            newFree.append((start, end))
    address[0] = merge(newFree)
    return True


def check1(x,address):
    for id, add in address.items():
        for start, end in add:
            if start <= x <= end:
                return id
    return 0


def check2(l, r,address):
    for id, add in address.items():
        for start, end in add:
            if start <= l <= r <= end:
                return id
    return 0

if __name__=='__main__':
    main()

# input:
# 32 12
# 1 1 0001:8000 0001:ffff
# 2 0001:a000
# 3 0001:c000 0001:ffff
# 1 2 0000:0000 000f:ffff
# 2 0000:1000
# 1 1 0001:8000 0001:8fff
# 1 2 0000:0000 0000:ffff
# 2 0000:1000
# 1 1 0002:8000 0002:ffff
# 3 0001:8000 0002:ffff
# 1 1 0001:c000 0003:ffff
# 3 0001:8000 0002:ffff

# output:
# YES
# 1
# 1
# NO
# 0
# NO
# YES
# 2
# YES
# 0
# YES
# 1

T5——施肥

问题描述

春天到了，西西艾弗岛上的n块田地需要施肥了。n块田地编号为 1,2,⋯,n，按照编号从小到大的顺序排成一列。
为了给田地施肥，顿顿准备了m辆施肥车。但是由于土地的松软程度不同，施肥车的质量不一，不一定每一辆施肥车都能给每一块田地施肥。其中，第i辆施肥车只能恰好从第l_i块田地开到第r_i块田地，并给编号在l_i与r_i之间的田地（包含 l_i和 r_i）都施一遍肥。其中 1≤l_i<r_i≤n。
顿顿希望制定一个施肥的计划。首先，他将选定二元组 (L,R)(1≤L<R≤n)，并选择只给编号在L,R之间（包含L,R）的田地施肥。接着，他会从使用这m辆施肥车中的一部分（或全部）对田地施肥。他想要保证：编号在L和R之内的田地至少被某一辆施肥车施了一次肥，且编号范围外的田地都没有被施过肥。
现在，他想知道，他能够选择多少种不同的二元组 (L,R) 作为施肥范围，使得可以选出一部分（或全部）施肥车，完成他的目标。

输入格式

从标准输入读入数据。
第一行输入两个正整数n,m 表示田地的块数和 施肥车的辆数。数据保证 2≤n≤210**5,1≤m≤210**5。
接下来m行，第i行输入两个正整数l_i,r_i，表示第i辆施肥车的施肥范围从第l_i块田地到第r_i块田地。数据保证 1<=l_i<r_i<=n。

输出格式

输出到标准输出。
输出一个正整数，表示顿顿能够选择多少种不同的二元组 (L,R) 作为施肥范围，使得他可以选出一部分（或全部）施肥车，完成他的目标。

样例输入1

4 3
1 2
3 4
2 3

样例输出1

6

样例解释

在这组样例中，顿顿可以选择 6 种不同的二元组 (L,R)。
第一种：选择 (L,R)=(1,2)，并只选取第 1 个施肥车施肥。
第二种：选择 (L,R)=(3,4)，并只选取第 2 个施肥车施肥。
第三种：选择 (L,R)=(2,3)，并只选取第 3 个施肥车施肥。
第四种：选择 (L,R)=(1,4)，并选取第 1 个和第 2 个施肥车施肥。
第五种：选择 (L,R)=(1,3)，并选取第 1 个和第 3 个施肥车施肥。
第六种：选择 (L,R))=(2,4)，并选取第 2 个和第 3 个施肥车施肥。

样例2

见题目目录下的 2.in 与 2.ans。
这个样例满足 n,m≤18。

样例3

见题目目录下的 3.in 与 3.ans。
这个样例满足 n,m≤50。

样例4

见题目目录下的 4.in 与 4.ans。
这个样例满足 n,m≤400。

样例5

见题目目录下的 5.in 与 5.ans。
这个样例满足 n,m≤3000。

样例6

见题目目录下的 6.in 与 6.ans。
这个样例满足特殊性质 A。

样例7

见题目目录下的 7.in 与 7.ans。
这个样例满足 n,m≤200000。

子任务

测试点编号	n≤	m≤	特殊性质
1	18	18
2	18	18
3	18	18
4	50	50
5	50	50
6	400	400
7	400	400
8	3000	3000
9	3000	3000
10	3000	3000
11	3000	3000
12	3000	3000
13	200000	200000	A
14	200000	200000	A
15	200000	200000	A
16	200000	200000
17	200000	200000
18	200000	200000
19	200000	200000
20	200000	200000

特殊性质 A：保证任意两个施肥车的施肥范围不存在相互包含的关系，也就是说，对任意 1≤i<j≤m，l_i<l_j,r_i<r_j 或 l_i>l_j,r_i>r_j。

def main():
    ans = 0
    n, m = list(map(int, input().split()))
    cars = set()
    for _ in range(m):
        cars.add(tuple(map(int, input().split())))
    # cars = sorted(cars)
    # print(cars)
    for L in range(1, n):
        for R in range(L + 1, n + 1):
            if check(cars, L, R, n):
                ans += 1
    print(ans)


def check(cars, L, R, n):
    flag = [0] * (n + 2)
    for l, r in cars:  # 遍历所有的车
        if L <= l < r <= R: # 保证编号范围外的田地都没有被施过肥
            flag[l] += 1
            flag[r + 1] -= 1
    for i in range(1, n+1):
        flag[i] += flag[i - 1]
    # print(L,R,flag)
    return all(num > 0 for num in flag[L:R + 1]) # 编号在L,R之间的田地都被施过肥

if __name__ == '__main__':
    main()

# input:
# 4 3
# 1 2
# 3 4
# 2 3

# output:
# 6

# import sys

# # 线段树模板
# class SegTree:
#     def __init__(self, n):
#         self.n = n
#         self.tree = [0] * (4 * n+1)
#
#     def update(self, u, v, x):
#         self.__update(1, 1, self.n, u, v, x)
#
#     def query(self, u, v):
#         return self.__query(1, 1, self.n, u, v)
#
#     def __update(self, k, l, r, u, v, x):
#         if l >= u and r <= v:
#             self.tree[k] += x
#             return
#         mid = (l + r) // 2
#         if u <= mid:
#             self.__update(k * 2, l, mid, u, v, x)
#         if v > mid:
#             self.__update(k * 2 + 1, mid + 1, r, u, v, x)
#         self.tree[k] = self.tree[k * 2] + self.tree[k * 2 + 1]
#
#     def __query(self, k, l, r, u, v):
#         if l >= u and r <= v:
#             return self.tree[k]
#         mid = (l + r) // 2
#         res = 0
#         if u <= mid:
#             res += self.__query(k * 2, l, mid, u, v)
#         if v > mid:
#             res += self.__query(k * 2 + 1, mid + 1, r, u, v)
#         return res
#
# # 读入数据
# n, m = map(int, input().split())
#
# # 将施肥区间按照左端点从小到大排序
# ranges = []
# for i in range(m):
#     l, r = map(int, input().split())
#     ranges.append((l, r))
# ranges.sort()
#
# # 初始化线段树
# seg_tree = SegTree(n)
#
# # 按照右端点建立一个线段树
# right_tree = SegTree(n)
# for l, r in ranges:
#     right_tree.update(r, r, 1)
#
# # 枚举区间 [l, r]，判断它是否能被覆盖
# res = 0
# for l in range(1, n):
#     right_tree.update(l - 1, l - 1, -1)
#     for r in range(l, n + 1):
#         # 查询线段树，判断 [l, r] 是否被覆盖
#         if seg_tree.query(l, r) == 0 and right_tree.query(l, r) == 0:
#             res += 1
#         # 更新线段树，将 [l, r] 所对应的施肥区间的贡献加上
#         for i in range(len(ranges)):
#             if ranges[i][0] <= l and ranges[i][1] >= r:
#                 seg_tree.update(l, r, 1)
#                 break
#
# # 输出答案
# print(res)