The Great Equalizer

# The Great Equalizer

## 题面翻译

Tema 购买了一台老旧设备，设备上有一个小屏幕和一个磨损的铭文“伟大的平衡器”。

卖家说，这台设备需要提供一个整数数组 $a$ 作为输入，之后“伟大的平衡器”将按照以下方式工作：

1. 将当前数组按升序排序，并删除重复元素，相同元素仅保留第一次出现的；
2. 如果当前数组的长度等于 $1$，设备停止工作并输出数组中的唯一一个数字，即设备的输出值；
3. 向当前数组添加一个等差数列 $\{n,\ n - 1,\ n - 2,\ \ldots,\ 1\}$，其中 $n$ 是当前数组的长度。换句话说，数组的第 $i$ 个元素需要加上 $n - i$（下标从 $0$ 开始）；
4. 返回第 $1$ 步。

为了测试设备的运行，Tema 构想了一个整数数组 $a$，然后希望对数组 $a$ 执行 $q$ 次操作，操作如下：

1. 将值 $x$（$1 \le x \le 10^9$）赋给元素 $a_i$（$1 \le i \le n$）；
2. 将数组 $a$ 作为输入提供给设备，并找到设备操作后的结果，同时数组 $a$ 保持不变。

帮助 Tema 找出每个操作后设备的输出值。

## 题目描述

Tema bought an old device with a small screen and a worn-out inscription "The Great Equalizer" on the side.

The seller said that the device needs to be given an array $ a $ of integers as input, after which "The Great Equalizer" will work as follows:

1. Sort the current array in non-decreasing order and remove duplicate elements leaving only one occurrence of each element.
2. If the current length of the array is equal to $ 1 $ , the device stops working and outputs the single number in the array — output value of the device.
3. Add an arithmetic progression { $ n,\ n - 1,\ n - 2,\ \ldots,\ 1 $ } to the current array, where $ n $ is the length of the current array. In other words, $ n - i $ is added to the $ i $ -th element of the array, when indexed from zero.
4. Go to the first step.

To test the operation of the device, Tema came up with a certain array of integers $ a $ , and then wanted to perform $ q $ operations on the array $ a $ of the following type:

1. Assign the value $ x $ ( $ 1 \le x \le 10^9 $ ) to the element $ a_i $ ( $ 1 \le i \le n $ ).
2. Give the array $ a $ as input to the device and find out the result of the device's operation, while the array $ a $ remains unchanged during the operation of the device.

Help Tema find out the output values of the device after each operation.

## 输入格式

The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

Then follows the description of each test case.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the size of the array $ a $ that Tema initially came up with.

The second line of each test case contains $ n $ integers $ a_1, a_2, a_3, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of the array $ a $ .

The third line of a set contains a single integer $ q $ ( $ 1 \le q \le 2 \cdot 10^5 $ ) — the number of operations.

Each of the next $ q $ lines of a test case contains two integers $ i $ ( $ 1 \le i \le n $ ) and $ x $ ( $ 1 \le x \le 10^9 $ ) - the descriptions of the operations.

It is guaranteed that the sum of the values of $ n $ and the sum of the values of $ q $ for all test cases do not exceed $ 2 \cdot 10^5 $ .

## 输出格式

For each test case, output $ q $ integers — the output values of the device after each operation.

## 样例 #1

### 样例输入 #1

```

4
3
2 4 8
3
1 6
2 10
3 1
5
1 2 2 2 2
1
5 3
2
5 6
7
1 2
1 7
1 7
2 5
1 2
2 7
2 2
5
2 5 1 10 6
10
1 7
4 8
2 5
1 4
2 8
3 4
1 9
3 7
3 4
3 1

```

### 样例输出 #1

```

10 12 15 
4 
10 8 8 9 8 12 2 
14 12 12 11 11 10 11 10 11 14

```

## 提示

Let's consider the first example of the input.

Initially, the array of numbers given as input to the device will be $ [6, 4, 8] $ . It will change as follows: $ $$$[6, 4, 8] \rightarrow [4, 6, 8] \rightarrow [7, 8, 9] \rightarrow [10, 10, 10] \rightarrow [10] $ $ </p><p>Then, the array of numbers given as input to the device will be  $ \[6, 10, 8\] $ . It will change as follows:  $ $ [6, 10, 8] \rightarrow [6, 8, 10] \rightarrow [9, 10, 11] \rightarrow [12, 12, 12] \rightarrow [12] $ $ </p><p>The last array of numbers given as input to the device will be  $ \[6, 10, 1\] $ . It will change as follows:  $ $ [6, 10, 1] \rightarrow [1, 6, 10] \rightarrow [4, 8, 11] \rightarrow [7, 10, 12] \rightarrow [10, 12, 13] \rightarrow [13, 14, 14] \rightarrow [13, 14] \rightarrow [15, 15] \rightarrow [15] $ $$$

参考代码

#include <bits/stdc++.h>
#define long long ll;
using namespace std;

int a[200005], b[200005];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t; 
	cin>>t;
	
	while(t--)
	{
		int n;
		cin>>n;
		multiset <int> s, diff;
		diff.insert(0);
		
		for (int i = 1; i <= n; i++)
		{
			cin>>b[i];
			a[i] = b[i];
			s.insert(b[i]);
		}
		
		sort(b + 1, b + n + 1);
		
		for (int i = 2; i <= n; i++)
			diff.insert(b[i] - b[i - 1]);
		
		int q;
		cin>>q;
		
		while (q--)
		{
			int id, x, A = -1, B = -1;
			cin>>id>>x;
			
			s.erase(s.find(a[id]));
			auto it = s.lower_bound(a[id]);
			
			if(it != s.end())
				B = *it;
			if(it != s.begin())
			{
				--it;
				A = *it;
			}
			if(A != -1)
				diff.erase(diff.find(a[id] - A));
			if(B != -1)
				diff.erase(diff.find(B - a[id]));
			if(A != -1 && B != -1)
				diff.insert(B - A);
			
			a[id] = x;
			it = s.lower_bound(a[id]);
			A = -1;
			B = -1;
			if (it != s.end())
				B = *it;
			if (it != s.begin())
			{
				--it;
				A = *it;
			}
			if (A != -1)
				diff.insert(a[id] - A);
			if (B != -1)
				diff.insert(B - a[id]);
			if (A != -1 && B != -1)
				diff.erase(diff.find(B - A));
			
			s.insert(a[id]);
			cout << *(--s.end()) + *(--diff.end()) << ' ';
		}
		cout << '\n';
	}
	return 0;
}

原题链接

CF1862G The Great Equalizer