Observations

Let us say the horse that bathes \(x\)-th has position \(x\), and call the tidiness of horse \((x-1)\) (or \(1\) for \(x=1)\) the weight of the position-\(x\) horse.

Suppose that there are \(z\) horses with tidiness \(1\), positioned at \(t_1 < \dots < t_{z}\).

Then the horses with weight \(1\) are:

• case \(1\): if \(z > 0\) and \(t_z < N\), the \((z+1)\) horses with positions \(1, (t_1 + 1), (t_2 + 1), \dots, (t_z + 1)\).
• case \(2\): if \(z > 0\) and \(t_z = N\), the \(z\) horses with positions \(1, (t_1 + 1), (t_2 + 1), \dots, (t_{z-1} + 1)\).
• case \(3\): if \(z = 0\), the one horse with position \(1\).

Consider case \(1\). If we rearrange horses with positions \((t_z + 1), (t_z + 2), \dots, N, 1, 2, \dots, t_z\) in this order, their weights change as follows:

• the horse with original position \(1\) has an original weight \(1\), so the new weight is greater or equal.
• the horse with original position \((t_z + 1)\) has an original weight \(1\), so the new weight is greater or equal.
• any other horses’ weight do not change, because the horses in front of them remain the same.

Therefore, rearranging this way does not reduce the total satisfaction. Since the rearrangement always result in case \(2\), it is sufficient to consider cases \(2\) and \(3\).

If \(z = 0\) (all horses’ tidiness is \(2\))

This falls into case \(3\). The horse with position \(1\) has a weight \(1\), and all other horses has a weight \(2\). Thus, the maximum value is obtained by placing a horse with the lowest mood at position \(1\), and the answer is \(2 \sum A_i - \min A_i\).

If \(z = N\) (all horses’ tidiness is \(1\))

All horses’ weight is \(1\), so the answer is \(\sum A_i\).

If \(0 < z < N\)

It is sufficient to consider case-\(2\) arrangements.

Suppose there are \((N - z)\) horses of tidiness \(2\), positioned at \(s_1 < \dots < s_{N-z}\).

Then the horse at position \(s_1\) always has a weight \(1\). This is obvious for \(s_1 = 1\), and if \(s_1 \geq 2\), then the horse at position \(s_1 - 1\) has a tidiness \(1\).

Therefore, at least one horse of tidiness \(2\) will have a weight \(1\).

Conversely, for any set \(S\) of \(z\) horses that contain one or more horses of tidiness \(2\), one can arrange the horses so that the horses belonging to \(S\) have a weight \(1\), and the other have a weight \(2\) (described later).

Hence, the answer is \(2 \sum A_i - x\), where \(x\) is the minimum sum of \(A_i\) for a set of \(S\) of \(z\) horses containing at least one horse of tidiness \(2\).

Let \(T\) be the set of \(z\) horses with the smallest \(A_i\). Then the sought minimum value can be found as follows:

• If any element in \(T\) satisfies \(B_i = 2\), then \(T\) already satisfies the condition of \(S\), and the answer is \(2 \sum A_i - \sum_{j \in T} A_j\).
• If all elements of \(T\) satisfy \(B_i = 1\), then replacing one element of \(T\) with a horse with \(B_i = 2\) satisfy the condition of \(S\). For the former, it is optimal to choose the one with the maximum \(A_i\), and for the latter, it is optimal to choose the one with the minimum \(A_i\). The answer is \(\displaystyle 2 \sum A_i - (\sum_{j \in S} A_j - \max_{j \in S} A_j + \min_{B_j = 2} A_j)\).

How to arrange horses to meet the conditions

Let \(H_{i,j}\) be the set of horses with tidiness \(i\) and requested weight \(j\). By assumption, \(|H_{1,1}| + |H_{1,2}| = z \geq 1\) and \(|H_{2,1}| = |H_{1,2}| \geq 1\).

Then, by arranging the elements as follows without repetition, the requested weights can be realized.

• One element from \(H_{2,1}\)
• All elements from \(H_{2,2}\)
• One element from \(H_{1,2}\)
• Elements from \(H_{2,1}\) and elements from \(H_{1,2}\), alternately (\((|H_{2,1}| - 1)\) pairs)
• All elements from \(H_{1,1}\)

Implementation

Note that values \(A_i\) may contain duplicates. The query can be answered by managing a segment tree that stores the following information for each node \(\left[ l, r \right)\):

• \(c_1\): the number of \(i\) satisfying \(l \leq A_i < r\) and \(B_i = 1\).
• \(c_2\): the number of \(i\) satisfying \(l \leq A_i < r\) and \(B_i = 2\).
• \(s\): the value of \(\displaystyle\sum_{l \leq A_i < r} A_i\).

We handle \(z = 0, N\) separately.

If \(0 < z < N\), perform a binary search on the segment tree to find the minimum \(r\) such that there are \(z\) or more elements \(A_i\) such that \(A_i \leq r\). Let \(c_1, c_2, s\) be the values stored in node \([0, r+1)\). Then:

• If there exists \(i\) with \(A_i \leq r\) and \(B_i = 2\) (i.e. if \(c_2 > 0\)), the answer is \(s - (c_1 + c_2 - z)r\).
• Otherwise, the answer is \(s - r + \min_{B_j = 2} A_j\). Here, \(\min_{B_j = 2} A_j\) can be found by performing a binary search with criteria \(c_2 > 0\) on the segment tree.

The time complexity is \(O(M + N + Q \log M)\) where \(M := \max A_i\), which is fast enough.

Sample code (C++)

#include <iostream>
using std::cin;
using std::cout;
#include <vector>
using std::vector;
#include <algorithm>
using std::sort;
using std::max;
using std::min;

typedef long long int ll;

#include <atcoder/segtree>
using atcoder::segtree;

ll n, q;
vector<ll> a, b;

const ll MAX_A = 1'000'006LL;

struct Seg {
	ll sum;
	ll cnt1;
	ll cnt2;
};
const Seg unity = {0, 0, 0};

Seg seg_op (Seg l, Seg r) {
	return {
		l.sum  + r.sum,
		l.cnt1 + r.cnt1,
		l.cnt2 + r.cnt2
	};
}
Seg seg_e () {
	return unity;
}

ll f_thres = 0;
bool f_lower (Seg s) {
	return (s.cnt1 + s.cnt2) < f_thres;
}
bool f_no2 (Seg s) {
	return s.cnt2 <= 0;
}


void solve () {
	ll whole1 = 0, whole2 = 0, wholesum = 0;
	vector<Seg> leaf(MAX_A + 1, unity);
	segtree<Seg, seg_op, seg_e> seg(MAX_A + 1);
	for (ll i = 0; i < n; i++) {
		wholesum += a[i];
		if (b[i] == 1) {
			leaf[a[i]].sum += a[i];
			leaf[a[i]].cnt1 += 1;
			whole1++;
		} else {
			leaf[a[i]].sum += a[i];
			leaf[a[i]].cnt2 += 1;
			whole2++;
		}
		seg.set(a[i], leaf[a[i]]);
	}
	
	for (ll qi = 0; qi < q; qi++) {
		ll w, x, y;
		cin >> w >> x >> y;
		--w;
		
		wholesum -= a[w];
		if (b[w] == 1) {
			leaf[a[w]].sum  -= a[w];
			leaf[a[w]].cnt1 -= 1;
			whole1--;
		} else {
			leaf[a[w]].sum  -= a[w];
			leaf[a[w]].cnt2 -= 1;
			whole2--;
		}
		seg.set(a[w], leaf[a[w]]);

		a[w] = x;
		b[w] = y;
		wholesum += a[w];
		if (b[w] == 1) {
			leaf[a[w]].sum  += a[w];
			leaf[a[w]].cnt1 += 1;
			whole1++;
		} else {
			leaf[a[w]].sum  += a[w];
			leaf[a[w]].cnt2 += 1;
			whole2++;
		}
		seg.set(a[w], leaf[a[w]]);

		ll minus;
		if (whole2 == 0) {
			minus = wholesum;
		} else {
			ll z = max(1LL, whole1);

			f_thres = z;
			ll ri = seg.max_right<f_lower>(0); // z-smallest (combining type1/2) is ri

			Seg s = seg.prod(0, ri+1);
			if (s.cnt2 > 0) {
				minus = s.sum - ri * (s.cnt1 + s.cnt2 - z);
			} else {
				ll bi = seg.max_right<f_no2>(0); // smallest type2 is bi
				minus = s.sum - ri * (s.cnt1 + s.cnt2 - z + 1) + bi;
			}
		}

		ll ans = wholesum * 2 - minus;
		cout << ans << "\n";

	}
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	
	cin >> n >> q;
	a.resize(n);
	b.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}

	solve();

	return 0;
}