思路：单调栈+ST表/线段树

显然，对于先手仅能选取$[l,r]$中最大的数，因此我们需要知道该区间的最大值，可以用ST表/线段树等数据结构进行预处理，同时我们处理出最大值所在的位置，额外用数组记录即可。

而对于后手，要求$[L,R]$最小且要赢，说明要找到两边区间内大于$[l,r]$中最大值且距离最近的位置。可以使用单调栈来预处理。

对于$a_i$右边的最大值，我们维护一个单调递减栈，从左往右枚举，当栈头出栈时，当前数即为栈头右侧第一个比它大的数的位置，记录即可。

对于左侧同理。

找到左右两侧更大的数（或者找不到就是输），比较位置远近即可。

代码

C++

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>

using namespace std;

// 定义全局变量
int n, k; // 数组长度和查询次数
vector<int> elements, log_values; // 元素数组和log值数组
vector<vector<int>> sparse_table; // 稀疏表
vector<int> left_greater_indices, right_greater_indices; // 每个元素左边和右边第一个比它大的元素的索引

// 构建log值数组
void buildLogValues() {
    for (int i = 2; i <= n; i++) {
        log_values[i] = log_values[i / 2] + 1; // 通过前一个元素的log值计算当前元素的log值
    }
}

// 构建稀疏表
void buildSparseTable() {
    for (int i = 0; i < n; i++) {
        sparse_table[i][0] = i; // 初始化稀疏表的第一列为元素的索引
    }

    int j = 1;
    while ((1 << j) <= n) { // 根据区间长度迭代稀疏表的列
        for (int i = 0; i <= n - (1 << j); i++) {
            int left_index = sparse_table[i][j - 1]; // 左区间的最大值索引
            int right_index = sparse_table[i + (1 << (j - 1))][j - 1]; // 右区间的最大值索引
            sparse_table[i][j] = (elements[left_index] >= elements[right_index]) ? left_index : right_index; // 将较大值的索引存入稀疏表
        }
        j++;
    }
}

// 在区间[left, right]中找到最大值的索引
int findMaxIndex(int left, int right) {
    int span = log_values[right - left + 1]; // 计算区间长度的log值
    int left_index = sparse_table[left][span]; // 左区间的最大值索引
    int right_index = sparse_table[right - (1 << span) + 1][span]; // 右区间的最大值索引
    return (elements[left_index] >= elements[right_index]) ? left_index : right_index; // 返回较大值的索引
}

// 计算每个元素左边和右边第一个大于它的元素的索引
void calculateGreaterIndices() {
    right_greater_indices.assign(n, -1); // 初始化右侧第一个大于元素的索引数组
    left_greater_indices.assign(n, -1); // 初始化左侧第一个大于元素的索引数组
    vector<int> stack; // 用于存储索引的栈

    // 计算右侧第一个大于该元素的索引
    for (int i = 0; i < n; i++) {
        while (!stack.empty() && elements[stack.back()] <= elements[i]) {
            right_greater_indices[stack.back()] = i; // 更新右侧第一个大于该元素的索引
            stack.pop_back(); // 弹出栈顶元素
        }
        stack.push_back(i); // 当前元素的索引入栈
    }

    stack.clear(); // 清空栈

    // 计算左侧第一个大于该元素的索引
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.empty() && elements[stack.back()] <= elements[i]) {
            left_greater_indices[stack.back()] = i; // 更新左侧第一个大于该元素的索引
            stack.pop_back(); // 弹出栈顶元素
        }
        stack.push_back(i); // 当前元素的索引入栈
    }
}

// 处理查询
void processQueries(const vector<int>& max_indices, int max_val_count) {
    for (int i = 0; i < k; i++) {
        int left, right;
        cin >> left >> right;
        left -= 1; // 转换为0-based索引
        right -= 1; // 转换为0-based索引

        int max_index = findMaxIndex(left, right); // 在区间[left, right]中找到最大值的索引

        if (elements[max_index] == elements[max_indices[0]]) { // 如果区间最大值等于全局最大值
            if (max_val_count >= 2) { // 如果全局最大值出现次数大于等于2次
                cout << "draw" << endl;
                int lower_bound_idx = lower_bound(max_indices.begin(), max_indices.end(), left) - max_indices.begin(); // 找到大于等于left的第一个最大值索引
                int upper_bound_idx = upper_bound(max_indices.begin(), max_indices.end(), right) - max_indices.begin() - 1; // 找到小于等于right的最后一个最大值索引
                if (lower_bound_idx < upper_bound_idx) {
                    cout << right - left + 1 << endl; // 如果在查询区间内有两个最大值，输出查询区间的长度
                } else {
                    int adjustment = INT_MAX; // 初始化调整值
                    if (lower_bound_idx > 0) {
                        adjustment = min(adjustment, max_indices[lower_bound_idx] - left); // 计算调整值
                    }
                    if (upper_bound_idx < (int)max_indices.size() - 1) {
                        adjustment = min(adjustment, right - max_indices[upper_bound_idx]); // 计算调整值
                    }
                    cout << right - left + 1 + adjustment << endl; // 输出调整后的长度
                }
            } else {
                cout << "lose" << endl;
                cout << (left == right ? 2 : right - left + 1) << endl; // 如果全局最大值只有1次，输出"lose"并输出查询区间的长度
            }
        } else {
            int left_boundary = (left_greater_indices[max_index] != -1) ? left_greater_indices[max_index] : -0x3f3f3f3f; // 左侧第一个大于max_index元素的索引
            int right_boundary = (right_greater_indices[max_index] != -1) ? right_greater_indices[max_index] : 0x3f3f3f3f; // 右侧第一个大于max_index元素的索引
            cout << "win" << endl;
            cout << min(right_boundary - right, left - left_boundary) + right - left + 1 << endl; // 输出查询区间的长度
        }
    }
}

int main() {
	std::ios::sync_with_stdio(false); // 提高输入输出效率
    cin >> n >> k; // 输入数组长度和查询次数
    elements.resize(n); // 调整元素数组大小
    log_values.resize(n + 1, 0); // 初始化log值数组
    sparse_table.assign(n, vector<int>((int)log2(n) + 1, 0)); // 初始化稀疏表

    // 输入元素数组
    for (int i = 0; i < n; i++) {
        cin >> elements[i];
    }

    // 构建log值和稀疏表
    buildLogValues();
    buildSparseTable();

    // 计算左右侧第一个大于元素的索引
    calculateGreaterIndices();

    int max_val = *max_element(elements.begin(), elements.end()); // 找到元素数组中的最大值
    int max_val_count = count(elements.begin(), elements.end(), max_val); // 计算最大值的出现次数
    vector<int> max_indices; // 存储最大值的所有索引

    // 找出最大值的所有索引
    for (int i = 0; i < n; i++) {
        if (elements[i] == max_val) {
            max_indices.push_back(i); // 如果当前元素等于最大值，存储它的索引
        }
    }

    // 处理查询
    processQueries(max_indices, max_val_count);

    return 0;
}

题目内容

小明和小美在玩一个游戏，游戏中有一个长度为$n$的数组$a$,她们会玩$q$轮游戏，每轮游戏都是独立的。

游戏规则如下，双方都会执行最优策略：

$1)$第一步，游戏给出一个区间[$l,r$]。

$2)$第二步，小明在[$l,r$]区间中选择一个数。

$3)$第三步，小美将区间扩展成[$L,R$] ([$L,R$]必须包含[$l,r$])，然后在[$L,R$]区间中选择一个数，但不能跟小明选同一个数。

$4)$第四步，小明和小美选择的数字较大的一方获胜，若相同则平局。

小美想知道她每一轮的输赢状态，并且她想知道要达到输赢状态所需的[$L,R$]区间长度最小是多少。

输入描述

第一行输入两个正整数$n$，$q$($2≤n,q≤2×10^5$),表示数组长度和询问次数。

第二行输入$n$个正整数$a$($1≤a_i≤10^9$),表示数组。

接下来$q$行，每行输入两个整数($1≤l≤r≤n$)，表示询问

输出描述

对于每个询问先输出一行，若小美可以获胜则输出”$win$“,若平局则输出”$draw$“,多失败则输出”$lose$“。

第二行输出达到最终状态所需的区间长度的最小值。

样例1

输入

6 2
1 1 4 5 1 4
1 3
4 4

输出

win
4
lose
2

说明

第$1$个询问，小明会选择数字$4$，小美将区间扩展成[$1,4$]，选择数字$5$，小美获胜，扩展后的区间长度为$4$。

第$2$个询问，小明会选择数字$5$，小美将区间扩展成[$3,4$]，选择数字$4$，小美获胜，扩展后的区间长度为$2$。