考察

\(x\) 番目に水浴びをする馬のことを，位置 \(x\) にいると呼ぶことにします．また，位置 \(x-1\) の馬の丁寧さ (\(x = 1\) の場合は \(1\)) を，位置 \(x\) の馬の係数と呼ぶことにします．

丁寧さ \(1\) の馬が \(z\) 頭おり，それらの位置が \(t_1 < \dots < t_{z}\) とします．

このとき，係数 \(1\) の馬は以下の通りです．

• ケース \(1\): \(z > 0\) かつ \(t_z < N\) の場合，位置 \(1, (t_1 + 1), (t_2 + 1), \dots, (t_z + 1)\) にいる \(z+1\) 頭の馬．
• ケース \(2\): \(z > 0\) かつ \(t_z = N\) の場合，位置 \(1, (t_1 + 1), (t_2 + 1), \dots, (t_{z-1} + 1)\) にいる \(z\) 頭の馬．
• ケース \(3\): \(z = 0\) の場合，位置 \(1\) にいる \(1\) 頭の馬．

ここで，ケース \(1\) において位置 \((t_z + 1), (t_z + 2), \dots, N, 1, 2, \dots, t_z\) の馬がこの順に並びなおしたとき，各馬の係数は以下のように変化します．

• もともと位置 \(1\) にいた馬は，もともとの係数が \(1\) なので，新しい係数はそれ以上である．
• もともと位置 \((t_z + 1)\) にいた馬は，もともとの係数が \(1\) なので，新しい係数はそれ以上である．
• 上のいずれにもあてはまらない馬は，直前にいる馬が変わらないので，係数も変わらない．

したがって，上のように並べかえても全体の満足度は下がりません．並べ替え後の並びは必ずケース \(2\) に当てはまるので，ケース \(2, 3\) のみを考えればよいです．

\(z = 0\) の場合 (すべての馬の丁寧さが \(2\))

これはケース \(3\) にあたり，位置 \(1\) のみが係数 \(1\) になり，ほかの位置の係数は \(2\) になります．したがって，機嫌がもっとも低い馬を位置 \(1\) に置くことで達成できる最大値 \(2 \sum A_i - \min A_i\) が答えになります．

\(z = N\) の場合 (すべての馬の丁寧さが \(1\))

すべての位置で係数 \(1\) になるので，\(\sum A_i\) が答えになります．

\(0 < z < N\) の場合

ケース \(2\) の並べ方のみを考えれば十分です．

丁寧さ \(2\) の馬が \(N - z\) 頭おり，その位置が \(s_1 < \dots < s_{N-z}\) とします．

このとき，位置 \(s_1\) の馬はかならず係数 \(1\) です．これは，\(s_1 = 1\) の場合は明らかであり，\(s_1 \geq 2\) の場合は位置 \(s_1 - 1\) の馬が丁寧さ \(1\) であることがいえるためです．

したがって，丁寧さ \(2\) の馬のうち少なくとも \(1\) 頭は係数 \(1\) になります．

逆に，丁寧さ \(2\) の馬を \(1\) 頭以上含むような \(z\) 頭の馬の集合 \(S\) をどのように選んでも，\(S\) に属する馬の係数が \(1\) に，\(S\) に属さない馬の係数が \(2\) になるように馬の位置を決めることができます(後述)．

よって，丁寧さ \(2\) の馬を \(1\) 頭以上含むような \(z\) 頭の馬の集合 \(S\) に対する \(A_i\) の総和の最小値を \(x\) とおくと，\(2 \sum A_i - x\) が答えとなります．

これは，\(A_i\) の小さいほうから \(z\) 個の馬の集合を \(T\) として，

• \(T\) の要素のうち少なくとも \(1\) つが \(B_i = 2\) を満たす場合は，\(T\) がそのまま \(S\) の条件を満たし，\(2 \sum A_i - \sum_{j \in T} A_j\) が答え．
• \(T\) の要素のすべてが \(B_i = 1\) を満たす場合は，\(T\) の要素のひとつを，\(B_i = 2\) を満たす馬のひとつに置き換えることで \(S\) の条件を満たす．前者は \(A_i\) 最大の，後者は \(A_i\) 最小のものを選ぶのが最適で，答えは \(\displaystyle 2 \sum A_i - (\sum_{j \in S} A_j - \max_{j \in S} A_j + \min_{B_j = 2} A_j)\)．

条件を満たす位置の決め方

集合 \(H_{i,j}\) を，丁寧さが \(i\) であり，係数を \(j\) にしたい馬の集合とします．仮定より \(|H_{1,1}| + |H_{1,2}| = z \geq 1\)，\(|H_{2,1}| = |H_{1,2}| \geq 1\) です．

このとき，集合の要素を被りなく以下の順に並べることで，要求する係数を達成することが可能です．

• \(H_{2,1}\) の要素のひとつ
• \(H_{2,2}\) の要素すべて
• \(H_{1,2}\) の要素ひとつ
• \(H_{2,1}, H_{1,2}\) の要素を交互に \((|H_{2,1}| - 1)\) 組
• \(H_{1,1}\) の要素すべて

実装方針

\(A_i\) の値の被りが許されることに注意すると，以下の情報をノード \(\left[ l, r \right)\) に持つセグメント木を更新することでクエリに対応することができます．

• \(l \leq A_i < r, B_i = 1\) を満たす \(i\) の個数 \(c_1\)
• \(l \leq A_i < r, B_i = 2\) を満たす \(i\) の個数 \(c_2\)
• \(\displaystyle\sum_{l \leq A_i < r} A_i\) の値 \(s\)

\(z = 0, N\) の場合は別途処理することにします．

\(0 < z < N\) の場合は，\(A_i \leq r\) を満たす \(A_i\) が \(z\) 個以上となる最小の \(r\) をセグメント木上の二分探索によって求め，ノード \([0, r+1)\) 上の情報 \(c_1, c_2, s\) に対して

• \(A_i \leq r, B_i = 2\) を満たす \(i\) が存在すれば(つまり，\(c_2 > 0\) ならば) \(s - (c_1 + c_2 - z)r\) が答えです．
• そうでなければ，\(s - r + \min_{B_j = 2} A_j\) が答えになります．\(\min_{B_j = 2} A_j\) については，\(c_2 > 0\) を条件としてセグメント木上を二分探索することで求まります．

時間計算量は \(M := \max A_i\) として \(O(M + N + Q \log M)\) となり，十分高速です．

実装例 (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;
}