# Dãy Liên Tiếp - Solution

## Subtask 3

Do $1 \le l \le r \le 5000$, và $a_i \le 5000$, ta có thể dùng thuật toán $O(n \times q)$ bằng đếm phân phối như sau:
- Gọi $cnt_i$ là số lần xuất hiện của giá trị $i$ trong dãy $C$ được tạo bởi đoạn $[l,r]$.
- Ta sẽ duyệt qua từng $a_i$ trong $[l,r]$, ta biết rằng giá trị $a_i$ này sẽ xuất hiện trong $(i-l+1)\times(r-i+1)$ đoạn con của đoạn $[l,r]$. Vậy nên, ta cộng thêm cho $cnt_{a_i}$ một lượng bằng $(i-l+1)\times(r-i+1)$.
- Sau đó, ta duyệt các giá trị $i$ trong khoảng từ $[1,5000]$, nếu tổng tiền tố của nó không bé hơn $k$ thì $i$ chính là đáp án của truy vấn.

## Subtask 4

Dựa vào nhận xét, giá trị $a_i$ này sẽ xuất hiện trong $(i-l+1)\times(r-i+1)$ đoạn con của đoạn $[l,r]$, ta có thể biến đổi một chút như sau:
- $(i-l+1)\times(r-i+1) = -i^2 + i\times(r+l) + (r-l+1 - r\times l)$

Từ đây, với mảng $cnt_i$ được định nghĩa như subtask $3$, ta có thể tính $cnt_x = \sum (-i^2 + i\times(r+l) + (r-l+1 - r\times l))$, $\forall i \in [l,r]$ và $a_i = x$.

Do $1 \le a_i \le 100$, ta có thể dùng mảng cộng dồn để tính tương ứng với $3$ giá trị trong phép tính.

## Subtask 5

Xét với mỗi truy vấn, nếu ta hoàn toàn có thể tìm kiếm nhị phân kết quả của nó, tức là chỉ cần kiểm tra xem liệu giá trị $x$ **lớn hơn hoặc bằng** bao nhiêu giá trị của dãy $C$ tạo bởi đoạn $[l,r]$. Tuy nhiên, việc kiểm tra này sẽ mất $O(n)$.

Vậy nên, ta cần áp dụng phương pháp chặt nhị phân song song để xử lí cùng lúc tất cả các truy vấn. Kết hợp thêm với phương pháp sweepline $1$ chiều để check.

Độ phức tạp: $O(n \times log^2)$.
## Subtask 6

Thay vì cần chặt nhị phân song song, ta có thể thay bằng Persistent Tree để cho ra độ phức tạp $O(n\times log)$.

## Code mẫu (subtask $3,4,5$):

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,q;
int a[N];
int mx = 0;
namespace sub3 {
	const int N = 5050;
	int cnt[N];
	void solve () {
		while (q--) {
			int l,r,k; cin >> l >> r >> k;
			int cur = 0;
			for (int i=1; i<=5000; i++) cnt[i] = 0;
			for (int i=l; i<=r; i++) {
				cnt[a[i]] += (i-l+1)*(r-i+1);
			}
			for (int i=1; i<=5000; i++) {
				cur += cnt[i];
				if (cur >= k) {
					cout << i << '\n';
					break;
				}
			}  
		}
	}
}
namespace sub4 {
	int f[101][N],s[101][N],cnt[101][N];
	int get (int i, int l, int r) {
		return (f[i][r]-f[i][l-1])*(r+l) + (s[i][r]-s[i][l-1]) + (cnt[i][r]-cnt[i][l-1])*(r-l+1-r*l);
	}
	void solve () {
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=100; j++) f[j][i] = f[j][i-1],s[j][i] = s[j][i-1],cnt[j][i] = cnt[j][i-1];
			f[a[i]][i] += i;
			s[a[i]][i] += -(i*i);
			cnt[a[i]][i] ++; 
		}
		while (q--) {
			int l,r,k; cin >> l >> r >> k;
			int res = 0;
			for (int i=1; i<=100; i++) {
				res += get(i,l,r);
				if (res >=k) {
					cout << i << '\n';
					break;
				} 
			}
		}
	}
}
namespace sub5 {
	struct fenwick {
		int n;
		vector<int> bit;
		fenwick (int n) : n(n), bit(n+6){}
		void update (int u, int val) {
			while (u <= n) bit[u] += val, u += u&(-u);
		}
		int get (int u) {
			int ans = 0;
			while (u>0) ans += bit[u], u -= u&(-u);
			return ans; 
		}
		void xoa () {
			for (int i=1; i<=n; i++) bit[i] = 0; 
		}
	};
	struct qr {
		int l,r,k;
	}go[N];
	struct vcl {
		int sig,mid,id;
	}; vector<vcl> event[N];
	int l[N],r[N],res[N],val[N];
	void solve () {
		for (int i=1; i<=q; i++) {
			cin >> go[i].l >> go[i].r >> go[i].k;
			l[i] = 1; r[i] = mx;
		}
		bool gone = false;
		fenwick f(mx),s(mx),cnt(mx);
		while (gone == false) {
			gone = true;
			f.xoa(); s.xoa(); cnt.xoa();
			for (int i=1; i<=q; i++) {
				val[i] = 0;
				if (l[i] > r[i]) continue;
				gone = false;
				int mid = (r[i] + l[i]) >> 1;
				event[go[i].l].push_back({1,mid,i});
				event[go[i].r+1].push_back({-1,mid,i});
			}
			for (int i=n; i>=1; i--) {
				f.update (a[i],i);
				s.update (a[i],-(i*i));
				cnt.update (a[i],1);
				for (int cc=0; cc<event[i].size(); cc++) {
					vcl cur = event[i][cc];
					int id = cur.id;
					int add = f.get(cur.mid)*(go[id].l+go[id].r)+s.get(cur.mid)+cnt.get(cur.mid)*(go[id].r-go[id].l+1-go[id].r*go[id].l);
					add = cur.sig*add;
					val[id] += add;
				} 
				event[i].clear();
			}
			event[n+1].clear();
			for (int i=1; i<=q; i++) {
				if (l[i] > r[i]) continue;
				int mid = (r[i] + l[i]) >> 1;
				if (val[i] >= go[i].k) res[i] = mid, r[i] = mid - 1;
				else l[i] = mid + 1;
			}
		}
		for (int i=1; i<=q; i++) cout << res[i] << '\n';
	}
} 
signed main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	freopen("DLT.inp","r", stdin);
	freopen("DLT.out", "w", stdout);
	cin >> n >> q;
	for (int i=1; i<=n; i++) cin >> a[i], mx = max (mx,a[i]);
	if (mx <= 5000&&n<=5000&&q<=5000) sub3::solve();
	else if (mx<=100) sub4::solve();
	else sub5::solve();
}