---
# System prepended metadata

title: T26寒訓練習賽

---


# T26寒訓練習賽題解
## [codeforces](https://codeforces.com/contests/499783)
## 比賽結束後仍然可以submit code
## 賽前預測AC人數

![賽前預測](https://hackmd.io/_uploads/HkmzAJ-5T.png =350x)

## 實際AC人數

![實際AC人數](https://hackmd.io/_uploads/B1slgrfqT.png =350x)


由 moon 出 A, D, H
其他由 tw20000807  出題
## A. 不要懷疑 首殺 : blameazu.
:::danger
**To AC is human; to AK, divine. - Moon**
:::
輸出"Hello worId"
但是他的world拼成worId了
![image](https://hackmd.io/_uploads/HJnL1rk9T.png)

:::spoiler 範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
int main()
{
	cout << "Hello worId" << "\n";
}
```
:::


---

## C. 假日時就是要刷題阿不然要幹嘛 首殺 : blameazu.

因為假日固定只有兩天，所以原本的問題可以理解成以下敘述

::: success
給你 $n$ 個數，有兩個序列，把這 $n$ 個數**依序**放進其中一個序列裡
問最小的不爽值是多少
以及怎麼放
:::
我們可以貪心一下
:::success
在放的時候我們希望每個序列最後放入的數字越大越好，因為這樣越有可能不會增加不爽值
:::

我們可以設想一些情況

假設第一個序列最後放入的數字為ff
假設第二個序列最後放入的數字為ss
假設現在要放入的數字為k

我們要讓ff跟ss越大越好

所以接下來會有6種情況
:::info
k > ss > ff
把k放進第一個序列
ff變成k
不爽值 + 1
:::
:::info
k > ff > ss
把k放進第二個序列
ss變成k
不爽值 + 1
:::

:::info
ss > k > ff
把k放進第二個序列
ss變成k
:::
:::info
ss > ff > k
把k放進第一個序列
ff變成k
:::
:::info
ff > ss > k
把k放進第二個序列
ss變成k
:::
:::info
ff > k > ss
把k放進第一個序列
ff變成k
:::

如果ss = k or ff = k 那就直接放到等號成立的那個序列
::: spoiler 範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> f, s;
int ary[1000000];
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> ary[i];
	
	long long ff = INT_MAX, ss = INT_MAX - 1;
	int k = 0;
	for(int i = 1; i <= n; i++){
		if(ary[i] == ff) f.pb(i);
		else if(ary[i] == ss) s.pb(i);
		else if(ary[i] > ss and ss > ff){
			k++;
			f.pb(i);
			ff = ary[i];
		}
		else if(ary[i] > ff and ff > ss){
			k++;
			s.pb(i);
			ss = ary[i];
		}
		else if(ss > ary[i] and ary[i] > ff){
			s.pb(i);
			ss = ary[i];
		}
		else if(ss > ff and ff > ary[i]){
			f.pb(i);
			ff = ary[i];
		}
		else if(ff > ss and ss > ary[i]){
			s.pb(i);
			ss = ary[i];
		}
		else if(ff > ary[i] and ary[i] > ss){
			f.pb(i);
			ff = ary[i];
		}
	}
	
	cout << k << "\n";
	cout << f.size() << "\n";
	
	for(auto w : f) cout << w << ' ';
	if(f.size() > 0) cout << "\n";
	
	cout << s.size() << "\n";
	for(auto w : s) cout << w << ' ';
}
```
:::

:::spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
using namespace std;
int inf = 1e9 + 10;
int v[200010];
int main(){
	int n, ans = 0;
	vector< int > a = {0}, b = {0};
	v[0] = inf;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> v[i];
	for(int i = 1; i <= n; i++){
		if(v[a.back()] > v[b.back()])swap(a, b);
		if(v[a.back()] >= v[i])a.push_back(i);
		else if(v[b.back()] >= v[i])b.push_back(i);
		else{
			ans++;
			a.push_back(i);
		}
	}
	cout << ans << "\n" << a.size() - 1 << "\n";
	for(int i = 1; i < a.size(); i++)
		cout << a[i] << " \n"[i == a.size() - 1];
	cout << b.size() - 1 << "\n";
	for(int i = 1; i < b.size(); i++) 
		cout << b[i] << " \n"[i == b.size() - 1];
}
```
stl 的 swap 是 O(1)
c style array 是 O(n)
:::



---

## D. 寫報告  首殺 : 

我不會qwq

詳解by moon
這是個貪心的題目
應該很好看出來
第一想法可能會是直接sort結束時間
然後逐步做過去就好
但仔細想想就會發現不太對
因為只限制了要在什麼時間之前做完
 而不是開始和結束時間
只要在結束時間之前是可以自由移動的
所以按照限制時間來排序之後
越後面的報告 如果能做的話
那一定能在更早之前做
所以我們會利用priority_queue來維護 之前的報告中花費時間最久的那個

可以試試看這個例子，答案應該是3
:::success
4
1 4
3 4
2 5
5 8
:::

:::spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define pii pair< ll, ll >
#define X first
#define Y second
using namespace std;
int main(){
	int n;
	cin >> n;
	vector< pii > v(n);
	//Y is need time, X is deadline
	for(int i = 0; i < n; ++i){
	    cin >> v[i].Y >> v[i].X;
	}
	sort(v.begin(), v.end());
	ll ans = 0, cur = 0;
	priority_queue< ll > pq;
	for(int i = 0; i < n; ++i){
	    if(cur + v[i].Y  <= v[i].X){
	        cur += v[i].Y;
	        ans++;
	        pq.push(v[i].Y);
	    }
	    else if(!pq.empty() && v[i].Y < pq.top()){
	        cur -= pq.top(); pq.pop();
	        cur += v[i].Y;
	        pq.push(v[i].Y);
	    }
	}
	cout << ans << "\n";
}
```
:::

:::spoiler 範例code by moon
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main()
{
	  int n;
	  cin >> n;
	  vector<pair<int, int>> v(n);
	  for(int i = 0; i < n; ++i){
	    cin >> v[i].second >> v[i].first;
	  }
	  sort(v.begin(), v.end());
	  long long ans = 0, cur = 0;
	  priority_queue<int> pq;
	  for(int i = 0; i < n; ++i){
	    if(cur + v[i].second <= v[i].first){
	      cur += v[i].second;
	      ans++;
	      pq.push(v[i].second);
	    }
	    else if(pq.size() and v[i].second < pq.top()){
	      cur = cur - pq.top() + v[i].second;
	      pq.pop();
	      pq.push(v[i].second);
	    }
	  }
	  cout << ans << '\n';
	
}
```
:::


---



## E. 中位數的中位數 首殺 : RedPlus
~~閱讀完題目後直接實作即可~~
因為這題的$n$很小，所以可以直接實作
題目給的數字到2147483674而int只到2147483647，所以要開long long
::: spoiler 範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
#define pb push_back
vector<long long> ans;
int main()
{
	KCC
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		vector<long long> v;
		for(int j = 0; j < n; j++){
			long long a;
			cin >> a;
			v.pb(a);
		}
		sort(v.begin(), v.end());
		ans.pb(v[n / 2]);
	}
	sort(ans.begin(), ans.end());
	cout << ans[n / 2] << "\n";
	return 0;
}
```

:::

:::spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll arr[1010][1010];
ll ans[1010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> arr[i][j];
		}
		sort(arr[i], arr[i] + n);
		ans[i] = arr[i][n / 2];
	}
	sort(ans, ans + n);
	cout << ans[n / 2] << "\n";
}
```
:::

---



## F. 迷宮 首殺 : charhao
這裡有一個難一點的類似題可以去試試看[連結在這](https://cses.fi/problemset/task/1193)

這題是一個BFS的裸題，題目就是問$A$走到傳送門及$B$走到傳送門分別最少要走幾步，然後再乘上各自走一步需要的時間

簡單來說就是做兩次BFS


::: spoiler 範例code byKCC

```cpp=
// 變數解釋:
// n, a, b 與題目敘述相同

// xa, xb, xo
// A,B, 傳送門的x座標

// yo, ya, yb
// A,B, 傳送門的y座標

// queue<pair< pair< int , int  >, int>> q
// queue<pair< pair< X座標, Y座標>, 走到(X,Y)需要的步數>> q
// 所以
// X座標會是 q.front().first.first
// Y座標會是 q.front().first.second
// 走到(X,Y)需要的步數會是 q.front().second
// ~~這寫法好像有點毒瘤~~
// 也可以用tuple(第二天的課有講到)
// aa為A走到傳送門需要的最短步數(也就是BFS後的結果)
// bb為B走到傳送門需要的最短步數(也就是BFS後的結果)
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
long long n, a, b, xa, xb, xo, ya, yb, yo;
char c[1005][1005];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
queue<pair< pair<int, int>, int >> q;
bool used[1005][1005];

long long bfs(int x, int y)
{
	q.push({{x, y}, 0});
	while(q.size()){
		
		int nowx = q.front().first.first;
		int nowy = q.front().first.second;
		int f = q.front().second;
		q.pop();
		
		if(nowx == xo and nowy == yo) return f; 
		
		for(int i = 0; i < 4; i++){
			
			int next_x = nowx + dx[i];
			int next_y = nowy + dy[i];
			
			if(!used[next_x][next_y] and 
				next_x >= 0 and next_x < n 
				and next_y >= 0 and next_y < n
				and c[next_x][next_y] != '#')
			{
					
				q.push({{next_x, next_y}, f + 1});
				used[next_x][next_y] = true;
			}
					
		}
		
	}
	return -1;
}
int main()
{
	KCC
	cin >> n >> a >> b;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> c[i][j];
			if(c[i][j] == 'A'){
				xa = i;
				ya = j;
			}
			if(c[i][j] == 'B'){
				xb = i;
				yb = j;
			}
			if(c[i][j] == 'O'){
				xo = i;
				yo = j;
			}
		}
	}
	long long aa = bfs(xa, ya);
	
	while(!q.empty()) q.pop();
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++) used[i][j] = false;
	}
	long long bb = bfs(xb, yb);
	if(aa == -1) cout << aa << ' ';
	else cout << aa * a << ' ';
	
	if(bb == -1) cout << bb << "\n";
	else cout << bb * b << "\n";

}
```
:::

:::spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
char mp[1010][1010];
long long disa[1010][1010];
long long disb[1010][1010];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int main(){
	int n, at, bt;
	cin >> n;
	cin >> at >> bt;
	pii A, B, O;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			disa[i][j] = disb[i][j] = -1;
			cin >> mp[i][j];
			if(mp[i][j] == 'O'){
				O = {i, j};
			}
			if(mp[i][j] == 'A'){
				A = {i, j};
			}
			if(mp[i][j] == 'B'){
				B = {i, j};
			}
			
		}
	}
	for(int i = 0; i <= n + 1; i++){
		mp[0][i] = mp[i][0] = mp[n + 1][i] = mp[i][n + 1] = '#';
	}
	
	vector< pii > qu;
	int idx = 0;
	qu.push_back(A);
	disa[A.X][A.Y] = 0;
	while(qu.size() > idx){
		pii cur = qu[idx++];
		for(int k = 0; k < 4; k++){
			pii nw = {cur.X + dx[k], cur.Y + dy[k]};
			if(mp[nw.X][nw.Y] != '#' && disa[nw.X][nw.Y] == -1){
				disa[nw.X][nw.Y] = disa[cur.X][cur.Y] + at;
				qu.push_back(nw);
			}
		}
	}
	qu.clear();
	idx = 0;
	qu.push_back(B);
	disb[B.X][B.Y] = 0;
	while(qu.size() > idx){
		pii cur = qu[idx++];
		for(int k = 0; k < 4; k++){
			pii nw = {cur.X + dx[k], cur.Y + dy[k]};
			if(mp[nw.X][nw.Y] != '#' && disb[nw.X][nw.Y] == -1){
				disb[nw.X][nw.Y] = disb[cur.X][cur.Y] + bt;
				qu.push_back(nw);
			}
		}
	}
	cout << disa[O.X][O.Y] << " " << disb[O.X][O.Y] << "\n";
}
```
:::


---


## G. 兩個背包問題 首殺 : 
這顯然是DP的經典問題對吧?
沒錯!!
當只有一個背包的時候dp的關係式為
\begin{align}
dp[i][j] = max 
\begin{cases}
 &dp[i - 1][j - w[i]] + val[i]\\
 &dp[i - 1][j]\\
\end{cases}
\end{align}



那兩個背包呢?

有幾個想法
* 把它視為一個大背包
* 增維

視為一個大背包顯然是不行的
因為物品不能被拆開成小塊

::: danger
例:一個背包能裝重量1，另一個能裝重量2，不能裝重量3的物品
:::

那增維的dp式怎麼列?
就像一個背包的時候一樣

$dp[i][j][k] = 選到第i個，第一個背包裝了j重量 + 第二個背包裝了k重量 的價值最大值$

$$
dp[i][j][k] = max 
\begin{cases}
 dp[i - 1] &[j] &[k]\\
 dp[i - 1] &[j - w[i]] &[k] &+ val[i]\\
 dp[i - 1] &[j] &[k - w[i]] &+ val[i]]\\
\end{cases}
$$

::: success
**dp的精隨在於宣告一個名為dp的陣列**
:::

:::spoiler 範例code byKCC

```cpp=
#include<bits/stdc++.h>
using namespace std;
int w[105];
int val[105];
int dp[200][200][200];
int main()
{
	int n, a, b, ans = 0;
	cin >> n >> a >> b;
	for(int i = 0; i < n; i++) cin >> val[i];
	for(int i = 0; i < n; i++) cin >> w[i];
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= a; j++){
			for(int k = 0; k <= b; k++){
				if(i - 1 >= 0){
					if(j - w[i] >= 0) dp[i][j][k] = max(dp[i][j][k], dp[i - 1] [j - w[i]] [k] + val[i]);
					if(k - w[i] >= 0) dp[i][j][k] = max(dp[i][j][k], dp[i - 1] [j] [k - w[i]] + val[i]);
					dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k]);
				}
				else{
					if(j - w[i] >= 0) dp[i][j][k] = max(dp[i] [j - w[i]] [k], val[i]);
					if(k - w[i] >= 0) dp[i][j][k] = max(dp[i] [j] [k - w[i]], val[i]);
				}
				ans = max(ans, dp[i][j][k]);
			}
		}
	}
	cout << ans << "\n";
	
}
```
:::

::: spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
using namespace std;
int w[110], v[110];
int dp[110][120][120];
int main(){
	int n;
	cin >> n;
	int a, b, ans = 0;
	cin >> a >> b;
	for(int i = 1; i <= n; i++)cin >> v[i];
	for(int i = 1; i <= n; i++)cin >> w[i];
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= a; j++){
			for(int k = 0; k <= b; k++){
				dp[i][j][k] = dp[i - 1][j][k];
				if(j - w[i] >= 0)
					dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - w[i]][k] + v[i]);
				if(k - w[i] >= 0)
					dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - w[i]] + v[i]);
				ans = max(ans, dp[i][j][k]);
			}
		}
	}
	cout << ans << "\n";
}
```
:::



---


## H. different prefix product 首殺 : 

這題要用到**模逆元**的概念
以下為$n$的模逆元(公式)
:::info
$inv[i]$ = $(n-n/i)$ $*$ $inv$[ $n$ % $i$ ] % $n$
:::
或者(費馬小定理推廣)
:::info
$i^{p - 2} \mod p$
:::
首先，0 必須要放在最後一位
如果0不放在最後一位，前綴積會重複出現0
例 : 0 1 2 3

其次，1必須放在第一位
如果不是放在第一位的話會出現兩個一樣的前綴積
例 : 2 1 3 0

最後，$n$必須要是質數才行
如果$n$不是質數，那麼從$1$~$n$的某些數乘起來一定會是$n$的倍數 
那麼在做前綴積的時候一定會發生取mod後變成0的情況

例 : $n = 6, 2 \times 3 = 6 \times 1$
例 : $n = 9, 3 \times 6 = 9 \times 2$

但是4是例外，可以構造出1 3 2 0

綜合上述，我們可以構造出類似這樣子的東西
:::success
1, $\frac{2}{1}$, $\frac{3}{2}$, $\frac{4}{3}$, $\frac{5}{4}$, $\frac{6}{5}$.....$\frac{n - 1}{n - 2}$, $\frac{n}{n - 1}$($每一項其實就相當於 (i + 1) \times inv[i]$)
:::

::: spoiler 範例code byKCC(公式)
```cpp=
#include<bits/stdc++.h>
using namespace std;
long long inv[1000000];
int main()
{
	int n;
	cin >> n;
	if(n == 1){
		cout << "YES" << "\n";
		cout << "0" << "\n";
		return 0;
	}
	if(n == 4){
		cout << "YES" << "\n";
		cout << "1 3 2 0" << "\n";
		return 0;
	}
	
	for(int i = 2; i * i <= n; i++){
		if(n % i == 0){
			cout << "NO" << "\n";
			return 0;
		}
	}
	cout << "YES" << "\n";
	inv[1] = 1;
	for(int i = 2; i <= n; i++) inv[i] = ((n - n / i) * inv[n % i]) % n;
	cout << 1 << ' ';
	for(int i = 1; i < n; i++) cout << ((i + 1) * inv[i]) % n << ' ';
	return 0;
}

```
:::

:::spoiler 範例code by tw20000807(費馬小定理)
```cpp=
#include<iostream>
#define ll long long
using namespace std;
ll ans[200010];
ll fpow(ll a, ll b, ll mod){
	ll re = 1;
	while(b){
		if(b & 1)re = re * a % mod;
		b >>= 1;
		a = a * a % mod;
	}return re;
}
ll rev(ll a, ll mod){
	return fpow(a, mod - 2, mod);
}
int main(){
	int n;
	cin >> n;
	ans[1] = 1 % n;
	if(n == 4){
		cout << "YES\n";
		cout << "1 3 2 0\n";
		return 0;
	}
	for(ll i = 2; i * i <= n; i ++){
		if(n % i == 0){
			cout << "NO\n";
			return 0;
		}
	}
	for(int i = 2; i <= n; i++){
		ans[i] = i * rev(i - 1, n) % n;
	}
	cout << "YES\n";
	for(int i = 1; i <= n; i++)cout << ans[i] << " \n"[i == n];
}
```
:::

[別人的題解](https://blog.csdn.net/tc_to_top/article/details/43614795)



---
## I. 動態工作規劃 首殺 : blameazu.
區間求和，單點修改
可用線段樹 or BIT(樹狀數組)來操作
可是線段樹的常數比較大且實作上較複雜，所以使用BIT就可以了
:::danger
使用線段樹只能拿45分qwq(後來把題目修改成線段樹也可以過了)
:::
因為需要蓋很多棵BIT樹，所以直接多一維變成二維即可

[不知道BIT是什麼的點這裡](https://hackmd.io/@tw20000807/all/https%3A%2F%2Fhackmd.io%2F%40tw20000807%2Fdatastructure)

[或者這裡](https://www.youtube.com/watch?v=ErmFGGw7f-s)


:::spoiler 後計
後來被用前綴和過了?!?!?!
顯然測資不夠強
前綴和複雜度$O(q \times k)$
:::

::: spoiler BIT範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
long long n, k, q, ans = 0;
long long bit[25][10005];
long long ary[25][10005];
long long sum(int w, int a, int b)
{
	long long k = 0, q = 0;
	a--;
	for(; b; b -= b & -b) k += bit[w][b];
	for(; a; a -= a & -a) q += bit[w][a];
	return k - q;
}
void fix(int w, int t, int x)
{
	for(; t <= k; t += t & -t) bit[w][t] += x;
	return ;
}
int main()
{
	KCC
	cin >> n >> k >> q;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= k; j++)
			cin >> ary[i][j];
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= k; j++) fix(i, j, ary[i][j]);
	}
	
	while(q--){
		int x;
		cin >> x;
		if(x == 1){
			int a, b;
			cin >> a >> b;
			long long k = 0;
			for(int i = 1; i <= n; i++) k = max(k, sum(i, a, b));
			ans += k;
		}
		else{
			int w, t, x;
			cin >> w >> t >> x;
			fix(w, t, x - ary[w][t]);
			ary[w][t] = x;
		}
	}
	cout << ans << "\n";
}
```
:::

:::spoiler 線段樹範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
long long tree[25][40010];
long long a[25][10010];
long long n, k, q;
void build(int w, int l, int r, long long id)
{
	if(l == r){
		tree[w][id] = a[w][l];
		return ;
	}
	long long mid = (l + r) >> 1;
	build(w, l, mid, id * 2 + 1);
	build(w, mid + 1, r, id * 2 + 2);
	
	tree[w][id] = tree[w][id * 2 + 1] + tree[w][id * 2 + 2];
	return ;
}
void fix(int w, int t, int x, int l, int r, long long id)
{
	if(l == r and l == t){
		tree[w][id] = x;
		return;
	}
	long long mid = (l + r) >> 1;
	
	if(t <= mid) fix(w, t, x, l, mid, id * 2 + 1);
	else fix(w, t, x, mid + 1, r, id * 2 + 2);
	
	tree[w][id] = tree[w][id * 2 + 1] + tree[w][id * 2 + 2];
	
	return ;
}
long long sum(int w, int a, int b, int l, int r, long long id)
{
	if(l >= a and b >= r) return tree[w][id];
	long long ans = 0;
	long long mid = (l + r) >> 1;
	if(a <= mid) ans += sum(w, a, b, l, mid, id * 2 + 1);
	if(b > mid) ans += sum(w, a, b, mid + 1, r, id * 2 + 2);
	
	return ans;
	
}
int main()
{
	KCC
	cin >> n >> k >> q;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 0; i < n; i++) build(i, 0, k - 1, 0);
	long long ans = 0;
	while(q--){
		int f;
		cin >> f;
		if(f == 1){
			int a, b;
			cin >> a >> b;
			a--;b --;
			long long wage = 0;
			
			for(int i = 0; i < n; i++) wage = max(wage, sum(i, a, b, 0, k - 1, 0));
			ans += wage;
		}
		else if(f == 2){
			int w, t, y;
			cin >> w >> t >> y;
			w--;t--;
			fix(w, t, y, 0, k - 1, 0);
		}
	}
	cout << ans << "\n";
	
}
```
:::

:::spoiler BIT範例code by tw20000807
```cpp=
#include<iostream>
using namespace std;
int n, k, q;
int v[25][10010];
long long tree[200010];
int to(int i, int j){
	return (i - 1) * k + j;
}
void update(int id, int val){
	for(; id <= n * k; id += id &-id)tree[id] += val;
}
long long query(int id){
	long long re = 0;
	for(; id; id -= id&-id)re += tree[id];
	return re;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k >> q;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= k; j++){
			cin >> v[i][j];
			update(to(i, j), v[i][j]);
		}
	}
	long long ans = 0;
	
	while(q--){
		int t; cin >> t;
		if(t == 1){
			int a, b;
			long long mx = 0;
			cin >> a >> b;
			for(int i = 1; i <= n; i++)
				mx = max(mx, query(to(i, b)) - query(to(i, a) - 1));
			ans += mx;
		}
		if(t == 2){
			int w, t, x;
			cin >> w >> t >> x;
			update(to(w, t), x - v[w][t]);
			v[w][t] = x;
		}
	}
	cout << ans << "\n";
}
```
:::


---

## J. 糖果傳奇 首殺 : blameazu.
這題主要考stl的操作及使用
可以利用 $map<int, set<int>> xy, yx$來操作
xy代表在x這個鉛直線上有哪些條紋糖果及他們的y座標
yx代表在y這個水平線上有哪些條紋糖果及他們的x座標

用一個queue來記錄哪些條紋糖果爆炸了
然後再分別檢查x座標及y座標的哪些條紋糖果會被炸到

一直重複做，直到所有爆炸了的條紋糖果


:::warning
後來發現其實用pair就可以了
:::
:::spoiler 範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
map<int, set<int>> xy, yx;
int main()
{
	int k, x0, y0, ans = 1;
	cin >> k;
	cin >> x0 >> y0;
	for(int i = 0; i < k - 1; i++){
		int a, b;
		cin >> a >> b;
		xy[a].insert(b);
		yx[b].insert(a);
	}
	queue<pair<int, int>> q;
	q.push({x0, y0});
	while(!q.empty()){
		pair<int, int> f = q.front();
		q.pop();
		vector<pair<int, int>> v;
		for(int i : xy[f.first]) v.push_back({f.first, i});
		for(int i : yx[f.second]) v.push_back({i, f.second});
		for(pair<int, int> i : v){
			ans++;
			q.push(i);
			xy[i.first].erase(i.second);
			yx[i.second].erase(i.first);
		}
	}
	cout << k - ans << "\n";
}
```
:::

::: spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
#define pii pair< int, int >
#define X first
#define Y second
using namespace std;
map< int, set<int> > xy, yx;
int main(){
	int k, a, b;
	cin >> k;
	int x0, y0;
	cin >> x0 >> y0;
	for(int i = 1; i < k; i++){
		cin >> a >> b;
		xy[a].insert(b);
		yx[b].insert(a);
	}
	vector< pii > stk;
	int ans = 1;
	stk.push_back({x0, y0});
	while(!stk.empty()){
		pii cur = stk.back(); stk.pop_back();
		vector< pii > clr;
		for(int i : xy[cur.X]){
			clr.push_back({cur.X, i});
		}
		for(int i : yx[cur.Y]){
			clr.push_back({i, cur.Y});
		}
		for(pii i : clr){
			ans++;
			stk.push_back(i);
			xy[i.X].erase(i.Y);
			yx[i.Y].erase(i.X);
		}
		clr.clear();
	}
	cout << k - ans << "\n";
}
```
:::

::: spoiler 範例code by yuzhe097
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define pf p[i].first
#define ps p[i].second
using namespace std;
ll n , x , y , ans;
pair<ll , ll> p[2000000];
bool pq[2000000];
int f( ll x , ll y ){
	for( ll i = 0 ; i < n-1 ; i++ ){
		if( pf == x && !pq[i] ){
			pq[i] = 1;
			ans --;
			f( pf , ps );
		}
		if( ps == y && !pq[i]){
			pq[i] = 1;
			ans --;
			f( pf , ps );
		}
	}
	return 0;
};
int main(){
	cin >> n >> x >> y;
	ans = n-1;
	for( ll i = 0 ; i < n-1 ; i++ ){
		cin >> pf >> ps;
	}
	f(x,y);
	cout << ans << '\n';
}
```
:::


---



<!-- ## Multiplication Table
:::success
中位數的意思是前面有一半的數字小於或等於中位數，也就是有$n \times n / 2$個數字小於或等於中位數
:::
我們可以利用二分搜找出答案
每次利用
```cpp
for(int i = 1; i <= n; i++) cnt += min(n, mid / i);
```
找出小於mid的數字數量
其中，$mid / i$ 代表 $i$ 的倍數有幾個比 $mid$ 小
因為最多只會有 $n$ 個數字(題目限制說的)，所以跟 $n$ 取 $min$

這裡$r$不能 $= mid - 1$，因為$mid - 1$不一定能夠滿足前面有$n \times n / 2$個數字小於或等於$mid - 1$
而$l$則一定要是$mid + 1$，因為$mid$已經確定不符合條件了
如果剛好有 $n \times n / 2$個數字 $\leq mid$ 那就輸出$mid + 1$
因為



---

 -->


## 我超棒

## 注意

由於測資都是隨機生成且沒有特別去卡假解，因此可能會被一些假解唬爛過去，也可能官解本身就是錯的，有任何問題可以到 https://hackmd.io/@tw20000807/T26_winter/edit 回報

我不會出題

好多題被假解唬爛過去






