前后缀分离，CF1209 C. Maximal Intersection

本文主要是介绍前后缀分离，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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---