题目描述
Farmer John 买了台时光机，这使得他可以方便地管理自己的奶牛群。
他现在有?NN?个操作（1 \leq N \leq 8 \times 10^41≤N≤8×104），每次操作仅可能是如下三种之一：
a x：添加一头编号为?xx?的奶牛（1 \leq x \leq 10^61≤x≤106）。s：卖掉最近添加的奶牛（保证此时至少有一头奶牛）。t x：回到第?xx?次操作前的状态（保证第?xx?次操作存在）。
你需要在 FJ 执行每次操作后输出他拥有的最新的奶牛的编号。特别地，如果没有奶牛，输出?-1?1。
输入格式
第一行一个整数?NN。
接下来?NN?行，每行描述一次操作。
输出格式
第?ii?行输出第?ii?次操作后 FJ 拥有的最新的奶牛的编号。特别地，如果没有奶牛，输出?-1?1。
输入输出样例
输入 #1复制
12
a 5
a 3
a 7
s
t 2
a 2
t 4
a 4
s
t 7
s
s
输出 #1复制
5
3
7
3
5
2
7
4
7
2
5
-1
#include <iostream>
#include <cstring>
#include <algorithm>
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int N = 2e5;
rope<int>*ro[N];
int ssr[N];
int main()
{
ro[0]=new rope<int>(-1);
int m,i,x;
char opt;
scanf("%d",&m);
for(i=1;i<=m;i++)
{
ro[i]=new rope<int>(*ro[i-1]);
cin >> opt;
if(opt=='s') ro[i]->pop_back();
else
{
scanf("%d",&x);
if(opt=='a') ro[i]->push_back(x);
if(opt=='t') ro[i]=ro[x-1];
}
printf("%d\n",ro[i]->at(ro[i]->size()-1));
}
}
#include<cstdio>
#include<iostream>
using namespace std;
const int N=8e4+10;
int n,num[N]={-1}//储存牛奶编号
,t[N]//i次操作之后的栈高
,pre[N]//前一个
,top=0;
int main(){
cin >> n;
char ch;int x;
for(int i=1;i<=n;i++)
{
cin >> ch;
if(ch=='a')
{
cin >> x;
num[++top]=x;
t[i]=top;
pre[t[i]]=t[i-1];
}
else if(ch=='t')
{
//回溯
cin >> x;
t[i]=t[x-1];
}
else
t[i]=pre[t[i-1]];
printf("%d\n",num[t[i]]);
}
return 0;
}
----------------------------------我是分割线--------------------------------------
题目描述
Knuth 先生家里有个精致的书架，书架上有?NN?本书，如今他想学到更多的知识，于是又买来了?MM?本不同的新书。现在他要把新买的书依次插入到书架中，他已经把每本书要插入的位置标记好了，并且相应的将它们放好。由于 Knuth 年龄已大，过几天他已经记不清某些位置上放的到底是什么书了，请问你能帮助他吗？
输入格式
输入文件的第一行为整数?NN，接下来?NN?行分别是书架上依次放着的 N 本书的书名（书名由不含空格的字符串构成，长度不超过?1010）。下一行将要输入一个整数?MM，接下来的?MM?行分别为这本书的书名和要插入的位置。下一行将要输入一个整数?QQ，接下来共有?QQ?次询问，每行都是一个整数表示询问的位置。（书架上位置的编号从?00?开始）
输出格式
输出?QQ?行，每行对应着相应查询位置的书名。
输入输出样例
输入 #1复制
3
Math
Algorithm
Program
2
Picture 2
System 1
3
0
1
3
输出 #1复制
Math
System
Picture
说明/提示
原来有三本书 Math、Algorithm、Program，后来又买了两本书，分别插入到?22?和?11?的位置，每次插入时其他书都要向后挪一个位置，最后书架上书的序列为：
0 Math
1 System
2 Algorithm
3 Picture
4 Program
QQ?次询问依次为?00,?11,?33?位置的书，所以答案为：Math、System、Picture
对于?30\%30%?的数据，1 \leqslant N \leqslant 1001?N?100,?1 \leqslant M \leqslant 10^31?M?103,?1 \leqslant Q \leqslant 10^31?Q?103
对于?100\%100%?的数据，1 \leqslant N \leqslant 2001?N?200,?1 \leqslant M \leqslant 10^51?M?105,?1 \leqslant Q \leqslant 10^41?Q?104
对于?100\%100%?的数据都符合题目中所描述的限制关系，数据保证每次插入的位置均不超过当时书架上书的数量，而且保证?QQ?次查询中的每个位置上一定有书。
#include <iostream>
#include <cstring>
#include <algorithm>
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int N = 2e5;
rope<int>ro;
string ssr[N];
int main()
{
int n,x,m;
cin>>n;
int cnt=0;
while(n--)
{
cin >> ssr[cnt];
ro.push_back(cnt);
cnt++;
}
cin>>m;
while(m--)
{
cin >> ssr[cnt];
cin >> x;
ro.insert(x,cnt);
cnt++;
}
cin>>n;
while (n -- )
{
cin >> x;
cout<<ssr[ro[x]]<<endl;
}
}