Truy vấn $$$t = 1$$$, bạn có thể sử dụng hàm binary_search trả về kiểu dữ liệu bool có sẵn trong thư viện.

Truy vấn $$$t = 2$$$, bạn có thể sử dụng hàm lower_bound trả về luôn vị trí cần tìm.

Truy vấn $$$t = 3$$$, bạn có thể sử dụng hàm upper_bound trả về vị trí ngay sau vị trí cần tìm.

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

#define el '\n'
#define mxn 100005

int n, q, a[mxn];
 
void solve(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    while(q--){
        int t, x; cin >> t >> x;
        if(t == 1){
            bool ok = 0;
            int l = 0, r = n + 1;
            while(r - l > 1){
                int mid = l + r >> 1;
                if(a[mid] == x){
                    ok = 1; break;
                }
                if(a[mid] < x) l = mid;
                else r = mid;
            }
            cout << (ok ? "YES\n" : "-1\n");
        }else if(t == 2){
            int l = 0, r = n + 1;
            while(r - l > 1){
                int mid = l + r >> 1;
                if(a[mid] >= x) r = mid;
                else l = mid;
            }
            if(r <= n and a[r] == x) cout << r << el;
            else cout << "-1\n";
        }else{
            int l = 0, r = n + 1;
            while(r - l > 1){
                int mid = l + r >> 1;
                if(a[mid] <= x) l = mid;
                else r = mid;
            }
            if(l >= 1 and a[l] == x) cout << l << el;
            else cout << "-1\n";
        }
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta sẽ duy trì $$$2$$$ con trỏ $$$i, j$$$ chạy từ đầu mảng $$$a$$$ và $$$b$$$, nếu $$$a_i \le b_j$$$ thì ta sẽ đưa phần tử $$$a_i$$$ vào cuối mảng $$$c$$$ và thêm ký tự a vào xâu truy vết, ngược lại thì ta sẽ đưa phần tử $$$b_j$$$ và thêm ký tự b.

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

#define el '\n'
#define mxn 1000005

int n, m, a[mxn], b[mxn];
vector<int> c;
 
void solve(){
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    cin >> m;
    for(int i=0; i<m; i++) cin >> b[i];
    string s = "";
    int i = 0, j = 0;
    while(i < n and j < m){
        if(a[i] <= b[j]){
            c.push_back(a[i++]);
            s.push_back('a');
        }else{
            c.push_back(b[j++]);
            s.push_back('b');
        }
    }
    while(i < n) c.push_back(a[i++]), s.push_back('a');
    while(j < m) c.push_back(b[j++]), s.push_back('b');
    for(int &i : c) cout << i << ' ';
    cout << el << s;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Với mỗi giá trị $$$b_i (1 \le i \le m)$$$, ta sẽ cần tìm vị trí $$$j$$$ cuối cùng trong mảng $$$a$$$ sao cho $$$a_j < b_i$$$, bởi vì như vậy, các số từ $$$1$$$ đến $$$j$$$ sẽ đều thoả mãn nhỏ hơn $$$b_i$$$. Tuy nhiên, ta có thể sẻ dụng hàm lower_bound có sẵn trong thư viện, trả về vị trí $$$j$$$ đầu tiên mà $$$a_j \geq b_i$$$, suy ra là nếu ta lùi về $$$1$$$ đơn vị thì ta cũng ra được vị trí cần tìm.

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

void solve(){
    int n, m; cin >> n >> m;
    int a[n+5], b[m+5];
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    for(int i=1; i<=m; i++){
        cin >> b[i];
    }
    for(int i=1; i<=m; i++){
        int l = 0, r = n + 1;
        while(r - l > 1){
            int mid = l + r >> 1;
            if(a[mid] < b[i]) l = mid;
            else r = mid;
        }
        cout << l << ' ';
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Xét từng vị trí $$$i$$$ trong mảng $$$a$$$ $$$(1 \le i \le n)$$$, ta sẽ cần đi tìm vị trí $$$j$$$ đầu tiên mà $$$a_i = b_j$$$ và một vị trí $$$k$$$ đầu tiên sao cho $$$a_i > b_k$$$. Như vậy, kết quả sẽ được tăng thêm một lượng bằng độ dài đoạn $$$[j, j + 1, ..., k - 1]$$$.

Tuy nhiên, ta hoàn toàn có thể áp dụng hàm có sẵn bằng việc tìm vị trí $$$j$$$ bằng lower_bound và vị trí $$$k$$$ bằng upper_bound.

Một cách xử lý khác nghe có vẻ đơn giản hơn đó chính là sử dụng $$$map$$$ để đếm số lượng các giá trị. Tuy nhiên, do độ phức tạp của $$$map$$$ có thêm một hằng số $$$c$$$ có giá trị nào đó mà không phải là độ phức tạo $$$O(log(n))$$$ của tìm kiếm nhị phân nên có thể sẽ bị TLE trong một vài trường hợp đặc biệt.

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

#define mxn 1000005

int n, m, a[mxn], b[mxn];
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    for(int i=1; i<=m; i++){
        cin >> b[i];
    }
    long long res = 0;
    for(int i=1; i<=m; i++){
        int l = lower_bound(a+1, a+n+1, b[i]) - a;
        int r = upper_bound(a+1, a+n+1, b[i]) - a;
        res += r - l;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta sẽ duyệt mọi vị trí bắt đầu, ta sẽ gọi là $$$i (1 \le i \le n)$$$, như vậy ta sẽ cần tìm vị trí $$$j$$$ cuối cùng sao cho $$$a_i + a_{i + 1} + ... + a_j \le s$$$. Ta có thể rút ra nhận xét ở đây là ta sẽ cần sử dụng mảng cộng dồn để tính tổng tĩnh một cách nhanh chóng và mảng cộng dồn cũng thoả mãn tính chất tăng dần (đồng biến) để ta có thể tìm kiếm nhị phân.

Cụ thể hơn, ta sẽ có biểu thức sau đây: $$$pre[j] - pre[i - 1] \le s \to pre[j] \le pre[i - 1] + s$$$. Như vậy, ta sẽ tìm vị trí $$$j$$$ đầu tiên có $$$pre[j] > pre[i - 1] + s$$$ bằng upper_bound rồi sau đó lùi về $$$1$$$ đơn vị.

Hoặc ta cũng có thể sử dụng $$$2$$$ con trỏ để giải quyết. Duy trì con trỏ $$$r$$$ duyệt qua mảng, con trỏ $$$l$$$ được tuỳ chỉnh theo trạng thái dãy con $$$[l, r]$$$ hiện tại và một tổng $$$sum$$$ lưu tổng các phần tử trong đoạn $$$[l, r]$$$. Ngay khi tổng $$$sum$$$ vượt quá $$$s$$$, ta sẽ dịch con trỏ $$$l$$$ lên dần dần, tổng $$$sum$$$ trừ dần đi các $$$a_l$$$ đã bỏ qua, rồi sau đó khi tổng trở về $$$\le s$$$ thì ta sẽ cập nhật kết quả.

Hướng giải quyết thì ta sẽ tư duy giống như bài $$$E$$$ ở phía trên, chỉ khác ở chỗ kết quả sẽ được cập nhật bằng độ dài đoạn $$$[i, i + 1, ..., j]$$$ do $$$j$$$ là vị trí cuối cùng thoả mãn, nên các vị trí đằng trước đương nhiên cũng thoả mãn.

Ta sẽ duyệt mọi vị trí bắt đầu, ta sẽ gọi là $$$i (1 \le i \le n)$$$, như vậy ta sẽ cần tìm vị trí $$$j$$$ đầu tiên sao cho $$$a_i + a_{i + 1} + ... + a_j \geq s$$$. Ta có thể rút ra nhận xét ở đây là ta sẽ cần sử dụng mảng cộng dồn để tính tổng tĩnh một cách nhanh chóng và mảng cộng dồn cũng thoả mãn tính chất tăng dần (đồng biến) để ta có thể tìm kiếm nhị phân.

Cụ thể hơn, ta sẽ có biểu thức sau đây: $$$pre[j] - pre[i - 1] \geq s \to pre[j] \geq pre[i - 1] + s$$$. Như vậy, ta sẽ tìm vị trí $$$j$$$ đó bằng lower_bound rồi sau đó cập nhật kết quả.

Hoặc ta cũng có thể sử dụng $$$2$$$ con trỏ để giải quyết. Duy trì con trỏ $$$r$$$ duyệt qua mảng, con trỏ $$$l$$$ được tuỳ chỉnh theo trạng thái dãy con $$$[l, r]$$$ hiện tại và một tổng $$$sum$$$ lưu tổng các phần tử trong đoạn $$$[l, r]$$$. Chừng nào ta còn có thể dịch cận $$$l$$$ lên thêm $$$1$$$ đơn vị, tức là $$$sum - a_l \geq s$$$ thì ta sẽ tiếp tục dịch để giảm độ dài đoạn con.

Hướng giải quyết thì ta sẽ tư duy giống như bài $$$G$$$ ở phía trên, chỉ khác ở chỗ kết quả sẽ được cập nhật bằng độ dài đoạn $$$[1, i - 1]$$$ do $$$[i, j]$$$ là đoạn ngắn nhất ta tìm được, vậy nên khi thêm các phần tử vào thì $$$sum$$$ vẫn $$$\geq s$$$.

Ta sẽ sử dụng $$$2$$$ con trỏ để giải quyết, con trỏ $$$r$$$ sẽ duyệt từ đầu đến cuối cùng với đó là tăng số lần xuất hiện của $$$a_r$$$ lên $$$1$$$ đơn vị, nếu số lần xuất hiện là $$$1$$$ thì đây là lần $$$a_r$$$ xuất hiện đầu tiên và như vậy ta sẽ phải tăng số lượng phần tử khác nhau lên $$$1$$$ đơn vị.

Ngay khi số lượng phần tử khác nhau vượt quá $$$k$$$ thì ta sẽ loại bỏ dần các phần tử $$$a_l$$$, giảm số lần xuất hiện nếu trở về $$$0$$$ thì giảm số phần tử khác nhau đi $$$1$$$ đơn vị. Cuối cùng, ta sẽ có đoạn $$$[l, r]$$$ thoả mãn yêu cầu đề bài để cập nhật kết quả.

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, k, a[mxn], d[mxn];

void solve(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    int res = 0, cnt = 0, l = 1;
    for(int r=1; r<=n; r++){
        ++d[a[r]];
        if(d[a[r]] == 1) ++cnt;
        while(cnt > k){
            --d[a[l]];
            if(d[a[l]] == 0) --cnt;
            ++l;
        }
        res += r - l + 1;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta vẫn sẽ dùng $$$2$$$ con trỏ để giải quyết bài toán, tuy nhiên ở đây để lưu trạng thái đoạn con $$$[l, r]$$$ đang xét thì ta sẽ cần sử dụng đến multiset. Lí do chính là vì nó sẽ giúp chúng ta lấy ra được giá trị $$$min$$$ và $$$max$$$ một cách dễ dàng, rồi sau đó kiểm tra xem hiệu giữa chúng có thoả mãn hay không.

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e5 + 7;

int n, k, a[mxn];
multiset<int> ms;

void solve(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    int res = 0, l = 1;
    for(int r=1; r<=n; r++){
        ms.insert(a[r]);
        while((*ms.rbegin()) - (*ms.begin()) > k){
            ms.erase(ms.find(a[l]));
            ++l;
        }
        res += r - l + 1;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define int long long
#define mxn 200005

int n, q, a[mxn], f[mxn];
 
void solve(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1, greater<int>());
    for(int i=1; i<=n; i++){
        f[i] = f[i - 1] + a[i];
    }
    while(q--){
        int x; cin >> x;
        int l = 0, r = n + 1;
        while(r - l > 1){
            int mid = l + r >> 1;
            if(f[mid] >= x) r = mid;
            else l = mid;
        }
        cout << (r <= n ? r : -1) << ' ';
    }
    cout << '\n';
}

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

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

#define int long long
#define mxn 200005

int n, m, a[mxn];
bool check(int x){
    int s = 0;
    for(int i=1; i<=n; i++){
        s += x / a[i];
        if(s >= m) return 1;
    }return 0;
}
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    int l = 0, r = 1e18;
    while(r - l > 1){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << r;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define int long long

int a, b, n, c;
int gcd(int a, int b){
    while(b){
        a %= b; swap(a, b);
    }return a;
}
 
bool check(int x){
    return (x / a) + (x / b) - (x / c) >= n;
}
 
void solve(){
    cin >> a >> b >> n;
    c = a / gcd(a, b) * b;
    int l = min(a, b) - 1, r = 1e18 + 1;
    while(r - l > 1){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << r << '\n';
}

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

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

#define int long long

int odd(int l, int r){
    if(l % 2 == 0) ++l;
    if(r % 2 == 0) --r;
    return (r + l) * ((r - l) / 2 + 1) / 2;
}
 
int even(int l, int r){
    if(l % 2 == 1) ++l;
    if(r % 2 == 1) --r;
    return (r + l) * ((r - l) / 2 + 1) / 2;
}
 
void solve(){
    int n; cin >> n;
    int l = 0, r = n;
    while(r - l > 1){
        int mid = l + r >> 1;
        if(odd(1, mid) > even(mid + 1, n)) r = mid;
        else l = mid;
    }
    cout << r << '\n';
}

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

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

#define int long long
#define mxn 100005

int n, m, a[mxn];
bool check(int x){
    int cnt = 1, id = 1;
    for(int i=2; i<=n; i++){
        if(a[i] - a[id] >= x){
            ++cnt; if(cnt == m) return 1;
            id = i;
        }
    }return 0;
}
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    int l = 0, r = 1e9 + 1;
    while(r - l > 1){
        int mid = l + r >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << l;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}