题解：P11403 [RMI 2020] 软盘 / Floppy（无法评测）

Nelofus · 2025-01-06 12:04:48 · 题解

直接做单调栈。

从前往后做单调栈，不难注意到退栈总次数是 \mathcal O(n) 的，所以我们传的 01 串里，每次到一个新的位置就用一个 0 来标记，每发生一次退栈就在序列末尾加一个 1。

把所有询问挂在其右端点，询问的答案就是扫到右端点的时候，单调栈里大于等于左端点的最小元素。

// Code by Heratino & Nelofus
// 何度も 絶望の前で折り返す
#include "bits/stdc++.h"
#include "floppy.h"
using i64 = long long;

void save_to_floppy(const std::string &bits);
void read_array(int subtask_id, const std::vector<int> &v) {
    int n = v.size();
    std::string s;
    std::vector<int> stk;
    std::string str;
    for (int i = 0; i < n; i++) {
        str += '0';
        while (!stk.empty() && v[stk.back()] < v[i])
            stk.pop_back(), str += '1';
        stk.push_back(i);
    }
    save_to_floppy(str);
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    int m = a.size();
    std::vector<std::vector<int>> vec(N);
    std::vector<int> ans(m);
    for (int i = 0; i < m; i++)
        vec[b[i]].push_back(i);
    std::vector<int> stk;
    int pos = 0;
    for (int i = 0; i < bits.size(); i++) {
        int j = i + 1;
        while (bits[j] != '0' && j < bits.size())
            j++;
        j--;
        for (int _ = 0; _ < j - i; _++)
            stk.pop_back();
        stk.push_back(pos);
        for (const int &qry : vec[pos]) {
            int l = a[qry];
            ans[qry] = *std::lower_bound(stk.begin(), stk.end(), l);
        }
        pos++;
        i = j;
    }
    return ans;
}