#1820. 区间切割

    ID: 1820 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1457来源:qoj.ac数据:公开样例区间DP

区间切割

区间切割

题目描述

标题: 区间切割 - 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。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

(本题数据包未提供小体积样例)