Subtask 1+2

Có nhiều cách làm, một cách là: với mỗi truy vấn có thể dùng mảng đếm để đánh dấu những phần tử có trong đoạn, từ đó xét xem nó có phải là đoạn gồm các số liên tiếp hay không.

Một cách khác như sau:

Nhận xét: Một đoạn con là đoạn gồm những số liên tiếp khi và chỉ khi giá trị lớn nhất trừ giá trị nhỏ nhất bằng đúng độ dài của nó.

Vì vậy, có một cách trâu khác là tìm giá trị lớn nhất và giá trị nhỏ nhất trong đoạn rồi kiểm tra điều kiện giá trị lớn nhất trừ giá trị nhỏ nhất bằng đúng độ dài của nó có đúng hay không.

Subtask 3

Dựa vào cách thứ hai được nêu trong subtask trước, ta cần một thuật toán / cấu trúc dữ liệu để có thể tìm giá trị lớn nhất (nhỏ nhất) của 1 đoạn trong ~O(log~ ~n)~ hoặc ~O(1)~. Có nhiều cách để làm điều này, chẳng hạn như dùng Segment Tree, Binary Indexed Tree (BIT), hay Sparse Table.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)1e5+228;
const int logn = 17;

int n, p[N], q;
int minValue[N][logn+1], maxValue[N][logn+1];

int getMinValue(int l, int r)
{
    int k = log2(r-l+1);
    return min(minValue[l][k], minValue[r-MASK(k)+1][k]);
}

int getMaxValue(int l, int r)
{
    int k = log2(r-l+1);
    return max(maxValue[l][k], maxValue[r-MASK(k)+1][k]);
}

void solve()
{
    cin >> n >> q;
    for(int i=1; i<=n; ++i) cin >> p[i];

    for(int i=1; i<=n; ++i)
    {
        minValue[i][0] = maxValue[i][0] = p[i];
    }
    for(int j=1; MASK(j) <= n; ++j)
    {
        for(int i=1; i+MASK(j)-1 <= n; ++i)
        {
            minValue[i][j] = min(minValue[i][j-1], minValue[i+MASK(j-1)][j-1]);
            maxValue[i][j] = max(maxValue[i][j-1], maxValue[i+MASK(j-1)][j-1]);
        }
    }

    while(q--)
    {
        int l, r; 
        cin >> l >> r;
        int mi = getMinValue(l, r);
        int ma = getMaxValue(l, r);
        // cout << mi << " " << ma << '\n';
        if(ma - mi + 1 == r - l + 1) cout << "YES\n";
        else cout << "NO\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    solve();
    return 0;
}