CSES Problem Set

---

Sorting and Searching

Concert Tickets

這題基本上和APCS2021/1月的P3有異曲同工之妙

• 提示
  $operation⟹O(\log n)⟹AC$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

struct node {
	int v, cnt;
	node(int _v, int _cnt=1) : v(_v), cnt(_cnt) {}

	friend bool operator<(const node& a, const node& b) {
		return a.v < b.v;
	}
};

set<node> st;

int main() {
	IO;

	int n, m;
	cin >> n >> m;
	st.insert(node(-1, max(n, m)+1));
	for(int i = 0, tmp = 0; i < n; ++i) {
		cin >> tmp;
		node d(tmp);
		auto it = st.find(d);
		node sv = *it;
		if(it == st.end())
			st.insert(d);
		else {
			st.erase(it);
			++sv.cnt;
			st.insert(sv);
		}
	}
	for(int i = 0, tmp = 0; i < m; ++i) {
		cin >> tmp;
		node d(tmp);
		auto it = st.lower_bound(d);
		if(it == st.end())
			--it;
		while(it->v > tmp)
			--it;
		cout << it->v << endl;
		node sv = *it;
		st.erase(it);
		--sv.cnt;
		if(sv.cnt > 0)
			st.insert(sv);
	}
}

Restaurant Customers

直覺通常是 (?)

• 離散化 + Segment
• 動態開點

一樣

$O(n\log n)$ 但是麻煩
可以試試用sort實現一樣的目的

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

#define ar array

int n;
vector<ar<int,2>> t;

int main() {
	IO;

	cin >> n;
	t.resize(n<<1);
	bool neg = 0;
	for(auto& ry : t) {
		int x;
		cin >> x;
		ry = ar<int,2>{x, neg};
		neg = !neg;
	}
	sort(t.begin(), t.end());
	int cus = 0, ans = 0;
	for(auto& ry : t) {
		if(!ry[1])
			++cus;
		else
			--cus;
		ans = max(ans, cus);
	}
	cout << ans << endl;
}

Movie Festival

這題就Greedy

Greedy什麼

結束的時間。因為你愈早結束，能看到電影的機會愈多。

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

#define ar array

int n;
vector<ar<int,2>> t;

int main() {
	IO;
	
	cin >> n;
	t.resize(n);
	for(auto& ry : t) {
		int a, b;
		cin >> a >> b;
		ry = ar<int,2>{b, a};
	}
	sort(t.begin(), t.end());
	int ans = 0, pre = 0;
	for(auto& ry : t) {
		if(pre <= ry[1])
			pre = ry[0], ++ans;
	cout << ans << endl;
}

Sum of Two Values

• 提示
  $BinarySearch、DuelPointer$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;
 
int main() {
	IO;
	
	int n, x;
	cin >> n >> x;
	vector<pair<int,int>> vt(n);
	for(int i = 0; i < n; ++i) {
		int tmp;
		cin >> tmp;
		vt[i] = {tmp, i+1};
	}
	sort(vt.begin(), vt.end());
	auto l = vt.begin(), r = vt.end()-1;
	while(l->first + r->first != x && l != r) {
		if(l->first + r->first < x)
			++l;
		else if(l->first + r->first > x)
			--r;
		else
			break;
	}
	if(l->first + r->first == x && l != r)
		cout << l->second << ' ' << r->second << endl;
	else
		cout << "IMPOSSIBLE" << endl;
}

Maximum Subarray Sum

• 提示
  $DynamicProgramming$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;

int main() {
	IO;
	
	int n;
	cin >> n;
	vector<ll> dp(n);
	for(auto& i : dp)
		cin >> i;
	for(int i = 1; i < n; ++i)
		dp[i] = max(dp[i], dp[i-1]+dp[i]);
	for(int i = 1; i < n; ++i)
		dp[i] = max(dp[i], dp[i-1]);
	cout << dp[n-1] << endl;
}

Stick Lengths

• 提示
  $MathTheory$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;

int main() {
	IO;
	
	int n;
	cin >> n;
	vector<int> p(n);
	for(auto& i : p)
		cin >> i;
	sort(p.begin(), p.end());
	int idx;
	if(n&1)
		idx = (n/2 + (n+1)/2)/2;
	else
		idx = n/2;
	ll ans = 0;
	for(auto& i : p)
		ans += abs(i-p[idx]);
	cout << ans << endl;
}

Missing Coin Sum

• 提示
  $MathTheory$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;

int main() {
	IO;
	
	int n;
	cin >> n;
	vector<int> vt(n);
	for(auto& i : vt)
		cin >> i;
	sort(vt.begin(), vt.end());
	ll sum = 0;
	for(auto& i : vt) {
		if(sum+1 < i) {
			cout << sum+1 << endl;
			return 0;
		}
		else
			sum += i;
	}
	cout << sum+1 << endl;
}

原理

加到

$sum$ 時，
代表

$sum$ 以下的數都可以被組合出來，
所以當新的數要加進來時，
只要比

$sum+1$ 小，
就可以和前面的數組成

$sum+1$
概念類似

$DynamicProgramming$

Collecting Numbers

• $SpaceComplexity⟹O(2n)$
• $TimeComplexity⟹O(n)$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

int main() {
	IO;
	
	int n;
	cin >> n;
	vector<int> vt(n), idx(n+1);
	for(auto& i : vt)
		cin >> i;
	for(int i = 0; i < n; ++i)
		idx[vt[i]] = i;
	int ans = 0, top = 1;
	while(top <= n) {
		int Mxid = -1;
		while(top <= n && Mxid < idx[top])
			Mxid = idx[top], ++top;
		ans++;
	}
	cout << ans << endl;
}

Playlist

• $TLE?$
• $Discretization$

原理

先把資料離散化，以方便利用陣列取代map
維護一個處存編號

$K_i$到目前為止出現的最後Index陣列

Code

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

#define endl '\n'

void disn(vector<int>& vt) {
	vector<int> st(vt.begin(), vt.end());
	sort(st.begin(), st.end());
	st.resize(distance(st.begin(), unique(st.begin(), st.end())));
	for(auto& i : vt) i = lower_bound(st.begin(), st.end(), i)-st.begin();
}

void solve() {
	int n;
	cin >> n;
	vector<int> k(n);
	for(auto& i : k)
		cin >> i;
	disn(k);
	vector<int> mp(n, -1);
	int s = 0, ans = -1;
	for(int i = 0; i < n; ++i) {
		s = max(s, mp[k[i]]+1);
		mp[k[i]] = i;
		ans = max(ans, i-s+1);
	}
	cout << ans << endl;
}

int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);

	solve();
}

Towers

• $BinarySearch$

Code

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

#define endl '\n'
#define ar array
using ll = long long;

void solve() {
	int n;
	cin >> n;
	vector<int> vt(n);
	for(auto& i : vt)
		cin >> i;
	vector<int> v;
	for(int i = 0; i < n; ++i) {
		auto it = upper_bound(v.begin(), v.end(), vt[i]);
		if(it != v.end())
			*it = vt[i];
		else
			v.push_back(vt[i]);
	}
	cout << v.size() << endl;
}

int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);

	solve();
}

Traffic Lights

• $SegmentTree+set?$
  
  $⟹multiset+set$

Code

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

#define endl '\n'
#define ar array
using ll = long long;

template<class T>
T mvi(bool s, T it) {
	return s?++it:--it;
}

void solve() {
	int n, x;
	cin >> x >> n;
	set<int> st{0, x};
	multiset<int> ans{x};
	for(int i = 0, t = 0; i < n; ++i) {
		cin >> t;
		st.insert(t);
		auto it = st.find(t), l = mvi(0, it), r = mvi(1, it);
		ans.erase(ans.find(*r-*l));
		ans.insert(t-*l), ans.insert(*r-t);
		cout << *mvi(0, ans.end()) << ' ';
	}
	cout << endl;
}

int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);

	solve();
}

Dynamic Programming

Dice Combinations

• 提示
  $FibonacciSequence$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;

const int M = 1e9+7;

int main() {
	IO;

	int n;
	cin >> n, ++n;
	vector<int> dp(n, 0);
	dp[0] = 1;
	for(int i = 0; i < n; ++i) {
		for(int j = 1; j < min(i, 6)+1; ++j)
			dp[i] = dp[i] % M + dp[i-j] % M, dp[i] %= M;
	}
	cout << dp[n-1] << endl;
}

Minimizing Coins

• 提示
  $Knapsack$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;

int main() {
	IO;

	int n, x;
	cin >> n >> x;
	vector<int> c(n);
	for(auto& i : c)
		cin >> i;
	vector<ll> dp(x+1, 1e18);
	dp[0] = 0;
	for(int i = 0; i < n; ++i) {
		for(int j = c[i]; j <= x; ++j)
			dp[j] = min(dp[j-c[i]]+1, dp[j]);
	}
	cout << (dp[x]==1e18?-1:dp[x]) << endl;
}

Coin Combinations I

• 利用可能數的累加性質
• 錢幣是同時放進去看，才可找到各種組合

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;
 
const int M = 1e9+7;
 
int main() {
	IO;
 
	int n, x;
	cin >> n >> x;
	vector<int> c(n);
	for(auto& i : c)
		cin >> i;
	vector<ll> dp(x+1, 0);
	dp[0] = 1;
	for(int j = 0; j <= x; ++j) {
		for(int i = 0; i < n; ++i)
			if(j-c[i] >= 0)
				dp[j] += dp[j-c[i]], dp[j] %= M;
	}
	cout << dp[x] << endl;
}

Coin Combinations II

跟 Coin Combinations I一樣的概念，只要避免各種組合就好

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;
 
const int M = 1e9+7;
 
int main() {
	IO;
 
	int n, x;
	cin >> n >> x;
	vector<int> c(n);
	for(auto& i : c)
		cin >> i;
	vector<ll> dp(x+1, 0);
	dp[0] = 1;
	for(int i = 0; i < n; ++i) {
		for(int j = c[i]; j <= x; ++j)
			dp[j] += dp[j-c[i]], dp[j] %= M;
	}
	cout << dp[x] << endl;
}

Removing Digits

• 利用可能數的累加性質

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;
 
using ll = long long;

vector<int> sep(int n) {
	vector<int> ret;
	while(n != 0)
		ret.push_back(n%10), n /= 10;
	return ret;
}
 
int main() {
	IO;
 
	int n;
	cin >> n;
	vector<ll> dp(n+1, 1e18);
	dp[0] = 0;
	for(int i = 1; i <= n; ++i) {
		auto s = sep(i);
		for(auto& j : s)
			if(i-j >= 0)
				dp[i] = min(dp[i], dp[i-j]+1);
	}
	cout << dp[n] << endl;
}

Grid Paths

• 利用可能數的累加性質
• 注意可能數的特例

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;
 
const int M = 1e9+7;
 
int main() {
	IO;
 
	int n;
	cin >> n;
	vector<vector<bool>> rd(n, vector<bool>(n, 0));
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j) {
			char c;
			cin >> c;
			rd[i][j] = (c != '*');
		}
	vector<vector<ll>> dp(n, vector<ll>(n, 0));
	dp[0][0] = rd[0][0];
	for(int i = 1; i < n; ++i)
		dp[i][0] = (rd[i][0] ? dp[i-1][0] : 0), dp[0][i] = (rd[0][i] ? dp[0][i-1] : 0);
	for(int i = 1; i < n; ++i)
		for(int j = 1; j < n; ++j)
			dp[i][j] = (rd[i][j] ? dp[i-1][j]+dp[i][j-1]%M : 0), dp[i][j] %= M;
	cout << dp[n-1][n-1] << endl;
}

Book Shop

• 提示
  $Knapsack$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;
 
int main() {
	IO;
 
	int n, x;
	cin >> n >> x;
	vector<ll> dp(x+1, 0);
	vector<int> s(n), h(n);
	for(auto& i : h)
		cin >> i;
	for(auto& i : s)
		cin >> i;
	for(int i = 0; i < n; ++i) {
		for(int j = x; j-h[i] >= 0; --j)
			dp[j] = max(dp[j], dp[j-h[i]]+s[i]);
	}
	cout << dp[x] << endl;
}

Edit Distance

Code

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

#define endl '\n'
#define ar array
using ll = long long;

void solve() {
	string a, b;
	cin >> a >> b;
	int la = a.size(), lb = b.size();
	vector<vector<int>> dp(la+1, vector<int>(lb+1, 0));
	for(int i = 1; i <= la; ++i)
		dp[i][0] = i;
	for(int i = 1; i <= lb; ++i)
		dp[0][i] = i;
	for(int i = 1; i <= la; ++i) {
		for(int j = 1; j <= lb; ++j)
			dp[i][j] = min({dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(a[i-1]!=b[j-1])});
	}
	cout << dp[la][lb] << endl;
}

int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);

	solve();
}

Array Description

Code

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

#define endl '\n'
#define ar array
using ll = long long;

const int M = 1e9+7;

inline void add(ll& a, ll& b) {
	a += b, a %= M;
}

void solve() {
	int n, m;
	cin >> n >> m;
	vector<int> vt(n);
	for(auto& i : vt) cin >> i;
	vector<vector<ll>> dp(n, vector<ll>(m, 0));
	if(vt[0] == 0)
		for(int i = 0; i < m; ++i)
			dp[0][i] = 1;
	else
		dp[0][vt[0]-1] = 1;
	for(int i = 1; i < n; ++i) {
		if(vt[i] == 0) {
			for(int k = 0; k < m; ++k) {
				add(dp[i][k], dp[i-1][k]);
				if(k+1 < m)
					add(dp[i][k], dp[i-1][k+1]);
				if(k-1 >= 0)
					add(dp[i][k], dp[i-1][k-1]);
			}
		} else {
			--vt[i];
			add(dp[i][vt[i]], dp[i-1][vt[i]]);
			if(vt[i]+1 < m)
				add(dp[i][vt[i]], dp[i-1][vt[i]+1]);
			if(vt[i]-1 >= 0)
				add(dp[i][vt[i]], dp[i-1][vt[i]-1]);
		}
	}
	ll ans = 0;
	for(int i = 0; i < m; ++i)
		add(ans, dp[n-1][i]);
	cout << ans << '\n';
}

int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);

	solve();
}

Counting Towers

• $Border?$

想法

以下令

$A$ 為有邊界的正方形，

$B$為無邊界的

該層所有可能為

$AA、AB、BA、BB$
這時只要想什麼情況會重複計算就好
舉例

$ABAA$

$BAAA$
這兩個其實是一樣的
由此可知
可以把

$AA、AB、BA$ 合併成

$X$

$BB$ 則自己獨立成

$Y$
而

$X_i$ 可以是從最初的四種情況而來

$Y_i$ 則只能從

$X_1、Y_i$
所以可得轉移式

$\{\begin{array}{l}{X}_i=4\times X_{i-1}+Y_{i-1}\\ Y_i=X_{i-1}+2\times Y_{i-1}\end{array}$

Code

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

#define endl '\n'
#define ar array
using ll = long long;

const int M = 1e9+7, mxN = 1e6;

inline void add(ll& a, ll b) {
	a += b, a %= M;
}

void solve() {
	int n, t;
	vector<vector<ll>> dp(mxN, vector<ll>(2, 0));
	dp[0][0] = dp[0][1] = 1;
	for(int i = 1; i < mxN; ++i) {
		add(dp[i][0], dp[i-1][0]*4 + dp[i-1][1]);
		add(dp[i][1], dp[i-1][0] + dp[i-1][1]*2);
	}
	cin >> t;
	while(t--) {
		cin >> n, --n;
		cout << (dp[n][0]+dp[n][1])%M << '\n';
	}
}

int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);

	solve();
}

Range Queries

Static Range Sum Queries

• 提示
  $PrefixSum$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;

int main() {
	IO;

	int n, q;
	cin >> n >> q;
	vector<ll> pre(n+1, 0);
	for(int i = 1; i <= n; ++i)
		cin >> pre[i];
	for(int i = 1; i <= n; ++i)
		pre[i] += pre[i-1];
	while(q--) {
		int a, b;
		cin >> a >> b;
		cout << pre[b] - pre[a-1] << endl;
	}
}

Static Range Minimum Queries

• 提示
  $SegmentTree$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

const int mxN = 2e5;

int seg[mxN<<2];

#define mid ((l+r)/2)
#define lc (pos<<1)
#define rc (pos<<1|1)

void build(int pos, int l, int r) {
	if(l == r) {
		cin >> seg[pos];
		return;
	}
	build(lc, l, mid), build(rc, mid+1, r);
	seg[pos] = min(seg[lc], seg[rc]);
}

int qry(int pos, int l, int r, int ql, int qr) {
	if(l == ql && r == qr)
		return seg[pos];
	if(qr <= mid)
		return qry(lc, l, mid, ql, qr);
	else if(mid < ql)
		return qry(rc, mid+1, r, ql, qr);
	return min(qry(lc, l, mid, ql, mid), qry(rc, mid+1, r, mid+1, qr));
}

int main() {
	IO;

	int n, q;
	cin >> n >> q;
	build(1, 1, n);
	while(q--) {
		int a, b;
		cin >> a >> b;
		cout << qry(1, 1, n, a, b) << endl;
	}
}

Dynamic Range Sum Queries

• 提示
  $SegmentTree$、
  $FenwickTree$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;

const int mxN = 2e5;

ll seg[mxN<<2];

#define mid ((l+r)/2)
#define lc (pos<<1)
#define rc (pos<<1|1)

void build(int pos, int l, int r) {
	if(l == r) {
		cin >> seg[pos];
		return;
	}
	build(lc, l, mid), build(rc, mid+1, r);
	seg[pos] = seg[lc] + seg[rc];
}

ll qry(int pos, int l, int r, int ql, int qr) {
	if(l == ql && r == qr)
		return seg[pos];
	if(qr <= mid)
		return qry(lc, l, mid, ql, qr);
	else if(mid < ql)
		return qry(rc, mid+1, r, ql, qr);
	return qry(lc, l, mid, ql, mid) + qry(rc, mid+1, r, mid+1, qr);
}

void upd(int pos, int l, int r, int x, int v) {
	if(l == r) {
		seg[pos] = v;
		return;
	}
	if(x <= mid)
		upd(lc, l, mid, x, v);
	else
		upd(rc, mid+1, r, x, v);
	seg[pos] = seg[lc] + seg[rc];
}

int main() {
	IO;

	int n, q;
	cin >> n >> q;
	build(1, 1, n);
	while(q--) {
		int o, a, b;
		cin >> o >> a >> b, --o;
		if(o)
			cout << qry(1, 1, n, a, b) << endl;
		else
			upd(1, 1, n, a, b);
	}
}

Dynamic Range Minimum Queries

• 提示
  $SegmentTree$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

const int mxN = 2e5;

int seg[mxN<<2];

#define mid ((l+r)/2)
#define lc (pos<<1)
#define rc (pos<<1|1)

void build(int pos, int l, int r) {
	if(l == r) {
		cin >> seg[pos];
		return;
	}
	build(lc, l, mid), build(rc, mid+1, r);
	seg[pos] = min(seg[lc], seg[rc]);
}

int qry(int pos, int l, int r, int ql, int qr) {
	if(l == ql && r == qr)
		return seg[pos];
	if(qr <= mid)
		return qry(lc, l, mid, ql, qr);
	else if(mid < ql)
		return qry(rc, mid+1, r, ql, qr);
	return min(qry(lc, l, mid, ql, mid), qry(rc, mid+1, r, mid+1, qr));
}

void upd(int pos, int l, int r, int x, int v) {
	if(l == r) {
		seg[pos] = v;
		return;
	}
	if(x <= mid)
		upd(lc, l, mid, x, v);
	else
		upd(rc, mid+1, r, x, v);
	seg[pos] = min(seg[lc], seg[rc]);
}

int main() {
	IO;

	int n, q;
	cin >> n >> q;
	build(1, 1, n);
	while(q--) {
		int o, a, b;
		cin >> o >> a >> b, --o;
		if(o)
			cout << qry(1, 1, n, a, b) << endl;
		else
			upd(1, 1, n, a, b);
	}
}

Range Xor Queries

• 提示
  $FenwickTree$、
  $SegmentTree$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

const int mxN = 2e5;

struct ft {
	int siz, bit[mxN+1];

	ft(int _siz) : siz(_siz+1) {
		for(int i = 1; i < siz; ++i)
			cin >> bit[i];
		for(int i = 1; i < siz; ++i) {
			int j = i + (i&-i);
			if(j < siz)
				bit[j] ^= bit[i];
		}
	}

	int qry(int l, int r) {
		--l;
		int ret = bit[l];
		l -= l&-l;
		for(; l; l -= l&-l)
			ret ^= bit[l];
		for(; r; r -= r&-r)
			ret ^= bit[r];
		return ret;
	}
};

int main() {
	IO;

	int n, q;
	cin >> n >> q;
	ft tr(n);
	while(q--) {
		int a, b;
		cin >> a >> b;
		cout << tr.qry(a, b) << endl;
	}
}

Range Update Queries

• $SegmentTree+LazyPropagation$
• $FenwickTree$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;

const int mxN = 2e5;

ll seg[mxN<<2], tag[mxN<<2];

#define mid ((l+r)/2)
#define lc (pos<<1)
#define rc (pos<<1|1)

void push(int pos, int l, int r) {
	if(tag[pos]) {
            if(l != r)
		    tag[lc] += tag[pos], tag[rc] += tag[pos];
		seg[lc] += tag[pos] * (mid-l+1), seg[rc] += tag[pos] * (r-mid);
		tag[pos] = 0;
	}
}

void build(int pos, int l, int r) {
	if(l == r) {
		cin >> seg[pos];
		return;
	}
	build(lc, l, mid), build(rc, mid+1, r);
	seg[pos] = seg[lc] + seg[rc];
}

void upd(int pos, int l, int r, int ql, int qr, int v) {
	if(l == ql && r == qr) {
		tag[pos] += v;
		seg[pos] += v * (r-l+1);
		return;
	}
	push(pos, l, r);
	if(qr <= mid)
		upd(lc, l, mid, ql, qr, v);
	else if(mid < ql)
		upd(rc, mid+1, r, ql, qr, v);
	else
		upd(lc, l, mid, ql, mid, v), upd(rc, mid+1, r, mid+1, qr, v);
	seg[pos] = seg[lc] + seg[rc];
}

ll qry(int pos, int l, int r, int x) {
	if(l == r)
		return seg[pos];
	push(pos, l, r);
	if(x <= mid)
		return qry(lc, l, mid, x);
	else
		return qry(rc, mid+1, r, x);
}

int main() {
	IO;

	int n, q;
	cin >> n >> q;
	build(1, 1, n);
	while(q--) {
		int o, a, b, u, k;
		cin >> o, --o;
		if(o) {
			cin >> k;
			cout << qry(1, 1, n, k) << endl;
		}
		else {
			cin >> a >> b >> u;
			upd(1, 1, n, a, b, u);
		}
	}
}

Forest Queries

• 提示
  $PrefixSum$、
  $2DSegmentTree$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

using ll = long long;

int main() {
	IO;

	int n, q;
	cin >> n >> q;
	vector<vector<ll>> pre(n+1, vector<ll>(n+1, 0));
	for(int i = 1; i <= n; ++i) {
		char c;
		for(int j = 1; j <= n; ++j) {
			cin >> c;
			pre[i][j] = (c == '*');
			pre[i][j] += pre[i][j-1];
		}
	}
	while(q--) {
		int y1, x1, y2, x2; 
		cin >> y1 >> x1 >> y2 >> x2, --x1;
		ll ans = 0;
		for(int i = y1; i <= y2; ++i)
			ans += (pre[i][x2] - pre[i][x1]);
		cout << ans << endl;
	}
}

Hotel Queries

• $SegmentTree+BinarySearch$

Code

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

#define endl '\n'
#define ar array
using ll = long long;
 
const int mxN = 2e5;
int seg[mxN<<2], n, m;
 
#define lc (id<<1)
#define rc (id<<1|1)
#define mid ((l+r)/2)
 
void pull(int id, int l, int r) {
	if(l != r) seg[id] = max(seg[lc], seg[rc]);
}
 
void build(int id, int l, int r) {
	if(l == r) {
		cin >> seg[id];
		return;
	}
	build(lc, l, mid), build(rc, mid+1, r);
	pull(id, l, r);
}
 
void updQry(int id, int l, int r, int v) {
	if(l == r) {
		if(seg[id] >= v) {
			cout << l << ' ';
			seg[id] -= v;
		} else {
			cout << 0 << ' ';
		}
		return;
	}
	if(seg[lc] >= v)
		updQry(lc, l, mid, v);
	else
		updQry(rc, mid+1, r, v);
	pull(id, l, r);
}
 
void solve() {
	cin >> n >> m;
	build(1, 1, n);
	for(int i = 0; i < m; ++i) {
		int q;
		cin >> q;
		updQry(1, 1, n, q);
	}
}
 
int main() {
        cin.tie(0), ios_base::sync_with_stdio(0);
    
	solve();
}

Tree Algorithms

Subordinates

• 提示
  $DFS$

Code

#include <bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0), ios_base::sync_with_stdio(0)
using namespace std;

vector<vector<int>> adj;
vector<int> dis;

void dfs(int i) {
	if(adj[i].empty())
		return;
	for(auto& j : adj[i])
		dfs(j);
	for(auto& j : adj[i])
		dis[i] += dis[j]+1;
}

int main() {
	IO;
	
	int n;
	cin >> n;
	adj.resize(n+1), dis.resize(n+1, 0);
	for(int i = 2, t = 0; i <= n; ++i) {
		cin >> t;
		adj[t].push_back(i);
	}
	dfs(1);
	for(int i = 1; i <= n; ++i)
		cout << dis[i] << ' ';
	cout << endl;
}

Distance Queries

• 提示
  $LCA$

Code

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ar array
using ll = long long;
 
int n, q;
vector<vector<int>> adj, anc;
vector<int> din, dout, dpt;
 
bool isanc(int n1, int n2) { // is n1 the anc of n2
	return din[n1] <= din[n2] && dout[n1] >= dout[n2];
}
 
void build(int node, int fnode) {
	static int ti = 0;
	dpt[node] = dpt[fnode]+1;
	din[node] = ti++;
	int _fd = fnode;
	for(int i = 0; i <= __lg(n); ++i)
		anc[node][i] = _fd, _fd = anc[_fd][i];
	for(auto& nd : adj[node])
		if(nd != fnode)
			build(nd, node);
	dout[node] = ti++;
}
 
int qry(int n1, int n2) {
	if(isanc(n1, n2)) return n1;
	if(isanc(n2, n1)) return n2;
	for(int i = __lg(n); i >= 0; --i) {
		if(!isanc(anc[n1][i], n2))
			n1 = anc[n1][i];
	}
	return anc[n1][0];
}
 
void solve() {
	cin >> n >> q;
	adj.resize(n+1), din.resize(n+1), dout.resize(n+1), anc.resize(n+1, vector<int>(__lg(n)+1)), dpt.resize(n+1, 0);
	for(int i = 0; i < n-1; ++i) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	build(1, 1);
	while(q--) {
		int a, b;
		cin >> a >> b;
		int ac = qry(a, b);
		cout << dpt[a]+dpt[b]-dpt[ac]*2 << endl;
	}
}
 
int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);
	
	solve();
}

Tree Diameter

• 提示
  $DP、TreeHeight、DFS$

Code

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ar array
using ll = long long;
 
int n, a, b, ans;
vector<vector<int>> adj;
vector<int> dp;
 
void dfs(int node, int fnode) {
	dp[node] = dp[fnode]+1;
	for(auto& nd : adj[node]) {
		if(nd != fnode)
			dfs(nd, node);
	}
	vector<int> cal(2, 0);
	for(auto& nd : adj[node]) {
		auto it = lower_bound(cal.begin(), cal.end(), dp[nd]);
		if(it == cal.end())
			cal[0] = cal[1], cal[1] = dp[nd];
		else if(it != cal.begin())
			--it, *it = dp[nd];
	}
	ans = max(ans, cal[0]+cal[1]-2*dp[node]);
	for(auto& nd : adj[node])
		dp[node] = max(dp[node], dp[nd]);
}
 
void solve() {
	cin >> n;
	adj.resize(n, vector<int>(0)), dp.resize(n+1, -1);
	for(int i = 0; i < n-1; ++i) {
		cin >> a >> b, --a, --b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(0, n);
	cout << ans << endl;
}
 
int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);
 
	solve();
}

Graph Algorithms

Road Reparation

• 提示
  $Pri{m}^{\prime }sAlgorithm$

Code

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

#define endl '\n'
#define ar array
using ll = long long;

vector<vector<ar<int,2>>> adj; // [cost, NextCity]

void solve() {
	int n, m;
	cin >> n >> m;
	adj.resize(n+1);
	for(int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back(ar<int,2>{c, b});
		adj[b].push_back(ar<int,2>{c, a});
	}
	priority_queue<ar<int,2>, vector<ar<int,2>>, greater<ar<int,2>>> pq;
	vector<bool> vis(n+1, 0);
	pq.push(ar<int,2>{0, 1});
	ll ans = 0, cnt = 0;
	while(!pq.empty()) {
		auto t = pq.top(); pq.pop();
		if(vis[t[1]]) continue;
		ans += t[0], cnt++, vis[t[1]] = 1;
		for(auto& nd : adj[t[1]]) {
			if(!vis[nd[1]])
				pq.push(nd);
		}
	}
	if(cnt != n)
		cout << "IMPOSSIBLE" << endl;
	else
		cout << ans << endl;
}

int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);

	solve();
}

Counting Rooms

• $DFS$

Code

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

#define endl '\n'
#define ar array
using ll = long long;

int n, m;
const vector<ar<int,2>> mvc{ar<int,2>{0, 1}, ar<int,2>{1, 0}, ar<int,2>{-1, 0}, ar<int,2>{0, -1}};
vector<vector<bool>> graph;

void dfs(int i, int j) {
	graph[i][j] = 0;
	for(auto& mv : mvc) {
		if(i+mv[0] < n && i+mv[0] >= 0 && j+mv[1] < m && j+mv[1] >= 0 && graph[i+mv[0]][j+mv[1]])
			dfs(i+mv[0], j+mv[1]);
	}
}

void solve() {
	cin >> n >> m;
	graph.resize(n, vector<bool>(m));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			char c;
			cin >> c;
			graph[i][j] = (c == '.');
		}
	}
	int ans = 0;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			if(graph[i][j])
				dfs(i, j), ++ans;
		}
	}
	cout << ans << endl;
}

int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);

	solve();
}

Road Construction

• 提示
  $DSU$

Code

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

#define endl '\n'
#define ar array
using ll = long long;

struct dsu {
	int asz, mxs = 1;
	vector<int> anc, sz;

	dsu(int _asz) : asz(_asz) {
		anc.resize(asz), sz.resize(asz, 1);
		iota(anc.begin(), anc.end(), 0);
	}

	int find(int nd) {
		return anc[nd] == nd ? nd : anc[nd]=find(anc[nd]);
	}

	void join(int na, int nb) {
		int a = find(na), b = find(nb);
		if(a == b)
			return;
		--asz;
		if(sz[a] > sz[b]) swap(a, b);
		anc[a] = b;
		sz[b] += sz[a];
		mxs = max(mxs, sz[b]);
	}
};

void solve() {
	int n, m;
	cin >> n >> m;
	dsu st(n);
	while(m--) {
		int a, b;
		cin >> a >> b, --a, --b;
		st.join(a, b);
		cout << st.asz << ' ' << st.mxs << endl;
	}
}

int main() {
	cin.tie(0), ios_base::sync_with_stdio(0);

	solve();
}

---

revcoding