P3850 [TJOI2007] 书架

XichenOC · 2025-01-21 21:18:50 · 题解

P3850 [TJOI2007] 书架

题目翻译：

原本有 n 本书，有 q 次插入操作，可以将任意书插入其中，最后共有 q 次查询，求某个位置上的书名。

思路：

又是一道可以用rope水掉的紫题

可以用 rope 储存每一个书名的编号，将对应编号用 insert 直接插入，然后在查询时直接根据编号输出书名即可。

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int N=2e5+10;
string s[N];
rope<int>a;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[a.size()];
        a.push_back(a.size());
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        int k;
        cin>>s[a.size()]>>k;
        a.insert(k,a.size());
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        cout<<s[a[k]]<<"\n";
    }
}

rope讲解