Bài này khá khó, mình mong nhận được hướng giải và code ( C++ ) full được test. Mình sẽ vote 5 sao. Dòng đầu tiên cho hai số N và Q. Dòng tiếp theo cho N số nguyên . Q dòng tiếp theo, mỗi dòng là một số t , yêu cầu trả lời câu hỏi : " Đếm số lượng dãy liên tiếp trong N số nguyên thoả mãn các phần tử của dãy đó đều lớn hơn t. " Giới hạn : N, Q <= 1e5. Các số nguyên trong mảng N số nguyên đều <= 10^9, các số t đều <= 10^9. Test mẫu : inp : 5 3 1 3 4 2 3 1 2 3 out : 1 2 1 Giới hạn thời gian : 1s .

Thuật toán

Ta sẽ xử lý từng truy vấn theo thứ tự từ bé đến lớn của $t$. Lý do ta làm như vậy bởi lúc này ta chỉ cần xử lý việc loại bỏ các phần tử không thỏa mãn và đếm số dãy liên tiếp.

Ta sẽ lưu các dãy con liên tiếp đang có sau truy vấn thứ $i$ vào một CTDL set. Ban đầu, chỉ có một dãy duy nhất là $a_1, a_2, \ldots, a_n$. Sau mỗi truy vấn, ta sẽ sử dụng kỹ thuật hai con trỏ (trên dãy $a$ sau khi đã sắp xếp) để xóa đi các phần tử không thỏa mãn, đồng thời tính lại số đoạn con.

Vậy làm thế nào để làm việc này một cách nhanh chóng?

Gọi số ta cần xóa là $x$ và nằm ở vị trí thứ $y$ trong dãy ban đầu. Nhờ CTDL set, ta có thể tìm được dãy con liên tiếp $a_l, a_{l+1}, \ldots, a_r$ sao cho $x$ thuộc dãy trên trong thời gian $O(\text{log } N)$.

Ta sẽ tiến hành xóa dãy con $[l,r]$ trong set và thêm vào hai dãy mới là $[l, y-1]$ và $[y+1, r]$. Nếu một trong hai dãy này rỗng, ta sẽ không thêm nó vào nữa. Các thao tác trên cũng mất thời gian $O(\text{log } N)$

Sau khi xóa đủ số phần tử cho truy vấn, đáp án của chúng ta sẽ là kích thước của set lưu các dãy liên tiếp. Tổng độ phức tạp của thuật toán này của chúng ta sẽ là $O(n \text{ log } n + q (\text{log } q + \text{ log }n))$ ($\text{log } q$ phát sinh từ chi phí sắp xếp truy vấn)

Code (C++)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

int n,q,cur,ans[maxn];
pair<int,int> a[maxn],t[maxn], val;
set<pair<int,int>> S;
set<pair<int,int>>::iterator it;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for(int i=1;i<=n;i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a+1,a+n+1);
    a[n+1] = make_pair(INT_MAX, -1);
    for(int i=1;i<=q;i++){
        cin >> t[i].first;
        t[i].second = i;
    }
    sort(t+1,t+q+1);
    cur = 1;
    // De su dung lower_bound hon neu de r = pair.first
    S.insert(make_pair(n,1));
    for(int i=1;i<=q;i++){
        while(a[cur].first <= t[i].first){
            it = S.lower_bound(make_pair(a[cur].second, -1));
            val = (*it);
            S.erase(it);
            if(a[cur].second < val.first){
                S.insert(make_pair(val.first, a[cur].second+1));
            }
            if(a[cur].second > val.second){
                S.insert(make_pair(a[cur].second-1, val.second));
            }
            cur++;
        }
        ans[t[i].second] = S.size();
    }
    for(int i=1;i<=q;i++) cout << ans[i] << '\n';
}