本文主要是介绍前后缀分离，CF1209 C. Maximal Intersection，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
Problem - 1029C - Codeforces
二、解题报告
1、思路分析
线段相交具有可重复贡献性：整个区间的交等价于把区间分为若干部分，分别求交再求交
那么我们只需维护每个线段的前后缀区间的线段交
然后枚举删除的线段，删除后的最大线段交就是前缀交线段和后缀交线段的交
2、复杂度
时间复杂度： O(n) 空间复杂度：O(n)
3、代码详解
import sys
from math import inf
# sys.stdin = open('in.txt', 'r')input = lambda: sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x))n = int(input())
lines = [tuple(map(int, input().split())) for _ in range(n)]prel, prer = [-inf] * n, [inf] * nfor i in range(1, n):prel[i] = max(lines[i - 1][0], prel[i - 1])prer[i] = min(lines[i - 1][1], prer[i - 1])
sufl, sufr = -inf, infans = 0for i in range(n - 1, -1, -1):ans = max(ans, min(sufr, prer[i]) - max(sufl, prel[i]))sufl = max(sufl, lines[i][0])sufr = min(sufr, lines[i][1])
write(ans)这篇关于前后缀分离，CF1209 C. Maximal Intersection的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
