C - Pigeonhole Query
Source: atcoder
Difficulty: 300

Problem Statement
There are
N
pigeons numbered from
1
to
N
, and there are
N
nests numbered from
1
to
N
. Initially, pigeon
i
is in nest
i
for
1\leq i\leq N
.
You are given
Q
queries, which you must process in order. There are two types of queries, each given in one of the following formats:
1 P H
: Move pigeon
P
to nest
H
.
2
: Output the number of nests that contain more than one pigeon.
Constraints
2 \leq N \leq 10^6
1 \leq Q \leq 3\times 10^5
1 \leq P, H \leq N
For a query of the first type, pigeon
P
is not in nest
H
before the move.
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is given in one of the following two formats:
1
P
H
2
Output
Print the answer to each query on a new line according to the instructions in the problem statement.
Sample Input 1
4 7
2
1 1 2
2
1 3 2
2
1 3 4
2
Sample Output 1
0
1
1
2
Initially, pigeons
1,2,3,4
are in nests
1,2,3,4
, respectively.
For the 1st query, the counts of pigeons in nests
1,2,3,4
are
1,1,1,1
. No nests contain multiple pigeons, output
0
.
For the 2nd query, move pigeon
1
to nest
2
.
For the 3rd query, the counts become
0,2,1,1
, respectively. One nest (nest
2
) contains multiple pigeons, so output
1
.
For the 4th query, move pigeon
3
to nest
2
.
For the 5th query, the counts become
0,3,0,1
, respectively. One nest (nest
2
) contains multiple pigeons, so output
1
.
For the 6th query, move pigeon
3
to nest
4
.
For the 7th query, the counts become
0,2,0,2
, respectively. Two nests (nests
2
and
4
) contain multiple pigeons, so output
2
.
Sample Input 2
5 10
2
1 4 3
1 4 5
2
1 3 1
2
1 2 3
1 2 5
1 1 3
2
Sample Output 2
0
1
2
1

C++ solution:
#include <bits/stdc++.h>

using namespace std;

// #define ls p << 1
// #define rs p << 1 | 1
#define x first
#define y second

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100010;

void solve(){
    int n, q;
    std::cin >> n >> q;

    std::vector<int> siz(n + 1), idx(n + 1);
    for (int i = 1; i <= n; i ++) siz[i] = 1, idx[i] = i;

    int cnt = 0;
    for (int _ = 1; _ <= q; _ ++){
        int op, x, h;
        std::cin >> op;

        if (op == 1){
            std::cin >> x >> h;

            
            if (siz[idx[x]] == 2) cnt --;
            siz[idx[x]] --;

            if (siz[h] == 1) cnt ++;
            idx[x] = h, siz[h] ++;
            
        }else {
            std::cout << cnt << '\n';
        }
    }
}

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);

    int T = 1;
    // std::cin >> T;

    while (T --){
        solve();
    }

    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt32)

	N, Q := readInt(), readInt()
	pigeons := make([]int, N) // 鳩がどこの巣にいるかを管理する
	for i := 0; i < N; i++ {
		pigeons[i] = i
	}
	holes := make([]int, N) // それぞれの巣に何羽の鳩がいるか管理する
	for i := 0; i < N; i++ {
		holes[i] = 1
	}
	ans := 0
	for i := 0; i < Q; i++ {
		q := readInt()
		if q == 1 {
			P, H := readInt()-1, readInt()-1
			// 鳩Pが今いる巣が移動後に複数いる巣ではなくなる場合、ansをマイナスする
			if holes[pigeons[P]] == 2 {
				ans--
			}
			// 鳩Pが現在いる巣の数を減らす
			holes[pigeons[P]]--

			// 鳩Pが巣Hに移動後、複数羽がいる巣になる場合、ansをプラスする
			if holes[H] == 1 {
				ans++
			}
			// 鳩Pを巣Hに移動させる
			pigeons[P] = H
			// 巣Hにいる数を増やす
			holes[H]++
		} else {
			out(ans)
		}
	}

}

func out(x ...interface{}) {
	fmt.Fprintln(wr, x...)
}

func outStrings(x []string) {
	out(strings.Join(x, " "))
}

func outInts(x []int) {
	y := make([]string, len(x))
	for i := 0; i < len(x); i++ {
		y[i] = strconv.Itoa(x[i])
	}
	outStrings(y)
}

func readInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func readInt64() int64 {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(), 0, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func readFloat() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func readInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = readInt()
	}
	return ret
}

func readFloats(N int) []float64 {
	ret := make([]float64, N)
	for i := 0; i < N; i++ {
		ret[i] = readFloat()
	}
	return ret
}

func readText() string {
	sc.Scan()
	return sc.Text()
}

func readRune() []rune {
	sc.Scan()
	return []rune(sc.Text())
}

// min, max, aSub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// min for n entry
func nMin(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = min(ret, e)
	}
	return ret
}

// max for n entry
func nMax(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = max(ret, e)
	}
	return ret
}

func chMin(a *int, b int) bool {
	if *a < b {
		return false
	}
	*a = b
	return true
}

func chMax(a *int, b int) bool {
	if *a > b {
		return false
	}
	*a = b
	return true
}

func aSub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func swap(a, b *int) {
	*a, *b = *b, *a
}

func swapArrElm(a []int, i, j int) {
	a[i], a[j] = a[j], a[i]
}

Java solution:
import java.util.*;
import java.io.*;

public class Main{
	public static void main(String[] args) throws Exception {
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		
		int[] birdPosition = new int[N+1];
		int[] count = new int[N+1];
		
		for (int i = 1; i <= N; i++) {
			birdPosition[i] = i;
			count[i] = 1;
		}
		
		int cnt = 0;
		for (int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine()," ");
			if(st.nextToken().equals("1")) {
				int bird = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				
				count[birdPosition[bird]]--;
				if(count[birdPosition[bird]] == 1) {
					cnt--;
				}
				birdPosition[bird] = to;
				count[birdPosition[bird]]++;
				if(count[birdPosition[bird]] == 2) {
					cnt++;
				}
			}
			else {
				sb.append(cnt).append("\n");
			}
		}
		
		System.out.println(sb.toString());
	}
	
}

JavaScript solution:
function main(input) {
  const inputArray = input.split("\n");
  const [N, Q] = inputArray[0].split(" ").map(Number);

  let bird_home = Array(N + 1).fill(0); // bird_home[i] は鳩iがどの巣にいるか
  let home_count = Array(N + 1).fill(0); // home_count[h] は巣hに何羽の鳩がいるか
  let multiple_birds_count = 0; // 複数の鳩がいる巣の数
  
  // 初期配置
  for (let i = 1; i <= N; i++) {
    bird_home[i] = i; // 鳩iは巣iにいる
    home_count[i] = 1; // 最初は各巣に1羽
  }
  
  // 複数の鳩がいる巣を数える関数
  function update_multiple_birds_count(home, oldCount, newCount) {
    if (oldCount >= 2) multiple_birds_count--;
    if (newCount >= 2) multiple_birds_count++;
  }

  // クエリ処理
  let output = [];
  for (let j = 1; j <= Q; j++) {
    const query = inputArray[j].split(" ").map(Number);

    if (query[0] === 1) {
      // 鳩Pを巣Hに移動させるクエリ
      const P = query[1];
      const H = query[2];

      const current_home = bird_home[P]; // 鳩Pが現在いる巣
      if (current_home === H) continue; // もし移動先が現在の巣なら何もしない

      // 現在の巣の鳩数を更新
      home_count[current_home]--;
      update_multiple_birds_count(current_home, home_count[current_home] + 1, home_count[current_home]);

      // 新しい巣の鳩数を更新
      home_count[H]++;
      update_multiple_birds_count(H, home_count[H] - 1, home_count[H]);

      // 鳩Pの移動先を更新
      bird_home[P] = H;

    } else if (query[0] === 2) {
      // 複数の鳩がいる巣の数を出力
      output.push(multiple_birds_count);
    }
  }
  
  console.log(output.join("\n"));
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

Python solution:
n, q = map(int, input().split())

arr_pig = [i+1 for i in range(n)]
arr_hole = [1] * n
m_hole = 0

for i in range(q):
    q = input()

    if q[0] == '1':
        q, pigeon, hole_after = map(int, q.split())
        hole_before = arr_pig[pigeon-1]

        if arr_hole[hole_before-1] == 2:
            m_hole -= 1
        if arr_hole[hole_after-1] == 1:
            m_hole += 1

        arr_pig[pigeon-1] = hole_after
        arr_hole[hole_before-1] -= 1
        arr_hole[hole_after-1] += 1
    elif q[0] == '2':
        print(m_hole)

Ruby solution:
# Your code here!

N, Q = gets.split.map(&:to_i)

ma = Array.new(N, 1)
poses = (0...N).to_a
multi = 0
Q.times{
    c, p, h = gets.split.map(&:to_i)
    if c==1
        p-=1
        h-=1
        pos = poses[p]
    #puts "1.-:#{ma.join(',')}, multi:#{multi}, pos:#{pos}, p:#{p}, h:#{h}"
        if ma[h] == 1
            multi += 1
        end
        if ma[pos]==2
            multi -= 1
        end
    #puts "2.0:#{ma.join(',')}, multi:#{multi}, pos:#{pos}, p:#{p}, h:#{h}"
        ma[h] += 1
    #puts "2.1:#{ma.join(',')}, multi:#{multi}, pos:#{pos}, p:#{p}, h:#{h}"
        ma[pos] -= 1
        poses[p] = h
    #puts "2.2:#{ma.join(',')}, multi:#{multi}, pos:#{pos}, p:#{p}, h:#{h}"
    end
    if c==2
        puts multi
    end
}