---
tags: DDJRC
---

# DDJ Regular Contest Round#6 Tutorial
[TOC]
## a624 A. Benson 的數學課
可以從前幾項來推測答案是 $\frac{x\cdot(x-1)}{2}$，接著嚴謹證明如下:
`step 1.`
若 $n=1$，得分為 $0=\frac{1\cdot(1-1)}{2}=0$，命題成立。
`step 2.`
設 $n=k$ 時，根據歸納假設將 $k$ 拆成任意 $a,b$ 滿足 $a+b=k$ 且 $a,b\in N$，由於 $a,b<k$，所以可從歸納法得到兩項最後分別會是 $\frac{a^2-a}{2},\frac{b^2-b}{2}$ 分，以及現在得到的 $a\times b$ 分，加起來 $\frac{a^2-a}{2}+\frac{b^2-b}{2}+ab=\frac{a^2+b^2-2ab-a-b}{2}=\frac{k^2-k}{2}$，因此式子成立，得證。

#include <bits/stdc++.h>
using namespace std;
int main() {
	int T; cin >> T;
	while (T--) {
		int x;
		cin >> x, cout << 1LL * x * (x - 1) / 2 << '\n';
	}
}

## a630 B. Benson 的體育課
可以發現答案有以下關係式:
$f(N)=\begin{cases}0&,N\equiv1\pmod{2}\\4f(N-2)-f(N-4)&,N\ge6\\3&,N=2\\11&,N=4\end{cases}$

這有證明
https://math.stackexchange.com/questions/2392795/domino-tiling-on-a-3-by-n-rectangle

由於 $1\le N\le10^{18}$，可用矩陣快速冪優化做到複雜度在 $O(2^3\log N)$ 的時間完成。
由於方便且再優化常數可以先判斷奇偶，只對偶數做矩陣快速冪。

$\left[\begin{matrix}4&-1\\1&0\end{matrix}\right]\left[\begin{matrix}f(N-1)\\f(N-2)\end{matrix}\right]=\left[\begin{matrix}f(N)\\f(N-1)\end{matrix}\right]$

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 998244353;
template <typename T> using vec = vector<T>;
template <typename T> using matrix = vec<vec<T>>;
template <typename T>
matrix<T> operator*(const matrix<T>& a, const matrix<T>& b) {
	int n = a.size(), r = b.size(), m = b.front().size();
	matrix<T> ret(n, vec<T>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < r; k++)
				ret[i][j] = (ret[i][j] + a[i][k] * b[k][j] + mod) % mod;
	return ret;
}
int fpow(ll n) {
	matrix<ll> ret{{11}, {3}}, t{{4, -1}, {1, 0}};
	for (; n; n >>= 1, t = t * t)
		if (n & 1) ret = t * ret;
	return ret[1][0];
}
int main() {
	int T; cin >> T;
	while (T--) {
		ll n; cin >> n;
		if (n & 1) cout << "0\n";
		else cout << fpow(n / 2 - 1) << '\n';
	}
}

## a631 C. Benson 的福利社
其實就是求序列的中位數而已，如果 $N$ 是偶數，則 $[arr[mid],arr[mid+1]]$ 的整數都是答案。

這有證明
https://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations-the-ell-1-norm

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n; cin >> n;
	vector<int> v(n);
	for (auto& i : v) cin >> i;
	cout << v[n / 2] << '\n';
}

## a632 D. Benson 的美術課
帶修改莫隊經典問題，時間複雜度為 $O(N^{\frac{5}{3}})$。
後來發現沒有卡好數字範圍，可以用 bitset 唬爛過去 QQ。

`程式碼代補`

// 唬爛做法
void solve() {
	int n, q; cin >> n >> q;
	int a[n + 1];
	bitset<1000001> b;
	for (int i = 1; i <= n; i++) cin >> a[i];
	while (q--) {
		bool op; cin >> op;
		if (op) {
			int l, r, ans = 0; cin >> l >> r;
			b.reset();
			for (int i = l; i <= r; i++) {
				if (!b[a[i]]) ans++;
				b[a[i]] = 1;
			}
			cout << ans << '\n';
		}
		else {
			int x, v; cin >> x >> v;
			a[x] = v;
		}
	}
}

## a516 E. Benson 的 LCM
線段樹裸題，不過因為數字範圍頗大，需要使用動態開點再帶上懶標記，如果一個區間只有一個數字的話，就標記它，該區間不再往下遞迴建構，以此類推，下次經過時再下放一層。

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define gcd __gcd // C++17 up
using ll = long long;

ll N; // max of row size
struct node {
	node *l, *r; ll v, tag;
	void pull() {
		ll g = gcd(l ? l->v : 1LL, r ? r->v : 1LL);
		v = (l ? l->v : 1LL) * (r ? r->v : 1LL) / g;
	}
	void push(ll l, ll r) {
		ll m = (l + r) >> 1;
		if (tag <= m) this->l = new node(v, tag);
		else this->r = new node(v, tag);
		tag = -2;
	}
	node(ll _v = 1, ll _tag = -1): v(_v), tag(_tag) {
		l = r = nullptr;
	}
} *root = nullptr;
void upd(node*& o, ll x, ll v, ll l = 1LL, ll r = N) {
	if (!o) o = new node;
	if (o->tag == x || l == r) {
		o->v = v;
		return;
	}
	if (o->tag == -1) {
		o->tag = x, o->v = v;
		return;
	}
	if (o->tag > 0) o->push(l, r);
	ll m = (l + r) >> 1;
	if (x <= m) upd(o->l, x, v, l, m);
	else upd(o->r, x, v, m + 1, r);
	o->pull();
}
ll qry(node* o, ll ql, ll qr, ll l = 1LL, ll r = N) {
	if (!o) return 1;
	if (ql <= l && r <= qr) return o->v;
	if (o->tag > 0) return ql <= o->tag && o->tag <= qr ? o->v : 1;
	ll m = (l + r) >> 1, lret = 0, rret = 0;
	if (ql <= m) lret = qry(o->l, ql, qr, l, m);
	if (qr > m) rret = qry(o->r, ql, qr, m + 1, r);
	ll g = gcd(lret ? lret : 1LL, rret ? rret : 1LL);
	return (lret ? : 1LL) * (rret ? : 1LL) / g;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int Q; cin >> N >> Q;
	while (Q--) {
		int op; cin >> op;
		if (op == 1) {
			ll x, v; cin >> x >> v;
			upd(root, x, v);
		}
		else {
			ll ql, qr; cin >> ql >> qr;
			cout << qry(root, ql, qr) << '\n';
		}
	}
}