# [Solution] Bài tập 3/3/2023

:::info
:bulb: Unofficial solution written by sweetestlove.
:warning: Thuật toán đúng tuy nhiên code mẫu chưa test kĩ, có thể sai sót.
:::

## Bài 1: Bộ 3 số
:book: Thuật toán: Bruteforce

Ta nhận thấy $n$ là $1e5$, nếu sử dụng duyệt $3$ lần, tức $O(n^3)$ thì chắc chắn sẽ bị quá thời gian. Tuy nhiên ta để ý giá trị $a_i$ có giá trị tuyệt đối $<=100$, vi thế ta sẽ duyệt trên giá trị của $a_i$ thay vì duyệt theo n.

Độ phức tạp: $O(200^3)$

:::spoiler C++ Solution

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

int n, val[205], res=0;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        int x;
        cin >> x;
        val[x+100]++;
    }
    for (int i=1; i<=200; i++) {
        for (int j=i+1; j<=200; j++) {
            for (int k=j+1; k<=200; k++) {
                if (val[i]!=0 && val[j]!=0 && val[k]!=0 && (i+j+k)%3==0 && val[(i+j+k)/3] != 0 && (i+j+k)/3!=i && (i+j+k)/3!=j && (i+j+k)/3!=k) {
                    //cout << i << ' ' << j << ' ' << k << '\n';
                    res+=(val[i]*val[j]*val[k]);
                }
            }
        }
    }
    cout << res;
    return 0;
}

:::

---

## Bài 2: Tích ba số
:book: Thuật toán: Merge sort tree, segment tree.

:point_right: Chi tiết thuật toán:
Ta để ý bản chất bài toán là tìm số đoạn liên tiếp có kích cỡ là $k+1$ trên khoảng từ $1->n$. Sử dụng cấu trúc sữ liệu merge sort tree (nâng cao của segment tree) để cài đặt, qua đó với mỗi đoạn từ $1$ đến $n-k+1$ ta sẽ lấy 3 số lớn nhất để có tích của chúng là lớn nhất (điều này là hiển nhiên vì tích của 3 số lớn nhất trong một đoạn con chính là tích lớn nhất mà đoạn con đó đạt đuợc).
Độ phức tạp: $O(n*(nlog2(k)))$

:::spoiler C++ Solution

/*
* @Author: tsumondai
* @Date:   2023-03-01 23:13:00
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e9 + 7, mod = 1e9 + 7;
 
int n, m, a[N], k, maxRange[N];
vector<int> arr;

void read() {
	cin >> n >> k;
	foru(i,0,n-1) cin >> a[i];
	k++;
}

void init() {
	
}

namespace subtask23 {
	vector<int> seg[N];
	void build(int ci, int st, int end,
			pair<int, int>* B)
	{
		if (st == end) {
			seg[ci].push_back(B[st].second);
			return;
		}

		int mid = (st + end) / 2;
		build(2 * ci + 1, st, mid, B);
		build(2 * ci + 2, mid + 1, end, B);
		merge(seg[2 * ci + 1].begin(), seg[2 * ci + 1].end(),
			seg[2 * ci + 2].begin(), seg[2 * ci + 2].end(),
			back_inserter(seg[ci]));
	}
	int query(int ci, int st, int end,
			int l, int r, int k)
	{
		// Base case
		if (st == end)
			return seg[ci][0];
		int p = upper_bound(seg[2 * ci + 1].begin(),
							seg[2 * ci + 1].end(), r)
				- lower_bound(seg[2 * ci + 1].begin(),
							seg[2 * ci + 1].end(), l);

		int mid = (st + end) / 2;
		if (p >= k)
			return query(2 * ci + 1, st, mid, l, r, k);
		else
			return query(2 * ci + 2, mid + 1, end, l, r, k - p);
	}

	void process() {
		pair<int, int> B[N];

		for (int i = 0; i < n; i++) {
			B[i] = { a[i], i };
		}
		sort(B, B + n);

		build(0, 0, n - 1, B);

		int res=-1;
		foru(i,0,n-k) {
			res=max(res, a[query(0,0,n-1,i,i+k-1,k)] * a[query(0,0,n-1,i,i+k-1,k-1)] * a[query(0,0,n-1,i,i+k-1,k-2)]);
		}
		cout << res;
	}
}



signed main() {
	cin.tie(0)->sync_with_stdio(false);
	freopen("three.inp", "r", stdin);
	freopen("three.out", "w", stdout);
	read();
	init();
	subtask23::process();
	return 0;
}

:::