Solving a subproblem

Consider the case where \(a_1 = \dots = a_{N-1} = -1\) and \(a_N = r \neq -1\). In other words, consider the following problem:

(Problem NOADJ) How many ways are there to choose \(r\) teapots out of \(N\) teapots arranged in a line, such that no two adjacent teapots are chosen?

We claim that the answer is equal to that of the following problem:

(Problem SIMPLE) How many ways are there to freely choose \(r\) out of \(N - (r-1)\) teapots?

To prove that, it suffices to say there is a one-to-one correspondence between the choice for Problem NOADJ and Problem SIMPLE.

Let \(i_1, \dots, i_r\) be the indices of teapots chosen in SIMPLE. Then, one can insert one teapot to each position to the left of teapots \(i_2, \dots, i_r\) to obtain any choice for NOADJ.

Conversely, let \(i_1, \dots, i_r\) be the indices of teapots chosen in NOADJ. Then, each of teapots \(i_2, \dots, i_r\) have an unchosen teapot to its left. Removing them yields any choice for SIMPLE.

Hence a bijection exists. The answer to Problem SIMPLE is \(\mathrm{binom}(N-(r-1),r)\) (where \(\mathrm{binom}\) is a binomial coefficient), so the answer to Problem NOADJ is also \(\mathrm{binom}(N-(r-1),r)\).

From now on, define \(\mathrm{noadj}(n, r) := \mathrm{binom}(n-(r-1), r)\).

Observations

For simplicity, we refer to teapots \(l, \dots, r\) as teapots \([l, r]\) collectively.

Let \(i_1, \dots, i_k\) be the indices \(i\) with \(a_i \neq -1\). For convenience, let \(a_0 = 0\) and \(i_0 = 0\). Then the constraints regarding \(a\) can be rephrased as follows:

• For \(j = 1, \dots, k\), exactly \((a_{i_j} - a_{i_{j-1}})\) teapots among teapots \([i_{j-1} + 1, i_j]\) have coffee.
• Any number of teapots among \([i_k + 1, N]\) can have coffee.

By rephrasing this way, every teapot is covered by exactly one segment-wise constraint.

When we know the number of ways to fill teapots \([1, i_{j-1}]\), how can we count the ways of filling teapots \([1, i_{j}]\)?

• Let \(x_0\) be the number of ways to fill teapots \([1, i_{j-1}]\), such that teapot \(i_{j-1}\) is not filled with coffee.
• Let \(x_1\) be the number of ways to fill teapots \([1, i_{j-1}]\), such that teapot \(i_{j-1}\) is filled with coffee.
• Let \(y_0\) be the number of ways to fill teapots \([1, i_{j}]\), such that teapot \(i_{j}\) is not filled with coffee.
• Let \(y_1\) be the number of ways to fill teapots \([1, i_{j}]\), such that teapot \(i_{j}\) is filled with coffee.

(For \(j=1\), define \(x_0=1\) and \(x_1=0\).) These satisfies:

\[\begin{bmatrix} x_0 & x_1 \\ \end{bmatrix} \begin{bmatrix} f_{0,0}(i_j - i_{j-1}, a_{i_j} - a_{i_{j-1}}) & f_{0,1}(i_j - i_{j-1}, a_{i_j} - a_{i_{j-1}}) \\ f_{1,0}(i_j - i_{j-1}, a_{i_j} - a_{i_{j-1}}) & f_{1,1}(i_j - i_{j-1}, a_{i_j} - a_{i_{j-1}}) \\ \end{bmatrix} = \begin{bmatrix} y_0 & y_1 \\ \end{bmatrix}.\]

Here, \(f_{s, t}(n, r)\) is the contribution from \(x_s\) to \(y_t\) when we fill exactly \(r\) out of \(n\) teapots with coffee, and can be written as

• \(f_{0,0}(n, r) = \mathrm{noadj}(n-1, r),\)
• \(f_{0,1}(n, r) = \begin{cases} \mathrm{noadj}(0, r-1) & (n=1) \\ \mathrm{noadj}(n-2, r-1) & (n \geq 2),\end{cases}\)
• \(f_{1,0}(n, r) = \begin{cases} \mathrm{noadj}(0, r) & (n=1) \\ \mathrm{noadj}(n-2, r) & (n \geq 2),\end{cases}\)
• \(f_{1,1}(n, r) = \begin{cases} 0 & (n=1) \\ \mathrm{noadj}(0, r-1) & (n=2) \\ \mathrm{noadj}(n-3, r-1) & (n \geq 3).\end{cases}\)

We denote them by \(\bm{f}(n, r)\).

Also, let us consider how we can count the ways to fill all the teapots based on the counts for teapots \([1, i_{k}]\). Let

• Let \(x_0\) be the number of ways to fill teapots \([1, i_{k}]\), such that teapot \(i_{k}\) is not filled with coffee.
• Let \(x_1\) be the number of ways to fill teapots \([1, i_{k}]\), such that teapot \(i_{k}\) is filled with coffee.

Then the sought count is \(x_0 \cdot fib[N - i_k] + x_1 \cdot fib[\max(N - i_k - 1, 0)]\), where \(fib[i]\) is obtained by the following recurrence relations:

\[fib[i] = \begin{cases} 1 & (i = 0) \\ 2 & (i = 1) \\ fib[i-1]+fib[i-2] & (i \geq 2). \end{cases}\]

Hence, if we can evaluate \(\bm{M} = \Pi_{j=1}^{k} \bm{f}(i_j - i_{j-1}, a_{i_j} - a_{i_{j-1}})\), the answer can be obtained as \(M_{0,0} \cdot fib[N - i_k] + M_{0,1} \cdot fib[\max(N - i_k - 1, 0)]\).

Per-query updates

Consider maintaining a sequence of matrices \(F = (F_1, \dots, F_N)\) such that:

• If \(a_i = -1\), let \(F_i\) contain the identity matrix \(\bm{E} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\);
• If \(a_i \neq -1\), let \(F_i\) contain \(\bm{f}(i - i', a_i - a_{i'})\), where \(i'\) is the maximum integer satisfying the following conditions. For convenience, if \(i'=0\), let \(a_{i'} = 0\).
  • \(i' < i\).
  • \(a_{i'} \neq -1\) or \(i' = 0\).

Then \(\prod_{i=1}^{N} F_i\) coincides with the matrix \(\bm{M}\) desired above.

When we want to update \(a_{x}\), we find the following values, then among the elements of \(F\), only those with \(i = x,\ x_{high}\) need to be updated:

• The maximum integer \(x_{low}\) such that:
  • \(x_{low} < x\)
  • \(a_{x_{low}} \neq -1\) or \(x_{low} = 0\)
• The maximum integer \(x_{high}\) such that:
  • \(x_{high} > x\)
  • \(a_{x_{high}} \neq -1\) or \(x_{high} = N+1\)

By using a balanced binary search tree or a segment tree, one can find \(x_{low}\) and \(x_{high}\) in \(O(\log N)\) time.

Also, updating an element of \(F\) and computing \(\prod_{i=1}^{N} F_i\) can be achieved with a segment tree in \(O(\log N)\) time each.

Hence, the problem has been solved with \(O(N)\)-time precomputation and \(O(\log N)\)-time process per query.

Sample code (C++)

In C++, one can use std::set as an implementation of a balanced binary search tree, and atcoder::segtree in AtCoder Library as a segment tree.

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <set>
#include <map>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;
using std::min;
using std::max;
using std::array;
using std::set;
using std::map;

#include <atcoder/all>
using mint = atcoder::modint998244353;
using atcoder::segtree;

typedef long long int ll;

vector<mint> frac, invf;
void f_init (ll n) {
	frac.resize(n+1);
	invf.resize(n+1);
	frac[0] = 1;
	for (ll i = 1; i <= n; i++) {
		frac[i] = frac[i-1] * i;
	}
	invf[n] = frac[n].inv();
	for (ll i = n; i >= 1; i--) {
		invf[i-1] = invf[i] * i;
	}
}
mint ncr (ll n, ll r) {
	if (n < r || n < 0 || r < 0) return 0;

	if (frac.size() <= n) {
		f_init(n+5);
	}
	return frac[n] * invf[n-r] * invf[r];
}

ll n, q;

using Mat = array<array<mint, 2>, 2>;
const Mat unity = {
	(array<mint, 2>){1,0},
	(array<mint, 2>){0,1}
};
Mat operator* (const Mat &l, const Mat &r) {
	Mat x = {
		(array<mint, 2>){0,0},
		(array<mint, 2>){0,0}
	};
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				x[i][j] += l[i][k] * r[k][j];
			}
		}
	}
	return x;
}

Mat seg_op (Mat l, Mat r) {
	return l * r;
}
Mat seg_e (void) {
	return unity;
}

// n boxes, r balls into unique boxes, no adjacent boxes
mint noadj (ll n, ll r) {
	if (n < r || r < 0) return 0;
	return ncr((n + 1) - r, r);
}

Mat lenmat (ll n, ll r) {
	Mat x;
	x[0][0] = noadj(n-1, r);
	if (n == 1) {
		x[0][1] = noadj(0, r-1);
	} else {
		x[0][1] = noadj(n-2, r-1);
	}
	if (n == 1) {
		x[1][0] = noadj(0, r);
	} else {
		x[1][0] = noadj(n-2, r);
	}
	if (n == 1) {
		x[1][1] = 0;
	} else if (n == 2) {
		x[1][1] = noadj(0, r-1);
	} else {
		x[1][1] = noadj(n-3, r-1);
	}
	
	return x;
}

map<ll, ll> stidx; // set of i such that a_i != -1
void solve () {
	segtree<Mat, seg_op, seg_e> seg(n);

	vector<mint> fib(n+1);
	fib[0] = 1;
	fib[1] = 2;
	for (ll i = 2; i <= n; i++) {
		fib[i] = fib[i-2] + fib[i-1];
	}

	stidx.insert({-1, 0}); // bottom
	stidx.insert({n, n}); // top
	for (ll qi = 0; qi < q; qi++) {
		ll x, y;
		cin >> x >> y;
		--x;

		// erase
		{
			auto it = stidx.find(x);
			if (it != stidx.end()) {
				--it; ll ilow  = (*it).first, vlow  = (*it).second; ++it;
				++it; ll ihigh = (*it).first, vhigh = (*it).second; --it;

				stidx.erase(it);
				seg.set(x, unity);
				if (ihigh < n) seg.set(ihigh, lenmat(ihigh - ilow, vhigh - vlow));
				
			}
		}

		// add
		if (y != -1) {
			stidx.insert({x, y});
			auto it = stidx.find(x);
			--it; ll ilow  = (*it).first, vlow  = (*it).second; ++it;
			++it; ll ihigh = (*it).first, vhigh = (*it).second; --it;

			seg.set(x, lenmat(x - ilow, y - vlow));
			if (ihigh < n) seg.set(ihigh, lenmat(ihigh - x, vhigh - y));
		}

		// answer
		Mat whole = seg.all_prod();
		ll remain;
		{
			auto it = stidx.find(n);
			--it; ll idx = (*it).first;

			remain = (n-1) - idx;
		}
		mint ans = 0;
		ans += whole[0][0] * fib[remain];
		ans += whole[0][1] * fib[max(remain - 1, 0LL)];


		cout << ans.val() << "\n";
	}
	
	return;
}

int main (void) {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> q;

	solve();

	return 0;
}