题解 | #我们惺惺相惜#

题目链接

我们惺惺相惜

思路分析

1. 问题转换

首先，我们需要理解“好区间”的定义：一个区间可以被划分成两个非空的严格单调递增子序列。

这是一个与 Dilworth 定理相关的问题。Dilworth 定理的一个推论是：将一个序列划分为严格单调递增子序列所需的最少数量，等于该序列中最长非递增子序列的长度。一个非递增子序列指的是序列中的元素满足 。

根据这个理论，一个序列可以被划分为至多两个严格单调递增子序列，当且仅当它的最长非递增子序列的长度不超过 2。

如果一个区间的长度至少为 2，并且它可以被划分为至多两个严格单调递增子序列，那么我们总能通过调整使得这两个子序列都非空。因此，核心问题就转化成了：判断一个区间的子序列中，是否存在长度为 3 或更长的非递增子序列。

换句话说，一个区间 是“不好”的，当且仅当在区间内存在三个索引 满足 且 。如果不存在这样的三元组，区间就是“好”的。

2. 高效查询

对于每个查询 ，我们都需要判断上述三元组是否存在。暴力搜索的复杂度是 ，对于多组查询来说太慢了。我们需要一种更高效的预处理或数据结构方法。

我们可以采用一种离线处理的思想，将问题转化为一个动态规划问题。 定义 为最小的右端点 ，使得区间 是一个“不好”的区间。换句话说， 是以大于等于 的索引为起点的所有“不好”三元组 中，最小的那个 。 如果我们能预计算出所有 ，那么对于一个查询 ，我们只需要检查 是否小于等于 即可。如果 ，说明在查询区间 内存在一个“不好”的子区间（即存在一个“不好”的三元组），因此答案是 "NO"；否则是 "YES"。

3. 计算

是所有以 开头的“不好”三元组 中最小的 。这可以表示为：

我们可以从后往前计算 。显然， 应该等于以 为起点的最小坏区间的终点，和 (以 之后为起点的最小坏区间终点) 这两者中的较小值。 其中 是以 为第一个元素的“不好”三元组 中最小的那个 。

可以进一步分解为：

我们可以预先计算出对每个 ，它右边第一个小于等于它的元素的位置，记为 nse[j] (next smaller or equal)。这个数组可以用单调栈在 时间内计算出来。 那么 。

现在的问题是如何为每个 高效地计算这个带条件的最小值 。 当我们从 向 遍历时，我们可以维护一个数据结构，它存储了所有已经处理过的索引 的 nse[j] 值。在计算 时，我们需要查询这个数据结构中，所有满足 的 对应的 nse[j] 的最小值。

这是一个典型的值域查询问题。我们可以使用线段树或树状数组来解决。 由于 的值域很大，我们需要先对 的值进行坐标离散化。然后，我们建立一个线段树，其叶子节点对应离散化后的值。

4. 算法步骤

1. 预处理 nse 数组：使用单调栈，在 时间内计算出每个位置 右侧第一个值小于等于 的元素的索引 nse[i]。
2. 坐标离散化：收集数组 中所有值，去重排序，建立一个从原始值到排名（）的映射。
3. 计算 M 数组： a. 建立一个空的线段树，范围是离散化后值的数量，所有节点值初始化为无穷大。 b. 从 倒序循环至 ： i. 查询线段树中，值域在 内的 nse 最小值。这个结果就是 。 ii. 。（ 初始为无穷大） iii.将 nse[i] 的值更新到线段树中 rank(a[i]) 对应的位置。
4. 处理查询：对于每个查询 （转换为0-based索引），检查是否 。

总的预处理时间复杂度为 ，每个查询的时间复杂度为 。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const int INF = 1e9 + 7;
vector<int> seg_tree;
int seg_size;

void update(int idx, int val, int x, int lx, int rx) {
    if (rx - lx == 1) {
        seg_tree[x] = min(seg_tree[x], val);
        return;
    }
    int m = (lx + rx) / 2;
    if (idx < m) {
        update(idx, val, 2 * x + 1, lx, m);
    } else {
        update(idx, val, 2 * x + 2, m, rx);
    }
    seg_tree[x] = min(seg_tree[2 * x + 1], seg_tree[2 * x + 2]);
}

int query(int l, int r, int x, int lx, int rx) {
    if (lx >= r || l >= rx) return INF;
    if (lx >= l && rx <= r) return seg_tree[x];
    int m = (lx + rx) / 2;
    int left_min = query(l, r, 2 * x + 1, lx, m);
    int right_min = query(l, r, 2 * x + 2, m, rx);
    return min(left_min, right_min);
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<int> sorted_unique_a;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sorted_unique_a.push_back(a[i]);
    }

    sort(sorted_unique_a.begin(), sorted_unique_a.end());
    sorted_unique_a.erase(unique(sorted_unique_a.begin(), sorted_unique_a.end()), sorted_unique_a.end());
    map<int, int> val_to_rank;
    for (int i = 0; i < sorted_unique_a.size(); ++i) {
        val_to_rank[sorted_unique_a[i]] = i;
    }

    vector<int> nse(n, INF);
    vector<int> stack;
    // Correctly find Next Smaller or Equal element's index to the right
    for (int i = n - 1; i >= 0; --i) {
        while (!stack.empty() && a[stack.back()] > a[i]) {
            stack.pop_back();
        }
        if (!stack.empty()) {
            nse[i] = stack.back();
        }
        stack.push_back(i);
    }

    seg_size = sorted_unique_a.size();
    seg_tree.assign(4 * seg_size, INF);
    
    vector<int> M(n + 1, INF);
    for (int i = n - 1; i >= 0; --i) {
        int rank = val_to_rank[a[i]];
        // Find min(nse[j]) for j > i and a[j] <= a[i]
        int R_i = query(0, rank + 1, 0, 0, seg_size);

        M[i] = min(M[i + 1], R_i);
        
        // Update segtree with nse[i] for calculations of indices < i
        update(rank, nse[i], 0, 0, seg_size);
    }

    for (int k = 0; k < q; ++k) {
        int l, r;
        cin >> l >> r;
        --l; --r;
        if (M[l] <= r) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static int[] segTree;
    static int segSize;
    static final int INF = Integer.MAX_VALUE;

    static void build(int size) {
        segSize = size;
        segTree = new int[4 * segSize];
        Arrays.fill(segTree, INF);
    }

    static void update(int idx, int val, int x, int lx, int rx) {
        if (rx - lx == 1) {
            segTree[x] = Math.min(segTree[x], val);
            return;
        }
        int m = (lx + rx) / 2;
        if (idx < m) {
            update(idx, val, 2 * x + 1, lx, m);
        } else {
            update(idx, val, 2 * x + 2, m, rx);
        }
        segTree[x] = Math.min(segTree[2 * x + 1], segTree[2 * x + 2]);
    }

    static int query(int l, int r, int x, int lx, int rx) {
        if (lx >= r || l >= rx) return INF;
        if (lx >= l && rx <= r) return segTree[x];
        int m = (lx + rx) / 2;
        int leftMin = query(l, r, 2 * x + 1, lx, m);
        int rightMin = query(l, r, 2 * x + 2, m, rx);
        return Math.min(leftMin, rightMin);
    }

    public static void solve(FastReader sc) throws IOException {
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] a = new int[n];
        TreeSet<Integer> uniqueVals = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            uniqueVals.add(a[i]);
        }

        Map<Integer, Integer> valToRank = new HashMap<>();
        int rankCounter = 0;
        for (int val : uniqueVals) {
            valToRank.put(val, rankCounter++);
        }

        int[] nse = new int[n];
        Arrays.fill(nse, INF);
        Deque<Integer> stack = new ArrayDeque<>();
        // Correctly find Next Smaller or Equal element's index to the right
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && a[stack.peek()] > a[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                nse[i] = stack.peek();
            }
            stack.push(i);
        }

        build(uniqueVals.size());
        int[] M = new int[n + 1];
        Arrays.fill(M, INF);

        for (int i = n - 1; i >= 0; i--) {
            int rank = valToRank.get(a[i]);
            int R_i = query(0, rank + 1, 0, 0, segSize);

            M[i] = Math.min(M[i + 1], R_i);

            update(rank, nse[i], 0, 0, segSize);
        }

        PrintWriter out = new PrintWriter(System.out);
        for (int k = 0; k < q; k++) {
            int l = sc.nextInt() - 1;
            int r = sc.nextInt() - 1;
            if (M[l] <= r) {
                out.println("NO");
            } else {
                out.println("YES");
            }
        }
        out.flush();
    }

    public static void main(String[] args) throws IOException {
        FastReader sc = new FastReader();
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
    
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){br=new BufferedReader(new InputStreamReader(System.in));}
        String next(){while(st==null||!st.hasMoreElements()){try{st=new StringTokenizer(br.readLine());}catch(IOException e){e.printStackTrace();}}return st.nextToken();}
        int nextInt(){return Integer.parseInt(next());}
    }
}

import sys

def solve():
    try:
        n_q_line = sys.stdin.readline()
        if not n_q_line: return
        n, q = map(int, n_q_line.split())
        a = list(map(int, sys.stdin.readline().split()))
        queries = []
        for _ in range(q):
            queries.append(list(map(int, sys.stdin.readline().split())))
    except (IOError, ValueError):
        return
    
    unique_vals = sorted(list(set(a)))
    val_to_rank = {val: i for i, val in enumerate(unique_vals)}
    
    # next smaller or equal element to the right
    nse = [float('inf')] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and a[stack[-1]] > a[i]:
            stack.pop()
        if stack:
            nse[i] = stack[-1]
        stack.append(i)
        
    seg_size = len(unique_vals)
    seg_tree = [float('inf')] * (4 * seg_size)

    def update(idx, val, x=0, lx=0, rx=seg_size):
        if rx - lx == 1:
            seg_tree[x] = min(seg_tree[x], val)
            return
        m = (lx + rx) // 2
        if idx < m:
            update(idx, val, 2 * x + 1, lx, m)
        else:
            update(idx, val, 2 * x + 2, m, rx)
        seg_tree[x] = min(seg_tree[2 * x + 1], seg_tree[2 * x + 2])

    def query(l, r, x=0, lx=0, rx=seg_size):
        if lx >= r or l >= rx:
            return float('inf')
        if lx >= l and rx <= r:
            return seg_tree[x]
        m = (lx + rx) // 2
        left_min = query(l, r, 2 * x + 1, lx, m)
        right_min = query(l, r, 2 * x + 2, m, rx)
        return min(left_min, right_min)

    M = [float('inf')] * (n + 1)
    for i in range(n - 1, -1, -1):
        rank = val_to_rank[a[i]]
        
        # Query for min(nse[j]) for j > i and a[j] <= a[i]
        R_i = query(0, rank + 1)
        M[i] = min(M[i + 1], R_i)
        
        # Add nse[i] to the structure for future calculations
        update(rank, nse[i])

    for l, r in queries:
        l -= 1
        r -= 1
        if M[l] <= r:
            print("NO")
        else:
            print("YES")

def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()