# Bài A - [Appy Loves One](https://www.codechef.com/problems/HMAPPY1)

## Tóm tắt đề bài

Cho dãy nhị phân $A$ có $n$ phần tử.
Cho $q$ truy vấn 2 loại:
- loại 1 - `!`: dịch(cyclic shift) dãy A sang phải 1 lần
- loại 2 - `?`: tìm đoạn con toàn 1 dài nhất $\leq k$

$k \leq n \leq 10^5, q \leq 3*10^5$

## Lời giải

### Thuật trâu $O(q * n)$:

Trước hết, thay vì dịch $A$, chúng ta sẽ gấp đôi dãy $A$.

Để trả lời truy vấn loại 2, ta sẽ for qua cả đoạn và tìm đoạn con toàn 1 dài nhất.

### Thuật chuẩn $O(q * \log n)$:

Ta sẽ sử dụng cây phân đoạn, mỗi nút sẽ lưu 4 thông tin để giúp ta có thể gộp được 2 nút lại:
- `le` là độ dài tiền tố dài nhất toàn 1
- `ri` là độ dài hậu tố dài nhất toàn 1
- `val` là độ dài đoạn con toàn 1 dài nhất
- `sz` là độ dài của đoạn

Khi gộp 2 nút `u` `v` lại thành nút `w`,
- `w.le` bằng `u.le`, nếu nút `u` toàn 1 thì là `u.sz + v.le`
- `w.le` bằng `v.ri`, nếu nút `v` toàn 1 thì là `v.sz + u.ri`
- `w.val` là max của `u.val`, `v.val`, hoặc là đoạn toàn 1 ở giữa `u` và `v`: `u.ri + v.le`
- `w.sz` đơn giản là tổng `u.sz + v.sz`
Ảnh chôm từ [Codeforces EDU](https://codeforces.com/edu/course/2/lesson/4/2)

### Code:

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

const int N = 2e5 + 5;

struct Node {
    int le, ri, val, sz;
};

int n, q, k;
int a[N];
Node seg[4 * N];

Node operator + (const Node& u, const Node& v) {
    return {
        u.le + (u.le == u.sz) * v.le, 
        v.ri + (v.ri == v.sz) * u.ri, 
        max({u.val, v.val, u.ri + v.le}), 
        u.sz + v.sz
    };
}

void Build(int x, int lx, int rx) {
    if (lx == rx) {
        seg[x] = a[lx] == 1 ? Node{1, 1, 1, 1} : Node{0, 0, 0, 1};
        return;
    }
    int m = (lx + rx) / 2;
    Build(2 * x, lx, m);
    Build(2 * x + 1, m + 1, rx);
    seg[x] = seg[2 * x] + seg[2 * x + 1];
}

Node Get(int l, int r, int x, int lx, int rx) {
    if (lx > r || rx < l) return {0, 0, 0, 0};
    if (l <= lx && rx <= r) return seg[x];
    int m = (lx + rx) / 2;
    return Get(l, r, 2 * x, lx, m) + Get(l, r, 2 * x + 1, m + 1, rx);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[n + i] = a[i];
    }
    Build(1, 1, 2 * n);
    int l = 1, r = n;
    while (q--) {
        char c;
        cin >> c;
        if (c == '!') {
            l--;
            if (l < 1) l += n;
            r = l + n - 1;
        } else {
            Node ans = Get(l, r, 1, 1, 2 * n);
            cout << min(ans.val, k) << '\n';
        }
    }
}

Ta cũng có thể coi thao tác dịch là thao tác xóa ở đầu và thêm vào cuối, và duy trì các đoạn toàn 1 bằng set: [Link code](https://vjudge.net/solution/44018827/E5Xq3sFGLH6TkYCdhbCr).

# Bài B - [Yet Again a Subarray Problem](https://www.codechef.com/problems/SUBPRNJL)

## Tóm tắt đề bài

Cho dãy $A$ có $n$ phần tử.
Với mỗi đoạn con $S=[l, r]$ của dãy:
- dãy $B$ = $m$ lần dãy $S$, với $m = \left \lceil{k / (r - l + 1)}\right \rceil$
- $X$ là phần tử thứ $k$ của $B$ sau khi sort
- $F$ là số lần xuất hiện của $X$ trong $S$
- đoạn $S$ đẹp nếu $F$ xuất hiện trong $S$

Đếm số đoạn con đẹp.

$n, a[i] \leq 2000, k \leq 10^9$

## Lời giải

### Thuật trâu $O(n^3)$:

Ta sẽ làm theo đúng những gì đề bài nói. Phần khó nhất ở đây là tìm được phần tử thứ $k$ của $B$ do $k$ có thể rất lớn. Ta sẽ for $i$ từ 1 đến 2000 và đếm số các số bé $\leq i$ trong $B$ (đếm trong $S$ xong nhân với $m$). $X$ sẽ là $i$ nhỏ nhất mà số đếm $\geq k$.

### Thuật gần chuẩn $O(n^2 * \log^2 n)$:

Thay vì for qua từng số, ta có thể dùng chặt nhị phân để tìm số $i$ đầu tiên có số đếm $\geq k$. Để kiểm tra thì ta có thể duy trì một cây phân đoạn tính tổng (hoặc một cây BIT) để đếm số các số $\leq i$.

(Nếu code BIT thì thuật này sẽ đủ nhanh để AC) [Link code](https://vjudge.net/solution/44017628/FG2EcseyQwwTCBOV6k5L).

### Thuật chuẩn $O(n^2 * \log n)$:

Để bỏ bớt 1 log từ chặt nhị phân, ta có thể dùng một kỹ thuật ["đi trên cây"](https://vnoi.info/wiki/algo/data-structures/segment-tree-extend.md#9-ch%E1%BA%B7t-nh%E1%BB%8B-ph%C3%A2n-tr%C3%AAn-segment-tree).

Ta cần tìm số $i$ nhỏ nhất sao cho (số các số $\leq i$) nhân $m$ $\geq k$.

int Get(int v, int x, int lx, int rx) {
    if (lx == rx) return lx;
    int m = (lx + rx) / 2;
    if (mm * seg[2 * x] >= v) return Get(v, 2 * x, lx, m);
    return Get(v - mm * seg[2 * x], 2 * x + 1, m + 1, rx);
}

Ở một nút, nếu nút bên trái thỏa mãn điều kiện, ta sẽ đi luôn vào nút bên trái. Nếu không thì ta sẽ đi vào nút bên phải và **điều chỉnh lại $k$** (trừ đi phần bên trái).

### Code:

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

const int N = 2005;

int n, k, a[N];
int occ[N];
int seg[4 * N];

void Update(int u, int v, int x, int lx, int rx) {
    if (lx == rx) {
        seg[x] += v;
        return;
    }
    int m = (lx + rx) / 2;
    if (u <= m) Update(u, v, 2 * x, lx, m);
    else Update(u, v, 2 * x + 1, m + 1, rx);
    seg[x] = seg[2 * x] + seg[2 * x + 1];
}

int mm;
int Get(int v, int x, int lx, int rx) {
    if (lx == rx) return lx;
    int m = (lx + rx) / 2;
    if (mm * seg[2 * x] >= v) return Get(v, 2 * x, lx, m);
    return Get(v - mm * seg[2 * x], 2 * x + 1, m + 1, rx);
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    int res = 0;
    for (int l = 1; l <= n; l++) {
        memset(occ, 0, sizeof occ);
        memset(seg, 0, sizeof seg);
        for (int r = l; r <= n; r++) {
            occ[a[r]]++;
            Update(a[r], +1, 1, 1, 2000);
            
            int len = r - l + 1;
            mm = (k + len - 1) / len;
            int ans = Get(k, 1, 1, 2000);
            
            int f = occ[ans];
            res += !!occ[f];
        }
    }   
    
    cout << res << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) solve();
}

# Bài C - [Pishty and Triangles](https://www.codechef.com/problems/PSHTRG)

## Tóm tắt đề bài

Cho dãy $a$ có $n$ phần tử.
Cho $q$ truy vấn 2 loại:
- loại 1: gán $a[pos] = val$
- loại 2: tìm chu vi tam giác lớn nhất sử dụng cạnh từ $a[l]$ đến $a[r]$

$n, q \leq 10^5, a[i] \leq 10^9$

## Lời giải

### Thuật trâu $O(q * n \log n)$:

Với mỗi truy vấn loại 2, ta sẽ sort đoạn $a[l..r]$. Với mỗi 3 phần tử liên tiếp trong đoạn, ta kiểm tra xem tổng 2 số bé có lớn hơn số lớn nhất không (bđt tam giác), và cập nhật đáp án.

### Nhận xét:

Để cho một dãy số không có đáp án, thì $a[i] + a[i + 1] \leq a[i + 2] \forall i$. Trong trường hợp tệ nhất thì sẽ là $a[i] + a[i + 1] = a[i + 2]$. Đây chính là dãy số fibonacci. Do dãy số fibonacci tăng rất nhanh (số thứ 40 của dãy đã $>10^9$), nên với mỗi đoạn $[l, r]$, ta chỉ quan tâm đến khoảng 50 số lớn nhất trong khoảng, vì khi đó chắc chắn sẽ tìm được kết quả.

### Thuật chuẩn $O(q * \log n * 50)$:

Ta sẽ dùng một cây phân đoạn, mỗi nút lưu tối đa 50 phần tử lớn nhất của đoạn, sort từ lớn đến bé. Cây phân đoạn này còn được gọi là merge sort tree vì nó giống thuật toán merge sort :v.

Khi gộp 2 nút của cây lại, ta dùng 2 con trỏ để tránh mất thêm log, trong code sử dụng hàm `merge` có sẵn trong thư viện.
### Code:

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

const int N = 1e5 + 5;
const int LIM = 50;

int n, q;
int a[N];
vector<int> seg[4 * N];

vector<int> operator + (const vector<int>& u, const vector<int>& v) {
    vector<int> w(u.size() + v.size());
    merge(u.begin(), u.end(), v.begin(), v.end(), w.begin(), greater<int>());
    if (w.size() > LIM) w.resize(LIM);
    return w;
}

void Build(int x, int lx, int rx) {
    if (lx == rx) {
        seg[x] = vector<int>(1, a[lx]);
        return;
    }    
    int m = (lx + rx) / 2;
    Build(2 * x, lx, m);
    Build(2 * x + 1, m + 1, rx);
    seg[x] = seg[2 * x] + seg[2 * x + 1];
}

void Update(int pos, int val, int x, int lx, int rx) {
    if (lx == rx) {
        seg[x] = vector<int>(1, val);
        return;
    }
    int m = (lx + rx) / 2;
    if (pos <= m) Update(pos, val, 2 * x, lx, m);
    else Update(pos, val, 2 * x + 1, m + 1, rx);
    seg[x] = seg[2 * x] + seg[2 * x + 1];
}

vector<int> Get(int l, int r, int x, int lx, int rx) {
    if (rx < l || lx > r) return vector<int>();
    if (l <= lx && rx <= r) return seg[x];
    int m = (lx + rx) / 2;
    return Get(l, r, 2 * x, lx, m) + Get(l, r, 2 * x + 1, m + 1, rx);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    Build(1, 1, n);
    
    while (q--) {
        int tt;
        cin >> tt;
        if (tt == 1) {
            int pos, val;
            cin >> pos >> val;
            Update(pos, val, 1, 1, n);
        } else {
            int l, r;
            cin >> l >> r;
            vector<int> tmp = Get(l, r, 1, 1, n);
            
            int sz = tmp.size();            
            int ans = 0;
            for (int i = 0; i + 2 < sz; i++)
                if (tmp[i] < tmp[i + 1] + tmp[i + 2]) {
                    ans = max(ans, tmp[i] + tmp[i + 1] + tmp[i + 2]);
                }
            
            cout << ans << '\n';
        }
    }
}