G. Count the trains (thought set + two points)

Codeforces Round #797 (Div. 3)

Problem

There are n Coach compartment , Each car can reach a maximum speed driven by its own engine , Record in a sequence $\{a_i\}$ in . The number of the carriage from left to right is 1 To n.

Now let these carriages move to the left as fast as possible , It is required that the actual speed of the carriage on the right cannot exceed that of the carriage on the left . In this way, several continuous cars with the same speed will be formed , Call such a section a train . For example, the sequence a=[10,13,5,2,6] The actual running speed of the corresponding carriage is [10,10,5,2,2], To form the 3 Train Festival .

When driving in the carriage , Received in turn m Bar information , Each message contains two numbers k and d, It means the first one k The top speed of the car has decreased due to the aging of the engine d. Please maintain the total number of trains in this process , Output each time you receive a message , The changes of each information to the array are saved .

Solution

1. It is required that the actual speed of the carriage on the right should not exceed the actual speed of the carriage on the left ,
   that , Eventually, a monotonic decreasing queue containing the first carriage will be formed .
   The final number of trains is the length of the strictly decreasing sequence of the queue .
2. We store the subscript of this sequence in set in , For each inquiry , find set The largest of j Satisfy $j\le k$
   1. If j = k, Insert set
   2. If $a[j]>a[k]$ （a[k] Is the modified value ）, Insert set
3. Maintain the monotonicity of the queue after insertion , So we need to put The subscript is greater than j Of And Its value Greater than or equal to a[k] The deletion of .
   Make the queue always strictly monotonically decreasing .
4. here set The size of is the result of this modification
5. Time complexity $O(mlogn)$

Code

int main()
{
    
	IOS;
	int T; cin >> T;
	while (T--)
	{
    
		int n, m; cin >> n >> m;
		for (int i = 1; i <= n; i++) cin >> a[i];
		set<int> s;
		for (int i = 1; i <= n; i++)
			if (s.empty() || a[i] < a[*s.rbegin()])
				s.insert(i);

		int k, d;
		while (m--)
		{
    
			cin >> k >> d;
			a[k] -= d;
			auto it = s.upper_bound(k);
			if (it == s.begin()) s.insert(k);
			else
			{
    
				it = prev(it);
				if (*it == k || a[*it] > a[k])
					s.insert(k);
			}

			while (1)
			{
    
				it = s.upper_bound(k);
				if (it != s.end() && a[*it] >= a[k])
					s.erase(it);
				else break;
			}

			cout << sz(s) << " ";
		}
		cout << "\n";
	}


	return 0;
}