题解：P11403 [RMI 2020] 软盘 / Floppy

许多 · 2025-11-10 20:39:58 · 题解

刚学通信题，这题很适合练手。

发现数据要求 L \le 2n，满足这个特性的结构不多，再结合题目要求找区间最大值位置，不难想到用单调栈维护，不会用单调栈维护离线 RMQ 问题的可以看 OI-wiki。

我们从头开始扫描，入栈记为 1，出栈记为 0。显然这个长度小于 2n。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r,i;
    bool operator<(const node a)const{
        return r<a.r;
    }
};
void save_to_floppy(const string&);
void read_array(int subtask_id, const vector<int> &v){
    stack<int>s;
    string S;
    for(auto now:v){
        while(!s.empty()&&s.top()<now)S=S+'0',s.pop();
        S=S+'1';s.push(now);
    }
    save_to_floppy(S);
}
vector<int> solve_queries(int subtask_id,int N,const string &bits, const vector<int> &a,const vector<int> &b){
    vector<node>x;
    for(int i=0;i<a.size();i++)
        x.push_back({a[i],b[i],i});
    sort(x.begin(),x.end());
    int s[100000],cnt=0,i=0,j=0;
    vector<int>ANS(x.size());
    for(auto now:x){
        while(j<=now.r){
            if(bits[i]=='0')cnt--;
            else s[++cnt]=j++;
            i++;
        }
        int L=1,R=cnt,ans=cnt;
        while(L<=R){
            int mid=L+R>>1;
            if(s[mid]>=now.l)ans=s[mid],R=mid-1;
            else L=mid+1;
        }
        ANS[now.i]=ans;
    }
    return ANS;
}