第一眼看到这题，woc，这不是主席树！？旁边HZ也表示同意，然后cGh队长就慢悠悠的过来：“想什么，USACO会有主席树！？”
↓打脸不解释，大家可以去%ta的博客(这样ta就不会D飞我了~)http://blog.csdn.net/cgh_andy/article/details/53012348
既然师兄都说链表了，如果用主席树（就是可持久化线段树啦）水，不是很不给面子......
所以就学了一发，果然又快又短~其实代码很好理解的（强行引用）
我们设c[i]为i位置最近买的牛 f[i]表示上一个状态是哪个位置
对于三个操作 买：c[i]=x f[i]=i-1
卖：c[i]=c[ f[i-1] ] f[i]=f[ f[i-1] ]
跳：c[i]=c[k-1] f[i]=f[k-1]
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; int f[110000],c[110000]; char ss[5]; int main() { freopen("ttravel.in","r",stdin); freopen("ttravel.out","w",stdout); int n,x; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",ss+1); if(ss[1]=='a') scanf("%d",&x), f[i]=i-1, c[i]=x; else if(ss[1]=='s') f[i]=f[f[i-1]], c[i]=c[f[i-1]]; else scanf("%d",&x), f[i]=f[x-1], c[i]=c[x-1]; if(c[i]!=0)printf("%d ",c[i]); else printf("-1 "); } return 0; }