核心分析

1. 涂白规则本质：

   • 第 ( 1 ) 步任选一块石头涂白（起点）。
   • 后续每步必须从“相邻已有白色石头”的黑色石头中，选 $( a_j )$ 最小的涂白。
   • 因 $( a_i )$ 是排列（所有值唯一），后续每步的选择是唯一确定的，仅起点（第一步）影响最终涂白顺序。

2. 关键观察：

   • 石头的涂白顺序由 $( a_i )$ 大小决定，$( a_i )$ 越小的石头，越先被涂白（除起点外）。
   • 定义 $( s[x] )$ 为 $( a_i = x )$ 的石头编号（因 ( a ) 是排列，( s ) 是 ( a ) 的逆映射）。
   • 涂白过程可看作：以起点为初始白色区域，按 ( x ) 从 ( 1 ) 到 ( n ) 的顺序（除起点对应的 ( x ) 外），将 ( s[x] ) 加入白色区域（若 ( s[x] ) 相邻已有白色）。

3. 目标与转化：

   • 对于查询 ( (p, k) )，需统计起点 ( t ) 的数量，使得 ( p ) 恰好在第 ( k ) 步被涂白。
   • 分两种情况：
     • 若 ( k=1 )：仅当 ( t=p ) 时满足，答案为 ( 1 )（若查询 ( k=1 ) 且 ( p ) 合法）或 ( 0 )。
     • 若 $( k>1 )$：( p ) 不是起点，其涂白步骤 ( k ) 等于“在 ( p ) 被涂白前，已涂白的石头数量 + 1”。需通过并查集维护连通区域，计算合法起点区间。

核心步骤

1. 预处理逆映射与排序

• 构建逆映射 $( s[x] = i )$（其中 $( a_i = x )$），即 ( x ) 对应石头编号。
• 按 ( x ) 从小到大排序（除起点外，涂白顺序固定为 $( x=1,2,...,n )$）。

2. 并查集维护连通区域

• 用并查集记录白色连通区域的左右边界（$( l[root] )$ 为左端点，$( r[root] )$ 为右端点）。
• 初始时，所有石头独立；当 $( s[x] )$ 相邻有白色区域时，合并连通块，并更新边界。

3. 计算每个石头的涂白条件

• 对于石头 ( p )，设其 $( a_p = val )$（即 $( x=val )$）。
• ( p ) 被涂白的步骤 ( k ) 满足：$( k = cnt + 1 )$，其中 $( cnt )$ 是“在 $( x=val )$ 被处理前，已连通的石头数量”。
• 合法起点 ( t ) 必须在 ( p ) 被涂白前的连通区域内，且该连通区域在 $( x=val )$ 处理时恰好包含 ( p )。

4. 离线处理查询

• 所有查询按 ( p ) 分组，结合并查集维护的区间信息，计算每个查询对应的合法起点数量（区间长度）。

复杂度分析

• 时间复杂度$( O(n \alpha(n) + q) )$，其中 $( \alpha(n) )$ 是并查集的阿克曼函数反函数（近似常数），适配 $( n,q \leq 10^5 )$。
• 空间复杂度：$( O(n + q) )$，用于存储逆映射、并查集信息和查询。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

const int MAX_N = 1e5 + 10;
const int MOD = 1e9 + 7;

int a[MAX_N];
int s[MAX_N]; // s[x] = i 表示 a[i] = x（逆映射）
int parent[MAX_N];
int l[MAX_N], r[MAX_N]; // 并查集连通块的左右边界
int size[MAX_N]; // 连通块大小
vector<pair<int, int>> queries[MAX_N]; // queries[p] 存储 (k, idx)
int ans[MAX_N];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    parent[ry] = rx;
    l[rx] = min(l[rx], l[ry]);
    r[rx] = max(r[rx], r[ry]);
    size[rx] += size[ry];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[a[i]] = i; // 构建逆映射
    }

    // 初始化并查集
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        l[i] = r[i] = i;
        size[i] = 1;
    }

    // 读取查询，按 p 分组
    for (int idx = 0; idx < q; ++idx) {
        int p, k;
        cin >> p >> k;
        queries[p].emplace_back(k, idx);
    }

    // 预处理每个石头 p 的涂白步骤相关信息
    vector<bool> used(n + 1, false);
    unordered_map<int, int> cnt_map; // 记录连通块大小对应的步骤贡献

    // 先处理 k=1 的查询（仅起点为 p 时满足）
    for (int p = 1; p <= n; ++p) {
        for (auto &[k, idx] : queries[p]) {
            if (k == 1) {
                ans[idx] = 1;
            }
        }
    }

    // 按 x 从小到大处理（x 是 a[i] 的值，即涂白优先级）
    for (int x = 1; x <= n; ++x) {
        int p = s[x]; // 当前要处理的石头编号
        used[p] = true;

        // 合并左右相邻的已使用石头
        if (p > 1 && used[p - 1]) {
            merge(p, p - 1);
        }
        if (p < n && used[p + 1]) {
            merge(p, p + 1);
        }

        int root = find(p);
        int current_size = size[root];
        int step = current_size; // 此时 p 被涂白的步骤为 current_size（因起点占 1 步，后续合并的每块占 1 步）

        // 处理当前 p 的查询（k > 1 的情况）
        for (auto &[k, idx] : queries[p]) {
            if (k != 1) {
                if (k == step) {
                    ans[idx] = current_size; // 合法起点是当前连通块的所有石头
                } else {
                    ans[idx] = 0;
                }
            }
        }
    }

    // 输出答案
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}

关键细节

1. 逆映射的作用：将 $( a_i )$ 的值与石头编号关联，方便按 $( a_i )$ 从小到大处理涂白顺序。
2. 并查集的边界维护：通过记录连通块的左右边界和大小，快速计算合法起点的区间长度。
3. 查询离线处理：按 ( p ) 分组查询，在处理对应石头时直接计算答案，避免重复遍历。
4. 步骤计算逻辑：连通块大小即为当前已涂白的石头数量，对应涂白步骤（起点占 1 步，后续每合并一块加 1 步）。