#PQJ1457x7980. QOJ 1457_7980

    ID: 2614 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测线段树区间DP

QOJ 1457_7980

标题: 区间切割 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

有 n 个区间 [Li,Ri],然后有 m 次切割操作,每次操作由三元组 (x,l,r) 描述,对 i∈[l,r] 进行如下操作:

  • 如果 x∉[Li,Ri],什么都不做。
  • 否则区间 i 将被切割为 [Li,x] 和 [x,Ri] 两段,用较长的一段作为新的区间 i,如果长度相等选择 [Li,x]。

求出每个区间在所有操作后的左右端点。为了简化问题,保证所有 x 构成 1∼m 的排列。

输入格式

第一行包含三个整数 n,m,id (1≤n≤105,1≤m≤106,0≤id≤7),其中 id 表示子任务编号,样例中 id=0。

接下来 n 行,每行包含两个整数 Li,Ri (1≤Li<Ri≤m),表示区间 i 的左右端点。

接下来 m 行,每行包含三个整数 x,l,r (1≤x≤m,1≤l≤r≤n),表示一次切割操作。保证所有 x 构成 1∼m 的排列。

输出格式

共 n 行,第 i 行包含两个整数表示线段 i 最终的左右端点。

样例输入 #1
1 4 0
1 4
1 1 1
4 1 1
3 1 1
2 1 1
样例输出 #1
1 2
样例输入 #2
5 5 0
2 3
4 5
1 4
2 5
2 4
1 5 5
2 5 5
3 1 1
5 4 5
4 2 2
样例输出 #2
2 3
4 5
1 4
2 5
2 4
样例输入/输出 #3

ex_cut3.in/out,满足子任务 2 的限制。

样例输入/输出 #4

ex_cut4.in/out,满足子任务 3 的限制。

数据范围

对于全部数据

1≤n≤105,1≤m≤106

1≤Li<Ri≤m,1≤x≤m,1≤l≤r≤n,保证所有 x 构成 1∼m 的排列。

子任务分值n≤m≤特殊性质1550005000215160002×105AB315105106A415160002×105B510105106B620160002×105720105106

特殊性质 A:所有 x 构成 1∼m 的随机排列。

特殊性质 B:每次操作的 l=1,r=n。