Mục lục
[TOC]

# Truy vấn mảng [QUERY]
> Bài 2/3, HSG lớp 9 - Vĩnh Phúc - 2023-2024
:::spoiler **Đề bài**

Cho dãy gồm $N$ phần tử $a_1, a_2, \ldots, a_N$. Bạn cần thực hiện $P$ truy vấn, mỗi truy vấn thuộc một trong hai loại sau:
- Loại 1: Dịch chuyển phần tử ở vị trí thứ $N$ về vị trí thứ 1, các phần tử còn lại dịch sang phải một vị trí;
- Loại 2: Tìm đoạn con độ dài $K$ có nhiều phần tử có giá trị bằng 1 nhất. In ra số lượng phần tử có giá trị 1 trong đoạn tìm được.

### Dữ liệu
- Dòng 1: Chứa ba số nguyên $N, K, P$ $(1\le N,K,P\le10^5)$;
- Dòng 2: Chứa $N$ số nguyên $a_1, a_2, \ldots, a_N$ $(a_i \in \{0,1\}, 1\le i\le N)$;
- Dòng 3: Chứa một xâu bao gồm $P$ kí tự, kí tự thứ $i$ $(1\le i\le P)$ mô tả truy vấn thứ $i$ với kí tự '!' mô tả truy vấn loại 1 và kí tự '?' mô tả truy vấn loại 2.

### Kết quả
Đối với mỗi truy vấn loại 2, in ra một dòng riêng biệt gồm một số nguyên là câu trả lời cho truy vấn tương ứng theo thứ tự đầu vào.

### Ví dụ
**query.inp**

5 4 4
1 0 1 0 1
?!!?

**query.out**

2
3

**Giải thích ví dụ**
Truy vấn thứ nhất: **1 0 1 0** 1
Sau truy vấn thứ hai dãy trở thành: 1 1 0 1 0
Sau truy vấn thứ ba dãy trở thành: 0 1 1 0 1
Truy vấn thứ tư: 0 **1 1 0 1**

### Ràng buộc
Mình là cao thủ mà, đã chơi là phải full điểm 😊
:::

:::spoiler **Cách làm**
- Đầu tiên, nhân đôi dãy $a$ lên, tức $a=[a_1, \ldots a_N, a_1, \ldots a_N]$;
- Sau đó, tạo dãy $cnt$ với $cnt_i$ là tổng của $K$ phần tử liên tiếp của dãy $a$ bắt đầu từ $i$ $(cnt_i=a_i+\ldots+a_{i+k-1})$;
- Dễ thấy dãy $cnt$ có $m=2N-K+1$ phần tử;
- Gọi $l = m-N+K, \space r=m$;
- Ban đầu, dãy $a$ tạo thành đoạn $[l, r]$ của dãy $cnt$ ($N-K+1$ phần tử cuối của dãy $cnt$);
- Sau truy vấn loại 1, dãy $a$ bị dịch sang trái một bước, vậy nên dãy $cnt$ cũng bị dịch sang trái một bước, do đó $l=l-1, \space r=r-1$;
- Sau $N$ truy vấn loại 1, dãy $a$ lại trở về như cũ, do đó, $l = m-N+K, \space r=m$;
- Bây giờ, làm thế nào để tìm $max(cnt_l,\ldots cnt_r)$? Code ở dưới dùng Segment Tree.
- Độ phức tạp:
- $\mathcal{O}(1)$ cho mỗi truy vấn loại 1;
- $\mathcal{O}(n * \log n)$ cho mỗi truy vấn loại 2.
:::

:::spoiler **Code - C++**

/**
 *     author: brownfox2k6
 *    created: Tue 16 Jan 2024 15:34:10 Hanoi, Vietnam
**/
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
int a[N], cnt[N], tree[4*N];

void build(int i, int tl, int tr) {
  if (tl == tr) {
    tree[i] = cnt[tl];
    return;
  }
  int tm = (tl + tr) >> 1;
  build(2*i+1, tl, tm);
  build(2*i+2, tm+1, tr);
  tree[i] = max(tree[2*i+1], tree[2*i+2]);
}

int query(int i, int tl, int tr, int ql, int qr) {
  if (tl > qr || ql > tr) {
    return 0;
  }
  if (ql <= tl && tr <= qr) {
    return tree[i];
  }
  int tm = (tl + tr) >> 1;
  int left = query(2*i+1, tl, tm, ql, qr);
  int right = query(2*i+2, tm+1, tr, ql, qr);
  return max(left, right);
}

main() {
  cin.tie(0)->sync_with_stdio(0);
  freopen("query.inp", "r", stdin);
  freopen("query.out", "w", stdout);

  int n, k, p;
  cin >> n >> k >> p;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i+n] = a[i];
  }

  cnt[0] = accumulate(a, a+k, 0);
  for (int i = 1; i <= 2*n - k; ++i) {
    cnt[i] = cnt[i-1] - a[i-1] + a[i+k-1];
  }

  int m = 2*n - k;
  build(0, 0, m);
  int l = m - (n - k);
  int r = m;
  string q;
  cin >> q;
  for (char c : q) {
    if (c == '!') {
      --l;
      --r;
      if (l == -1) {
        l = m - (n - k);
        r = m;
      }
    } else {
      cout << query(0, 0, m, l, r) << '\n';
    }
  }
}

:::

# Xoắn ốc [SPIRALP]
> Bài 3/3, HSG lớp 9 - Vĩnh Phúc - 2023-2024
:::spoiler **Đề bài**
Trên một lưới kích thước $N\times M$ ô vuông đơn vị, người ta đặt vào một quân cờ vào ô trên cùng bên trái. Các ô được điền số từ 1 đến $N\times M$ theo hình xoắn ốc, bắt đầu từ ô trên cùng bên trái và hướng sang phải.

Trên lưới, mỗi ô có màu đen hoặc trắng. Chỉ có thể di chuyển quân cờ vào những ô màu trắng.

Với một số nguyên $K$ cho trước, bạn cần tìm cách di chuyển quân cờ đến ô được đánh số $N\times M$ bằng cách thực hiện một số bước di chuyển như sau: "giả sử quân cờ đang ở ô ghi số $x$ thì bạn có thể di chuyển nó vào một trong các ô ghi số $x+1, x+2, \ldots, x+K$ với điều kiện ô đó phải có màu trắng".

Hãy lập trình xác định hai thông tin sau:
- Cần thực hiện ít nhất bao nhiêu bước để di chuyển quân cờ đến ô được đánh số $N\times M$?
- Gọi $F(i)$ là số cách di chuyển hợp lệ khi quân cờ đang ở ô màu trắng được đánh số $i$, hãy tính giá trị $max(F(1), F(2),\ldots F(N\times M))$.

### Dữ liệu
- Dòng 1: Chứa ba số nguyên $N, M, K$ $(N\le 200, M\le 30000, K \le 6000000)$;
- Tiếp theo là $N$ dòng, mỗi dòng chứa $M$ số nguyên 0 hoặc 1 mô tả lưới. Với số 0 đại diện cho ô màu trắng, số 1 đại diện cho ô màu đen.

### Kết quả
Ghi trên một dòng gồm hai số nguyên $P,Q$ là hai thông tin tìm được. $P$ là số bước di chuyển tối thiểu để quân cờ đến ô được đánh số $N \times M$, $Q$ là giá trị $max(F(1), F(2),\ldots F(N\times M))$. Nếu không có cách đưa quân cờ đến ô được đánh số $N\times M$ thì $P=-1$.

### Ví dụ
#### Test #1
##### spiralp.inp

4 5 3
0 1 1 0 1
1 0 1 0 1
0 0 1 0 0
1 1 0 1 1

##### spiralp.out

7 2

##### Giải thích test #1

Một trong các cách di chuyển chỉ với 7 bước là $1\to4\to7\to10\to13\to15\to18\to20$. Không có cách nào di chuyển với số bước ít hơn 7.

Hai vị trí có nhiều cách di chuyển hợp lệ nhất là $15$ và $17$.
- Vị trí được đánh số $15$ có thể di chuyển đến $17$ hoặc $18$
- Vị trí được đánh số $17$ có thể di chuyển đến $18$ hoặc $20$

#### Test #2
##### spiralp.inp

1 5 1
0 1 0 0 1

##### spiralp.out

-1 1

##### Giải thích test #1
Không có cách nào di chuyển đến ô được đánh số $5$.
$Q=max(F(1),F(3),F(4))=max(0,1,1)=1$

### Ràng buộc
Dân chuyên chỉ chơi test case to nhất thôi 😁
:::

:::spoiler **Code - C++**

/**
 *     author: brownfox2k6
 *    created: Tue 16 Jan 2024 16:57:27 Hanoi, Vietnam
**/
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
int A[200][30000];
bool vis[200][30000];
const int dr[4] = {0, 1, 0, -1};
const int dc[4] = {1, 0, -1, 0};
vector<int> v;

int next_cell(int i) {
  int ans = -1;
  int l = i + 1;
  int r = size(v) - 1;
  while (l <= r) {
    int m = (l + r) >> 1;
    if (v[m] <= v[i] + k) {
      ans = m;
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return ans;
}

int shortest_path() {
  if (v[0] != 1 || v.back() != n*m) {
    return -1;
  }
  int i = 0;
  int ans = 0;
  while (true) {
    int ni = next_cell(i);
    if (ni == -1) {
      break;
    }
    i = ni;
    ++ans;
  }
  if (i != size(v) - 1) {
    return -1;
  }
  return ans;
}

int findf() {
  int ans = 0;
  for (int i = 0; i < size(v); ++i) {
    int ni = next_cell(i);
    ans = max(ans, ni - i);
  }
  return ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  freopen("spiralp.inp", "r", stdin);
  freopen("spiralp.out", "w", stdout);

  cin >> n >> m >> k;

  int x = 0;
  int y = 0;
  int d = 0;
  for (int i = 1; i <= m*n; ++i) {
    A[x][y] = i;
    vis[x][y] = 1;
    int nx = x + dr[d];
    int ny = y + dc[d];
    if (0 <= nx && nx < n && 0 <= ny && ny < m && !vis[nx][ny]) {
      x = nx;
      y = ny;
    } else {
      d = (d + 1) % 4;
      x += dr[d];
      y += dc[d];
    }
  }

  for (int x = 0; x < n; ++x) {
    for (int y = 0; y < m; ++y) {
      int u;
      cin >> u;
      if (u == 0) {
        v.emplace_back(A[x][y]);
      }
    }
  }
  sort(v.begin(), v.end());

  cout << shortest_path() << ' ' << findf();
}

:::
# Giao dịch [GIAODICH]
> Bài 4/4, HSG lớp 12 - Đồng Nai - 2023-2024
:::spoiler **Đề bài**
Khu vườn của bạn Kiến là một ma trận hai chiều $A$ gồm $N$ hàng và $M$ cột. Từ ô $(i, j)$ Kiến có thẻ di chuyển đến ô $(i, j+1)$ hoặc $(i+1, j)$. Kiến không thể di chuyển ra khỏi ma trận.

Để có thể thoải mái dạo quanh khu vườn, Kiến phải trả chi phí mỗi khi đi đến một ô $(i, j)$ bất kỳ. Mỗi ô $(i, j)$ chứa một số nguyên dương $A_{i, j}$. Chi phí của ô $(i, j)$ chính là **số lượng ước lớn hơn 1** của $A_{i, j}$. Chi phí của đường đi được định nghĩa là tổng chi phí của tất cả các ô trên đường đi đó.

Em hãy giúp Kiến xác định đường đi tối thiểu để đi từ ô $(1, 1)$ đến ô $(N, M)$.

### Input
- Dòng dầu tiên chứa số lượng test $T$ $(T \le 10^4)$;
- Dòng đầu tiên của mỗi test chứa hai số nguyên $N$, $M$ là số hàng và số cột tương ứng $(1 \le N, M \le 10^3)$;
- $N$ dòng tiếp theo của mỗi test chứa $M$ số nguyên dương $A_{i, j}$ trên mỗi ô của ma trận $(1 \le A_{i, j} \le 10^5)$.

Lưu ý: $N*M*T\le 10^6$.

### Output
Gồm $T$ dòng kết quả. Với mỗi test, hãy in ra chi phí tối thiểu để đi từ ô $(1, 1)$ đến ô $(N, M)$.

### Ví dụ
#### Input

1
5 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

#### Output

5

#### Giải thích ví dụ
Đường đi tối ưu sẽ là $(1,1)$, $(2,1)$, $(3,1)$, $(4,1)$, $(5,1)$, $(5,2)$, $(5,3)$, $(5,4)$, $(5,5)$ với tổng chi phí là $0+0+0+0+0+1+1+2+1=5$.
:::

:::spoiler **Code - C++**

/**
 *     author: brownfox2k6
 *    created: Fri 19 Jan 2024 22:02:38 Hanoi, Vietnam
**/
#include <bits/stdc++.h>
using namespace std;

const int maxAij = 1e5 + 1;
const int maxNM = 1e3 + 1;
const int INF = 1e9 + 1;
int T, N, M;
int pf[maxAij];  // prime factor
int A[maxNM][maxNM];
int memo[maxNM][maxNM];  // for memoization DP

int cd(int x) {  // count divisors
  map<int, int> mp;
  while (x != 1) {
    ++mp[pf[x]];
    x /= pf[x];
  }
  int ans = 1;
  for (auto [d, cnt] : mp) {
    ans *= cnt + 1;
  }
  return ans - 1;
}

int f(int i, int j) {
  if (i == -1 || j == -1 || i == N || j == M) {
    return INF;
  } if (i == N-1 && j == M-1) {
    return A[i][j];
  } if (memo[i][j] != -1) {
    return memo[i][j];
  }
  int right = A[i][j] + f(i, j+1);
  int down = A[i][j] + f(i+1, j);
  return min(right, down);
}

int main() {
  iota(pf, pf + maxAij, 0);
  for (int i = 2; i*i < maxAij; ++i) {
    if (pf[i] == i) {  // i is prime
      for (int j = i*i; j < maxAij; j += i) {  // all multiples of i
        pf[j] = i;
      }
    }
  }
  for (cin >> T; T--; ) {
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < M; ++j) {
        cin >> A[i][j];
        A[i][j] = cd(A[i][j]);
        memo[i][j] = -1;
      }
    }
    cout << f(0, 0) << '\n';
  }
}

:::

:::spoiler **Code - Python**

# /**
#  *     author: brownfox2k6
#  *    created: 19/01/2024 22:26:49 Hanoi, Vietnam
# **/

from collections import defaultdict
import sys
input = sys.stdin.readline
print = sys.stdout.write

def cd(x):  # count divisors
  x = int(x)
  d = defaultdict(int)
  while x != 1:
    d[pf[x]] += 1
    x //= pf[x]
  ans = 1
  for cnt in d.values():
    ans *= cnt + 1
  return ans - 1

def f(i, j):
  if i == -1 or j == -1 or i == N or j == M:
    return float('inf')
  if i == N-1 and j == M-1:
    return A[i][j]
  if memo[i][j] != -1:
    return memo[i][j]
  right = A[i][j] + f(i, j+1)
  down = A[i][j] + f(i+1, j)
  return min(right, down)

maxAij = 100001
pf = [*range(maxAij)]  # prime factor
for i in range(2, int(maxAij**0.5)+1):
  if pf[i] == i:
    for j in range(i*i, maxAij, i):
      pf[j] = i

ans = []
for _ in range(int(input())):
  N, M = map(int, input().split())
  A = [[*map(cd, input().split())] for _ in range(N)]
  memo = [[-1] * N for _ in range(M)]
  ans.append(f(0, 0))

print('\n'.join(map(str, ans)))

:::
# Đếm đoạn tăng nghiêm ngặt
> Nguồn: https://robocontest.uz/olympiads/1088/tasks/C
:::spoiler **Đề bài**
Cho mảng $A$ gồm $N$ số nguyên dương. Đoạn $[L, R]$ được gọi là một **đoạn tăng nghiêm ngặt** nếu $A_L < A_{L+1} < \ldots < A_R$.

Có $Q$ truy vấn, mỗi truy vấn có dạng $i\space x$ - gán giá trị $x$ cho $A_i$.

Hãy tìm số lượng đoạn tăng nghiêm ngặt **sau** mỗi truy vấn.

### Input
- Dòng đầu chứa số nguyên dương $N \space (1 \le N \le 2*10^5)$;
- Dòng thức hai chứa $N$ số nguyên dương $A_1, A_2, \ldots A_N \space (1 \le A_i \le 10^9)$;
- Dòng thứ ba chứa số nguyên dương $Q \space (1\le Q\le 2*10^5)$;
- $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $x$, $y$ $(1\le x \le N, \space 1 \le y \le 10^9)$.

### Output
In ra $Q$ dòng, mỗi dòng là số đoạn tăng nghiêm ngặt tìm được sau mỗi truy vấn.

### Ví dụ

**Giải thích:** Với test #1:
- Sau truy vấn thứ nhất, $A = [100, 10, 1]$, ta tìm được ba đoạn tăng nghiêm ngặt là $[1,1],[2,2],[3,3]$;
- Sau truy vấn thứ hai, $A = [100, 1000, 1]$, ta tìm được bốn đoạn tăng nghiêm ngặt là $[1,1],[2,2],[3,3],[1,2]$.
:::