Subtask 1, 2:

Gọi ~dp_0(i)~ và ~dp_1(i)~ lần lượt là dãy con dài nhất thỏa mãn yêu cầu đề bài sao cho dãy này kết thúc tại một đỉnh hướng lên / đỉnh hướng xuống.

Dễ thấy ~dp_0(i) = max(dp_1(j)) + 1~, ~dp_1(i) = max(dp_0(j)) + 1~ trong đó: ~(j < i)~.

Độ phức tạp: ~O(n^2 \times q)~.

Subtask 3:

Ta cải tiến từ subtask 1 và 2 bằng cách duy trì ~max(dp_0(j))~ và ~max(dp_1(j))~ bằng các CTDL có khả năng truy vấn max nhanh như BIT hoặc IT.

Độ phức tạp: ~O(n \times q)~.

Subtask 4:

Do chiều cao chỉ có hai giá trị là ~1~ và ~2~, ta có thể nghĩ đến việc duy trì dp cho từng đoạn bằng cách quản lý bằng một node trên segment tree.

Gọi ~dp(i, j)~ là độ dài dãy con dài nhất thỏa mãn yêu cầu đề bài sao cho dãy bắt đầu bằng giá trị ~i~ và kết thúc bằng giá trị ~j~ (có thể xem ~1, 2~ như ~0, 1~ để tiện code).

Subtask 5:

Nhận xét: Với một dãy con phân biệt, chỉ cần quan tâm phần tử đầu, phần tử cuối và các cực trị cục bộ.

Code tham khảo:

• Code subtask 1 - 4: https://ideone.com/PoVhxX

• Code full: https://ideone.com/ShEEPr

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define bit(x, i) ((x >> i) & 1)
#define SZ(x) ((int)(x.size()))
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define task "climbing"

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }

const int MXN = 2e5 + 5;
const int MOD = 1e9 + 7;
const int BASE = 3137;
const int BL = 320;

int n, m, q, a[MXN], b[MXN], top[MXN], bot[MXN], ql[MXN], qr[MXN], pos[MXN];

namespace sub1 {
    void solve() {
        FOR(i, 1, q) {
            int cnt = 0, ans = 1;
            FOR(j, ql[i] + 1, qr[i]) {
                if (cnt % 2 == 0 && a[j] > a[j - 1]) cnt++;
                if (cnt % 2 != 0 && a[j] < a[j - 1]) cnt++;
                if (cnt % 2 == 0) ans = max(ans, cnt + 1);
            }
            cout << ans << "\n";
        }
    }
}

bool istop(int id) {
    return (b[id] > b[id - 1] || id == 1) && (b[id] > b[id + 1] || id == m);
}

bool isbot(int id) {
    return (b[id] < b[id - 1] || id == 1) && (b[id] < b[id + 1] || id == m);
}

namespace sub2 {
    void solve() {
        FOR(i, 1, q) {
            int l = ql[i], r = qr[i];
            while (l < r && a[l] == a[l + 1]) l++;
            while (r > l && a[r] == a[r - 1]) r--;
            while (l < r && a[l] > a[l + 1]) l++;
            while (r > l && a[r] > a[r - 1]) r--;
            while (l < r && a[l] == a[l + 1]) l++;
            while (r > l && a[r] == a[r - 1]) r--;
            if (l + 1 >= r) {
                cout << 1 << "\n";
                continue;
            }
            int l2 = pos[l], r2 = pos[r];
            int ans = top[r2-1]-top[l2]+bot[r2-1]-bot[l2]+(a[l]<a[l+1])+(a[r]<a[r-1]);
            if (ans % 2 == 0) ans--;
            cout << ans << "\n";
        }
    }
}

void solve() {
    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i];
    int m = 0;
    FOR(i, 1, n) {
        b[++m] = a[i];
        int j = i;
        while (j <= n && a[j] == a[i]) pos[j] = m, j++;
        i = j - 1;
    }
    FOR(i, 1, m) {
        top[i] = top[i - 1] + istop(i);
        bot[i] = bot[i - 1] + isbot(i);
    }
    FOR(i, 1, q) cin >> ql[i] >> qr[i];
    sub2::solve();
}

int32_t main() {
    if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
    ios::sync_with_stdio(0); cin.tie(0);
    int ntest = 1; //cin >> ntest;
    while (ntest--) solve();
    cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}