## Dãy số chẵn lẻ đẹp

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pii=pair<int, int>;
using pll=pair<ll, ll>;
using vi=vector<int>;
using vll=vector<ll>;

struct FenwickTree {
	vector<ll> bit;
	int n;
	FenwickTree(int n) {
		this->n = n;
		bit.assign(n, 0);
	}
	ll sum(int idx) {
		ll ret = 0;
		for (; idx >= 0; idx = (idx & (idx + 1)) - 1)
			ret += bit[idx];
		return ret;
	}
	ll sum(int l, int r) {
		return sum(r) - sum(l - 1);
	}
	void add(int idx, int delta) {
		for (; idx < n; idx = idx | (idx + 1))
			bit[idx] += delta;
	}
};

int n, k, a[200005];
ll b[200005], ps[200005];
FenwickTree fwt(200005);

int main() {
	#define name "DAYSOCHANLEDEP"
	if(fopen(name".inp", "r")){
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		ps[i] = ps[i-1];
		if (a[i]&1) ps[i] -= a[i];
		else ps[i] += a[i];
		b[i] = ps[i];
	}
	sort(b, b+n+1);
	int p=1;
	ll ans=0;
	for (int i=1; i<=n; i++) {
		while (a[p]%2!=a[i]%2) {
			int pos = lower_bound(b, b+n+1, ps[p-1]) - b;
			fwt.add(pos, 1);
			++p;
		}
		int l = lower_bound(b, b+n+1, ps[i]-k) - b;
		int r = upper_bound(b, b+n+1, ps[i]) - b - 1;
		ans += fwt.sum(l, r);
	}
	cout << ans;
	return 0;
}

## FastFood

#include<bits/stdc++.h>
using namespace std;
const int N = 1501;
vector<int> cnt[N*N];
int n;
int b[N*N];
int sum[N*N];
int ans[2*N];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i=1; i<=n; i++) {
		int val;
		for (int j=1; j<=n; j++) {
			cin >> val;
			cnt[val].push_back(j);
		}
	}
	for (int i=1; i<=n*n; i++) {
		int res = 0;
		int sz = cnt[i].size();
		for (int j=1; j<=sz; j++) b[j] = 1e9;
		for (int j=0; j<sz; j++) {
			int u = cnt[i][j];
			int pos = upper_bound (b,b+sz+1,u) - b;
			sum[j] = pos;
			b[pos] = u;
		}
		res = 0;
		for (int j=1; j<=sz; j++) b[j] = 1e9;
		for (int j=(int) sz-1; j>=0; j--) {
			int u = n-cnt[i][j]+1;
			int pos = upper_bound (b,b+sz+1,u) - b;
			b[pos] = u;
			ans[sum[j]+pos-1]++;
		}
	}
	for (int i=1; i<=2*n-1; i++) cout << ans[i] << '\n';
}

## abc

Giờ ta sẽ đi tìm lần lượt độ dài lớn nhất của đoạn con mà nó chứa quá bán kí tự $a$, $b$ rồi $c$.

Giả sử ta đang giải bài toán với kí tự $a$ chiếm quá bán:
- Đặt $b_i = 1$ nếu kí tự $i$ là $a$, ngược lại bằng $-1$.
- Bài toán lúc này quy về **tìm đoạn con có tổng dương dài nhất**. Các bạn có thể giải trong $O(n \times log)$, tham khảo tại [đây](https://www.geeksforgeeks.org/longest-subarray-with-sum-greater-than-equal-to-zero/) (bài tham khảo là tổng không âm).

<details>
<summary>Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
string s;
int n;
int a[N],f[N];
int solve (char c) {
	int ans = 0;
	for (int i=1; i<=n; i++) {
		a[i] = a[i-1];
		if (s[i] == c) a[i] += 1;
		else a[i] -= 1;
		int l = 1, r = i, res = i;
		f[i] = min (f[i-1],a[i]);
		while (r >= l) {
			int mid = (r-l+1);
			if (a[i] - f[mid] > 0) {
				res = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		ans = max (ans,i-res);
	}
	return ans;
}
void go () {
	cin >> n >> s;
	s = "?" + s;
	int res = max ({solve('a'), solve('b'), solve ('c')});
	cout << res << endl;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	go();
}

</details>

## Biển số xe
Ta sẽ chia ra $3$ biến lưu $3$ phần của biển số:
- Phần $2$ số đầu tiên
- Phần chữ cái
- Phần $7$ số cuối cùng

Sau đó, ta sẽ cộng dần kết quả vào phần $7$ chữ số cuối cùng.
Để đơn giản, ta cứ cộng lần lượt một lượng vừa đủ để $7$ chữ số cuối chạm mốc $10^7$, sau đó gán giá trị phần cuối cùng là $0$ và tăng chữ cái lên, nếu chữ cái đang là $‘Z’$ thì chuyển qua $‘A’$ và tăng phần đầu tiên lên $1$ đơn vị. Nếu $K$ không còn đủ lớn để cộng như vậy, ta cộng thẳng $K$ vào $7$ chữ số cuối cùng và kết thúc quá trình.

<details>
<summary>Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long
void print (int n, int k) {
	vector<int> v;
	while (n) v.push_back(n%10), n /= 10;
	while (v.size() < k) v.push_back(0);
	reverse(v.begin(),v.end());
	for (auto u : v) cout << u;
}
void solve () {
	string s;
	cin >> s;
	int k;
	cin >> k;
	int dau = (s[0]-'0')*10 + s[1] - '0';
	char giua = s[2];
	int cuoi = 0;
	for (int i=3; i<=9; i++) cuoi = cuoi*10 + s[i] - '0';
	int full = 1e7;
	while (k) { 
		int need = full - cuoi;
		if (need > k) {
			cuoi += k;
			break; 
		}
		else {
			cuoi = 0;
			k -= need;
			if (giua == 'Z') {
				giua = 'A';
				dau++;
			} 
			else {
				giua = char (giua + 1);
			}
		}
	}
	print (dau,2); 
	cout << giua;
	print (cuoi,7);
	cout << endl;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

</details>

## CApp

Do $a_i \le 2*10^5$ nên ta có thể dùng đếm phân phối.

Gọi $cnt_a$ là số lần giá trị $a$ xuất hiện trong đoạn đang xét hiện tại.

Gọi $res$ là kết quả tốt nhất hiện tại, $cur$ là giá trị $cnt(l,r)$ hiện tại.

Ta có hai thao tác:
- $add(a):$ $cnt_a++$, nếu $cnt_a = x$ thì $cur++$.
- $del(b):$ nếu $cnt_b = x$ thì $cur--$. Sau đó $cnt_b--$.

Ta thực hiện $add(a_i)$ với $i \in [1,k]$, lúc này ta sẽ có $cur$ là kết quả của đoạn $[1,k]$. Cập nhật $res$ với $cur$.

Để chuyển lên tính đoạn $[2,k+1]$, ta $del(a_1)$ đi và $add(a_{k+1})$ vào, lúc này biến $cur$ thành kết quả của đoạn $[2,k+1]$. Cập nhật $res$ với $cur$.

Cứ dịch như vậy tới khi xét hết tất cả các đoạn.

Độ phức tạp: $O(n)$.

<details>
<summary>Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int n,k,x;
int a[N],cnt[N];
int cur = 0;
void del (int val) {
	if (cnt[val] == x) cur--;
	cnt[val]--;
}
void add (int val) {
	cnt[val]++;
	if (cnt[val] == x) cur++; 
}
namespace trau {
	void solve () {
		int res = 0;
		for (int i=1; i<=n-k+1; i++) {
			int cur = 0;
			memset (cnt,0,sizeof(cnt));
			for (int j=i; j<=i+k-1; j++) {
				cnt[a[j]]++;
				if (cnt[a[j]] == x) cur++;
			}
			res = max (res,cur);	
		}
		cout << res ;
	}
}
void solve () {
	memset (cnt,0,sizeof(cnt));
	cin >> n >> k >> x;
	for (int i=1; i<=n; i++) {
		cin >> a[i];
	}
	int res = 0;
	cur = 0;
	for (int i=1; i<=k; i++) {
		add (a[i]);
	}
	res = cur;
	for (int i=k+1; i<=n; i++) {
		del(a[i-k]);
		add(a[i]);
		res = max (res,cur);
	}
	cout << res << endl;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

</details>

## MaxMod

Duyệt phân tập, gọi tập $a$ là những tổng đã sinh ra được từ nửa đầu, tập $b$ là tập những tổng đã sinh ra được từ nửa cuối.

Với mỗi phần tử trong tập $a$ hoặc $b$, ta lấy phần dư của nó với $m$. Sau đó, $sort$ các tập này lại.

Gọi phần tử đang xét ở tập $a$ là $u$, ta cần tìm một giá trị $v$ ở tập $b$ sao cho $(u+v)\%m$ là lớn nhất. Do $u,v < m$, vậy nên ta chỉ cần tìm phần tử $v$ sao cho $v$ lớn nhất và bé hơn hoặc bằng $m-u-1$. Bởi nếu ta lấy quá giá trị này, lúc đó $u+v \ge m$, và do $v < m$ nên $(u+v)\%m < u$, như vậy ta có thể lấy riêng tập $u$ sẽ tối ưu hơn.

Việc tìm $v$ có thể thực hiện bằng tìm kiếm nhị phân.

<details>
<summary>Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long	
int n,m;
vector<int> a,b;
const int N = 45;
int c[N];
void ql_first(int id, int sum) {
	if (id == n/2 + 1) {
		a.push_back(sum);
		return;
	}
	ql_first(id+1,sum);
	ql_first(id+1,(sum+c[id])%m);
}
void ql_second (int id, int sum) {
	if (id == n + 1) {
		b.push_back(sum);
		return;
	}
	ql_second(id+1,sum);
	ql_second(id+1,(sum+c[id])%m);
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i=1; i<=n; i++) {
		cin >> c[i];
	}
	a.push_back(0);
	b.push_back(0);
	ql_first(1,0);
	ql_second(n/2+1,0);
	sort (a.begin(),a.end());
	sort (b.begin(),b.end());
	int ans = 0;
	for (auto u : a) {
		int id = upper_bound (b.begin(),b.end(),m-u-1) - b.begin() - 1;
		ans = max (ans,u + b[id]);
	}
	cout << ans << '\n';
}

</details>

## LCMAX

Ta nhận thấy rằng, ta sẽ luôn chọn tách $n$ ra thành tổng của các lũy thừa của số nguyên tố phân biệt để tối ưu nhất, lưu ý rằng ta không nhất thiết cần chúng phải có tổng bằng đúng $n$, bởi vì ta có thêm bù các số $1$ vào mà không ảnh hưởng tới kết quả.

Gọi $dp(i,j)$ là bội chung lớn nhất thu được để tạo ra số bằng $i$ và chỉ dùng $j$ số nguyên tố đầu tiên. Tới lúc này ta chỉ cần duyệt số mũ (rất nhỏ) nữa để chuyển trạng thái.

<details>
<summary>Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int n;
const int N = 350;
int f[N][N];
int p[N];
int cnt[N];
int m;
void sieve () {
	for (int i=1; i<=350; i++) p[i] = 1;
	for (int i=2; i <= 350; i++) {
		if (p[i]) {
			for (int j=i*i; j<=350; j+=i) p[j] = 0;
			cnt[++m] = i;
		}
	} 
}
int dak;
void solve () {
	cin >> n;
     f[0][0] = 1;
	 for (int i=0; i<=m; i++) f[0][i] = 1;
	 for (int i=1; i<=n; i++) {
	 	for (int j=1; j<=m; j++) {
	 		f[i][j] = max (f[i][j-1],f[i-1][j]);
	 		for (int k=cnt[j]; k<=i; k=k*cnt[j]){
	 			 f[i][j] = max (f[i-k][j-1]*k,f[i][j]);
			 }
		 }
	 }
	 cout << f[n][m] << '\n';
}
signed main() {
	 sieve();
	 int t; t = 1;
	 while (t--) solve();
}

</details>