AtCoder Regular Contest 077F: SS

実験的にやるのがたぶん正攻法だけど、もうちょっと文字列の周期のこととかに気を配れるとよかった。

解説にも書いてありますが、g(n+2)=g(n+1)+g(n)になります。これは実験をすると比較的簡単に気づけます。
証明は
g(n)→g(n+1)にするということは、g(n)の接頭辞と接尾辞で一致しているもののうち、文字数が最大のものをTとすると、
g(n+1)=g(n)*2-Tとなるので、g(n)=S*n+S'とすれば
g(n+1)=S*n+S'+S(T=S*(n-1)+S'より)
g(n+2)=(S*n+S'+S)+(S*n+S') (T=Sより)
=g(n+1)+g(n)となります。

g(0)=T*n+T'とすると、g(1)=T*n+T'+Tであり、MP法を使えばTは求められるので解けました。
副産物として文字列の長さをNとしてMP[N]=aならば最初のN-a文字が文字列の周期であることもわかりました。


気づいたは気づいたんだけど、証明をどうすればいいかわかりませんでした。
文字列は周期が重要ということを完全に忘れてましたね…。

int N; ll L, R;
int A[MAX_N];
ll C[210][26];
ll D[210];

vector<int> MP(string S) { //it doesn't include itself
	int n = (int)S.size();
	vector<int> A(n + 1);
	A[0] = -1;
	rep(i, 0, n) {
		int j = A[i];
		while (j >= 0 && S[i] != S[j]) j = A[j];
		j++;
		A[i + 1] = j;
	}
	return A;
}

vi calc1(ll n) {
	ll a = n / N;
	ll b = n % N;
	vector<ll> cnt1(26, 0);
	vector<ll> cnt2(26, 0);
	rep(i, 0, N) {
		if(i < b) cnt2[A[i]]++;
		cnt1[A[i]]++;
	}
	rep(i, 0, 26) cnt1[i] = cnt1[i] * a + cnt2[i];
	return cnt1;
}

vi calc2(ll n, int m) {
	vector<ll> res(26, 0);
	for(int i = m - 1; i >= 0; i--) {
		if(n - D[i] >= 0) {
			n -= D[i];
			rep(j, 0, 26) {
				res[j] += C[i][j];
			}
		}
	}
	rep(i, 0, n) res[A[i]]++;
	return res;
}

void solve() {
	string str;
	cin >> str;
	N = sz(str) / 2;
	string tmp;
	rep(i, 0, N) tmp += str[i];
	int a = MP(tmp)[N];

	rep(i, 0, N) A[i] = str[i] - 'a';
	cin >> L >> R; L--;
	if(a == 0) {
		vi lv = calc1(L);
		vi rv = calc1(R);
		rep(i, 0, 26) {
			rv[i] -= lv[i];
			cout << rv[i] << " ";
		}
		cout << "\n";
	}
	else {
		rep(i, 0, N) {
			C[0][A[i]]++; C[1][A[i]]++;
			if(i < N - a) C[1][A[i]]++;
		}
		D[0] = N; D[1] = 2 * N - a;
		int i = 0;
		for(i = 2; ; i++) {
			D[i] = D[i - 1] + D[i - 2];
			rep(j, 0, 26) C[i][j] = C[i - 1][j] + C[i - 2][j];
			if(D[i] >= R) break;
		}
		vi lv = calc2(L, i);
		vi rv = calc2(R, i);
		rep(i, 0, 26) {
			rv[i] -= lv[i];
			cout << rv[i] << " ";
		}
		cout << "\n";
	}
}

AtCoder Grand Contest 019D: Shift and Flip

なんとなくの解法はわかるけど詰めるのが結構難しいと思う。

Sをiだけ右にshiftした場所でTと一致させることを考える。
移動したSとTを比較したとき、Si == 1 && Ti == 0のとき、その場でSiを0に反転させることができない。ほかの場合はその場で反転できるorそもそも一致しているなので、このような場合のみについて考えることにする。

Siを0にするためには、Tj == 1を満たす場所で反転を行う必要がある。何回shiftすればTj == 1となる場所と対応するかを右shift左shiftについて配列を持っておく。

各iについて右shiftまたは左shiftを選べばよいことになるが、shift0から順番に見ていくと右右…右左左…左の時が最適になることがわかる。右左右なら左を右にしても結果は変わらないからだ。
なので右から左に変えるところをn回試せば求めるべき値が求まる。

int N;
string S, T;
int A[MAX_N], B[MAX_N];
int C[MAX_N], M[MAX_N];

void solve() {
	cin >> S >> T;
	N = sz(S);
	fill(A, A + N, inf);
	rep(i, 0, N) {
		rep(j, 0, N) {
			if(T[(i + j) % N] == '1') {
				A[i] = min(A[i], j);
				B[i] = max(B[i], j);
			}
		}
	}
	if(A[0] == inf) {
		bool ok = true;
		rep(i, 0, N) if(S[i] == '1') ok = false;
		if(ok) cout << 0 << "\n";
		else cout << -1 << "\n";
		return;
	}
	int res = inf;
	rep(i, 0, N) {
		int tmp = 0;
		fill(C, C + N, inf);
		rep(j, 0, N) {
			if(T[(i + j) % N] != S[j]) {
				tmp++;
				if(S[j] == '1') MIN(C[A[j]], B[j]);
			}
		}
		fill(M, M + N + 1, inf);
		int mi = -1, mx;
		rer(j, N, 0) {
			M[j] = min(M[j + 1], C[j]);
			if(C[j] != inf) MAX(mi, j);
		}
		mx = M[0];
		if(mx == inf) MIN(res, tmp + min(i, N - i));
		else {
			MIN(res, tmp + mi + min(abs(mi - i), N - abs(mi - i))); 
			MIN(res, tmp + N - mx + min(abs(mx - i), N - abs(mx - i))); 
		}
		rep(j, 0, N) {
			if(C[j] != inf) {
				mi = j; mx = M[j + 1];
				if(mx == inf) continue;
				MIN(res, tmp + mi + N - (mx - mi) + min(abs(mx - i), N - abs(mx - i)));
				MIN(res, tmp + N - mx + N - (mx - mi) + min(abs(mi - i), N - abs(mi - i)));
			}
		}
	}
	cout << res << "\n";
}

こういう問題を素早く解けるようになるといいね。

赤黒木

最初に
これいる?

要はmergeとかsplitとかできるようになった強い配列です。ここらへんを参考にして実装しました。
https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4-copypaste-slides.pdf
http://algoogle.hadrori.jp/algorithm/prbtree.html
http://algoogle.hadrori.jp/algorithm/rbtree_merge.html
http://hogloid.hatenablog.com/entry/20120407/1333788248

なんとmerge/split baseの赤黒木は平衡の仕方を2種類覚えるだけで実装できます。これは絶対Splay木とかよりも楽。zig-zagとか絶対忘れるし。さらに永続化もできて、最強感が漂っています。
でも平衡木を使う機会が競プロではほとんどなく、永続平衡木なんてcopy and pasteくらいだと思います。
大体平衡木使おうとおもってもsegtreeとかで済む場合が多いのでライブラリ化したところであまり使わなさそうです…。

template<class T>
struct rbvector { //added insert O(logn), but random access is O(logn) too
	const bool black = false;
	const bool red = true;
	struct node {
		T t;
		bool color; int rnk, sz;
		node *nl, *nr;
	};
	typedef pair<node*, node*> np;

	node *root;
	inline int size() { return !root ? 0 : root->sz; }
	inline void update(node *a) {
		if(!a->nl) { a->rnk = 0; a->sz = 1; }
		else {
			a->rnk = a->nl->rnk + (a->nl->color == black);
			a->sz = a->nl->sz + a->nr->sz;
		}
	}
	node *new_node(bool color, T t, node *nl = NULL, node *nr = NULL) {
		node *nn = new node();
		nn->nl = nl; nn->nr = nr; nn->color = color; nn->t = t;
		update(nn);
		return nn;
	}
	node *merge_sub(node *a, node *b) {
		if(a->rnk < b->rnk) {
			node *c = merge_sub(a, b->nl);
			b->nl = c;
			if(b->color == black && c->color == red && c->nl->color == red) {
				if(b->nr->color == black) {
					node *y = c->nr;
					c->nr = b; b->nl = y;
					b->color = red; c->color = black;
					update(b); update(c);
					return c;
				}
				else {
					b->color = red;
					c->color = b->nr->color = black;
					update(c); update(b);
					return b;
				}
			}
			else { update(b); return b; };
		}
		else if(a->rnk > b->rnk) {
			node *c = merge_sub(a->nr, b);
			a->nr = c;
			if(a->color == black && c->color == red && c->nr->color == red) {
				if(a->nl->color == black) {
					node *y = c->nl;
					c->nl = a; a->nr = y;
					a->color = red; c->color = black;
					update(a); update(c);
					return c;
				}
				else {
					a->color = red;
					c->color = a->nl->color = black;
					update(c); update(a);
					return a;
				}
			}
			else { update(a); return a; }
		}
		else {
			node *c = new_node(red, T(), a, b);
			return c;
		}
	}
	node *merge(node *a, node *b) {
		if(!a) return b;
		if(!b) return a;
		a->color = black; update(a);
		b->color = black; update(b);
		node *c = merge_sub(a, b);
		c->color = black;
		return c;
	}
	np split(node *v, int k) {
		if(k <= 0) return np(NULL, v);
		if(k >= v->sz) return np(v, NULL);
		if(k < v->nl->sz) {
			np p = split(v->nl, k);
			return np(p.fst, merge(p.sec, v->nr));
		}
		else if(k > v->nl->sz) {
			np p = split(v->nr, k - v->nl->sz);
			return np(merge(v->nl, p.fst), p.sec);
		}
		else return np(v->nl, v->nr);
	}

	T& get_sub(node *a, int k, int l, int r) {
		if(r - l == 1) return a->t;
		if(k < a->nl->sz) return get_sub(a->nl, k, l, l + a->nl->sz);
		else return get_sub(a->nr, k - a->nl->sz, l + a->nl->sz, r);
	}
	void insert(const rbvector& sa, int k) { //after insert, sa is broken
		np p = split(root, k);
		root = merge(merge(p.fst, sa.root), p.sec);
	}
	void insert(T t, int k) {
		np p = split(root, k);
		root = merge(merge(p.fst, new_node(black, t)), p.sec);
	}
	T& get(int k) { return get_sub(root, k, 0, size()); }
	T& operator[](int k) { return get(k); }
	void push_back(const rbvector& sa) { insert(sa, size()); }
	void push_back(T t) { insert(t, size()); }

	friend ostream& operator<<(ostream& out, rbvector& sa){
		out << "[";
		rep(i, 0, sa.size() - 1) {
			out << sa.get(i) << ", ";
		}
		out << sa.get(sa.size() - 1) << "]";
		return out;
	}
};

mergeを見るとこうなっています。

node *merge(node *a, node *b) {
	if(!a) return b;
	if(!b) return a;
	a->color = black; update(a);
	b->color = black; update(b);
	node *c = merge_sub(a, b);
	c->color = black;
	return c;
}

上のhosさんのスライドと比べてa->color = blackという行が追加されています。それはなぜかというとsplitから根が赤色の木が出てくる可能性があるからです。
根を赤→黒にしてもrankに影響は出ないので、mergeするとき、2つの木の根を黒色にしてから処理するようにしています。

ちなみに永続化のコードはもっとシンプルになってえぇ…と困惑するかもしれませんが、めんどくさい処理をnew_nodeに押し付けられるからですね。

完全永続データ構造をマージする一般的なテクニック系Union Findを実装しようと思って永続配列を作ろう!ってなったんですが、そもそもそんなUF作ったところで使うところがないことに気づいて虚無です。

2-SAT

(P||Q||...)&(R||S||...)みたいな連言標準形で書かれた論理式を真にする割り当てはあるかを判定する問題をSATといいます。
2-SATの場合カッコ内のリテラル数が高々2つ、つまり(P||Q)&(R||S)みたいになってます。

2-SATの解き方は蟻本の通り、SCCを使って真のnodeと偽のnodeが同じcycle内に属さないことを確認すればよいです。割り当てはトポロジカル順序を確認すればいいです。

直感的に「ならば」の矢印の記号に沿って有向辺を張っていけばよいことがわかりますが、どうやって証明すればいいのでしょう。

僕は最初SCCした後のグラフを二部グラフっぽい形に変形して二部グラフの片側を真、反対側を偽にすればうまくいくことを証明しようとして失敗しました。なので1978年に出たTarjanの論文を読むことにしました。以下リンク。
https://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/2SAT.pdf

これを見ると次の真偽割り当てアルゴリズムを使って証明していることがわかります。

SCC後のグラフのトポロジカルソートを逆順から見て、
Sがマークされていたらなにもしない
Sがマークされていないとき、
S==!S(!SはSの真偽をswapさせた点の集合)ならreturn false
それ以外S=true,S=falseとする

このアルゴリズムでP(T)->Q(F)(P(T)はPの割り当てをTrueにしたということ)のような辺が生じると仮定すると、
!QはQよりもトポロジカル順で後ろで
!PはPよりもトポロジカル順で前になります。
P->Qに辺が張ってあるならば、!Q→!Pにも辺が存在し、!Q->!P->..->P->Q->...!Qのループが生じていることがわかります。
これはSCCした後のグラフがDAGであることに矛盾するので、この割り当てアルゴリズムは正しいと証明されました。

さらにこの証明で真偽の割り当てはSと!Sのトポロジカル順を比べて、Sの方が遅ければ真、!Sが遅ければ偽とすればいいことがわかりました。
蟻本のコードはこれをもとにしているわけですね。

論文にはさらにリテラルについて∃または∀の記号がついている際の真偽値の割り当ての方法に言及していますが、そこまではしなくてよさそう。


同じような問題として、(P&Q...)||(S&T...)||みたいな選言標準形をした論理式たちをさらに&でつないでいるものがあります。
いわれてもわけがわからないと思うので例をあげると、蟻本p85の食物連鎖(POJ1182)です。

Union-Findで同時に起こりうるものを管理していますが、これがうまくいく証明は簡単です。


→はSAT、&はUnionFindという認識くらい持っていると思いつけるようになりそうですね。

Euler Tour

Euler Tourは木を直線にして扱いやすくするテクニックです。
これを使うとLCA、二点間のpathの長さがO(logN)で求められます。

でもHL分解ならあるpath上の辺の長さをすべて+1するみたいなこともできるので、汎用性はHL分解の方が上です。
HL分解は実装が重いというのが弱点ですが、ライブラリ化しているのでわざわざEuler-Tourを使うことはあまりなさそうですね。

オンサイトで持ち込み禁止とかなら(まさにJOI)Euler-Tourを書くけど…JOIerがEuler-Tourを推すのはこのためか…

struct T {
	pi v;
	T(pi v = pi(inf, -1)) : v(v) {}
	T operator+(const T& t) { return T(min(v, t.v)); }
	friend ostream& operator<<(ostream& out, const T& t) {
		out << t.v; return out;
	}
};

struct segtree{
	int n; vector<T> seg;
	void init(int mx) {
		n = 1;
		while(n < mx) n *= 2;
		seg = vector<T>(n * 2);
	}
	segtree(int mx = 0) {
		init(mx);
	}
	void update(int i, T x) {
		i += n - 1;
		seg[i] = x;
		while(i > 0) {
			i = (i - 1) / 2;
			seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2];
		}
	}
	T ga(int a, int b, int k, int l, int r) {
		if(b <= l || r <= a) return T();
		if(a <= l && r <= b) return seg[k];
		else {
			T lv = ga(a, b, k * 2 + 1, l, (l + r) / 2);
			T rv = ga(a, b, k * 2 + 2, (l + r) / 2, r);
			return lv + rv;
		}
	}
	void show() {
		vector<T> tmp;
		rep(i, 0, n) tmp.push_back(get(i, i + 1));
		debug(tmp);
	}
	//edit from here
	T get(int a, int b) { return ga(a, b, 0, 0, n); } //[a, b)
};

struct BIT { //0-origin!!!
	int n; vi bit0, bit1;
	void init(int mx) {
		n = mx;
		bit0 = vi(n + 1, 0); bit1 = vi(n + 1, 0);
	}
	BIT(int mx = 0) { init(mx); } 

	ll ga(vi& bit, int i) {
		ll s = 0;
		while(i > 0) { s += bit[i]; i -= i & -i; }
		return s;
	}
	void app(vi& bit, int i, ll x) {
		while(i <= n) { bit[i] += x; i += i & -i; }
	}
	void update(int a, int b, ll x) { //[a, b)
		a++;
		app(bit0, a, -x * (a - 1));
		app(bit1, a, x);
		app(bit0, b + 1, x * b);
		app(bit1, b + 1, -x);
	}
	ll get(int a, int b) { //[a, b)
		a++;
		return (ga(bit1, b) * b + ga(bit0, b)) 
			- (ga(bit1, a - 1) * (a - 1) + ga(bit0, a - 1));
	}
};

namespace ET {
	struct edge { int to, cost; };
	int n;
	vector<edge> G[MAX_N];
	int root;
	int cost[MAX_N * 2]; //2 * n - 2
	int vs[MAX_N * 2]; //2 * n - 1
	int depth[MAX_N * 2]; //2 * n - 1
	int idb[MAX_N], ide[MAX_N]; //(e:v->p)'s cost: cost[idb[v] - 1](>0) or cost[ide[v]](<0)
	segtree seg;
	BIT bit;

	void add_edge(int a, int b, int cost) {
		G[a].pb(edge{b, cost});
		G[b].pb(edge{a, cost});
	}
	void dfs(int v, int p, int d, int pc, int &k) {
		idb[v] = k;
		vs[k] = v;
		depth[k++] = d;
		rep(i, 0, G[v].size()) {
			edge& e = G[v][i];
			if(e.to == p) continue;
			cost[k - 1] = e.cost;
			dfs(e.to, v, d + 1, e.cost, k);
			vs[k] = v;
			depth[k++] = d;
		}
		if(pc != -1) cost[k - 1] = -pc;
		ide[v] = k - 1;
	}
	void init(int nn, int nroot = 0) {
		n = nn; root = nroot;
		int k = 0; dfs(root, -1, 0, -1, k);
		seg.init(2 * n - 1); rep(i, 0, 2 * n - 1) seg.update(i, T(pi(depth[i], i)));
		bit.init(2 * n - 2); rep(i, 0, 2 * n - 2) bit.update(i, i + 1, cost[i]);
	}

	int lca(int u, int v) {
		int a = idb[u], b = idb[v];
		if(a > b) swap(a, b);
		return vs[seg.get(a, b + 1).v.sec];
	}
	ll path_cost(int u, int v) {
		int p = lca(u, v);
		int a = idb[u], b = idb[p], c = idb[v];
		return bit.get(min(a, b), max(a, b)) + bit.get(min(b, c), max(b, c));
	}
	void change_cost(int v, int c) {
		int a = cost[idb[v] - 1];
		cost[idb[v] - 1] = c; cost[ide[v]] = -c;
		bit.update(idb[v] - 1, idb[v], c - a);
		bit.update(ide[v], ide[v] + 1, a - c);
	}
	void show() {
		debug("cost", vi(cost, cost + n * 2 - 2));
		debug("vs", vi(vs, vs + n * 2 - 1));
		debug("depth", vi(depth, depth + n * 2 - 1));
		debug("idb", vi(idb, idb + n));
		debug("ide", vi(ide, ide + n));
	}
};

永続segtree

永続は怖いイメージがあると思いますが、segtreeくらいなら簡単に永続化できます。
単にupdateされる予定のnodeを複製して、その複製されたnodeに対してupdateを行えばいいです。
普通のセグ木に複製してリンクを張り替えるコストが増えただけで更新の計算量は変わらずO(logN)です。

永続にすると何が嬉しいんだっていう話になりますが、例えば配列A[a, b)内でk以下の値の個数を数えよみたいな問題が1クエリあたりO(logN)で解けるようになります。
どうやるかというと、まず区間sumができる永続segtree Sを用意します。A内の数字をsortして、小さい順に見ていきます。数字がもとにあった場所をvとして、Sの最新バージョンに対してS(v)に1を足す更新を行います。これで前処理は終了です。
クエリは、Aの中でk以下で最大の数字に対して処理を行ったバージョンに対して[a, b)の区間和をとればいいです。以上で前処理(NlogN)、クエリ一つ当たりO(logN)で計算できました。

l以上k以下も簡単にできるので、(k以下の値からl-1以下の値を引けばよい)二次元座標のx軸y軸に平行な辺を持つ長方形内の点の数を数えるのもO(logN)できます。

struct T {
	ll v;
	T(ll v = 0) : v(v) {}
	T operator+(const T& t) { return T(v + t.v); }
	friend ostream& operator<<(ostream& out, const T& t) {
		out << t.v; return out;
	}
};

struct p_segtree {
	struct node { T t; node *ln, *rn; };
	int n;
	vector<node*> roots;
	inline int latest(int k) { return k == -1 ? (int)roots.size() - 1 : k; }
	void init(int mx) {
		n = 1;
		while(n < mx) n *= 2;
		vector<node*> nodes(2 * n - 1);
		rep(i, 0, 2 * n - 1) {
			node* nn = new node();
			nodes[i] = nn;
		}
		rep(i, 0, n - 1) {
			nodes[i]->ln = nodes[i * 2 + 1];
			nodes[i]->rn = nodes[i * 2 + 2];
		}
		roots.pb(nodes[0]);
	}
	p_segtree(int mx = -1) {
		if(mx != -1) init(mx);
	}
	void app(int a, T x, node* root, int l, int r) {
		int b = a + 1;
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) root->t = x;
		else {
			node* nln = new node(*(root->ln));
			node* nrn = new node(*(root->rn));
			root->ln = nln; root->rn = nrn;
			app(a, x, nln, l, (l + r) / 2);
			app(a, x, nrn, (l + r) / 2, r);
			root->t = root->ln->t + root->rn->t;
		}
	}

	T ga(int a, int b, node* root, int l, int r) {
		if(b <= l || r <= a) return T();
		if(a <= l && r <= b) return root->t;
		else {
			T lv = ga(a, b, root->ln, l, (l + r) / 2);
			T rv = ga(a, b, root->rn, (l + r) / 2, r);
			return lv + rv;
		}
	}
	void update(int a, T t, int k = -1) {
		k = latest(k);
		node* nroot = new node(*roots[k]);
		roots.pb(nroot);
		app(a, t, nroot, 0, n);
	}
	T get(int a, int b, int k = -1) {
		k = latest(k);
		return ga(a, b, roots[k], 0, n);
	}
	void show(int k = -1) {
		vector<T> tmp;
		rep(i, 0, n) tmp.pb(get(i, i + 1, k));
		debug(tmp);
	}
};

似たような問題で蟻本のデータ構造の章のK-th Numberも永続segtreeを使ってシンプルに書けます。計算量は(NlogN+Mlog^2N)です。

int N, M;
p_segtree seg;
pi A[MAX_N];

bool ok(int a, int b, int t, int m) {
	return seg.get(a, b, m + 1).v >= t;
}

int main() {
	scanf("%d%d", &N, &M);
	seg.init(N);
	rep(i, 0, N) {
		scanf("%d", &A[i].fst);
		A[i].sec = i;
	}
	sort(A, A + N);
	rep(i, 0, N) {
		seg.update(A[i].sec, T(1));
	}
	while(M--) {
		int a, b, t;
		scanf("%d%d%d", &a, &b, &t); a--;
		int lv = -1, rv = N;
		while(rv - lv > 1) {
			int m = (lv + rv) / 2;
			if(ok(a, b, t, m)) rv = m;
			else lv = m;
		}
		printf("%d\n", A[rv].fst);
	}
}

実装これだけで済んですごい。でも空間量もO(NlogN)なのでTLEしました…POJの定数倍ゲーやめて。

似たような問題を永続データ構造なしで解くとしたらwavelet木になるので、こっちも勉強したいですね。

AGC017C: Snuke and Spells

http://agc017.contest.atcoder.jp/tasks/agc017_c

解説を見るとこんなうまいやり方があったのかぁ…となるんですが、それをどうやって思いつけるようになるかが重要だと思います。
僕はこう考えたらしっくりきました。

まず魔法をかける前、ボールがどうなっているか見てみます。例えば
2 2 5 5 5 6
について考えて
1 2 3 4 5 6と「見比べる」と、2つの5が3,4に、1つの2が1になっていることがわかります。
つまりnがk個あると、n,n-1,...,n-k+1に「言い換えられる」ような気がしてきます。

この言い換えをボールの数を変える前の数列に「適応」してみましょう。

3 3 4 5 5 6は
2 3 4 4 5 6となります。ここまでくれば、4がダブっているので4のどっちかを1に変えればうまくいくとわかります。

これを区間で表したのが解説となります。

このようにまず性質がいいものを特殊なケースと「見比べる」ことで、「言い換え」を思いつき、それをいろんなケースにも「適応」してみるのが、競プロでありがちな思考回路な気がします。

性質がいいものってなんだよと思いますが、例えば等差数列だったり、時系列で物を使っていく問題なら時間がそれに該当すると思います。

本番は1,2,3...と見比べるところまでは言ったが、言い換えるところに至らず、500点どまり。言い換えるのが苦手なのはいろんな問題を通じてわかっているので、強く意識すべきですね。

int N, M;
int S[MAX_N], A[MAX_N], C[MAX_N];

void solve() {
	cin >> N >> M;
	rep(i, 0, N) {
		int a; cin >> a; a--;
		A[i] = a;
		if(a - C[a] >= 0) S[a - C[a]]++;
		C[a]++;
	}
	int res = 0;
	rep(i, 0, N) res += S[i] ? 1 : 0;
	rep(i, 0, M) {
		int a, b;
		cin >> a >> b; a--; b--;
		int pb = A[a];
		A[a] = b;
		if(pb - C[pb] + 1 >= 0) {
			S[pb - C[pb] + 1]--;
			if(!S[pb - C[pb] + 1]) res--;
		}
		C[pb]--;
		if(b - C[b] >= 0) {
			S[b - C[b]]++;
			if(S[b - C[b]] == 1) res++;
		}
		C[b]++;
		cout << N - res << "\n";
	}
}

こういう抽象的なことって言葉にするのが難しいですね。