P7078: 重新定位
传统题
1.000s
时间限制
256MB
内存限制
8 提交
4 解决
【题目描述】
【题目描述】
在遥远的Lineland国家，科技公司遍地开花！每一周，科技公司似乎都在建立、合并、被收购或倒闭。对于在Lineland寻找新工作的软件工程师来说，甚至很难找到他们面试的公司的位置。
为了解决这个问题，你将创建一家新的科技公司！该产品很简单：通过在云中使用深度神经区块链，您的应用程序可以找到Lineland任何两家科技公司之间的距离。这是非常有用的，因为公司总是更换办公室，很难完全保持最新状态。通过集中这些信息，您的公司将使世界变得更美好。
由于Lineland是围绕一条直线组织的，因此公司的位置可以由一个坐标给出。任何两家公司之间的距离等于它们两个坐标之间的距离。
你的工作是处理两种用户对公司旗舰应用的请求。一种请求更新一家公司的地址，另一种请求两家公司之间的最短距离。
【输入】
第一行有两个正的空格分隔的整数N和Q：应用程序跟踪的公司数量（2≤
N≤
100000）和要处理的请求数量（1≤
Q≤
100000）。下一行有N个空分整数1≤
Xi≤
1000000000，这是N家公司的初始位置，按i=1到i=N的顺序给出。
接下来的每个Q行都有3个空格分隔的整数，采用以下形式之一：
l
1 C X，这意味着C公司将其位置移至X，或
l
2 A B，这是对公司A和B之间距离的查询。
保证1≤
A，B，C≤
N，1≤
X≤
100000000。两个公司可能共享同一个位置。还可以保证至少有一个类型为2的查询。
【输出】
对于类型2的每个查询，打印公司A和B之间的距离。
【样本输入1】
5 10
5 2 8 1 4
1 2 10
2 4 5
2 1 3
1 4 3
2 1 5
2 5 2
1 4 1
2 2 4
1 3 15
2 4 1
样本输出1
3
3
1
6
9
4
【示例说明】
在第一个查询中，公司2移动到位置10。然后，应用程序被要求计算4号公司和5号公司之间的距离，即3。下一个查询是公司1和3之间的距离，也是3。以下是一些更新和查询。