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';
}