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

#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;
}