A simple Blog for wyx I've been down the bottle hoping.
2010 Open Silver 3.Time Travel
发表于: | 分类: Oi | 评论:0 | 阅读:43

$Description$
维护一个可持久化的栈
$Solution$
由于是栈,所以只需要记一下栈顶的标号,当然这是对于栈这种特殊情况来说的,但是通常来说有更为普遍的方法

我们可以写一个可持久化的数组。可持久化的数组用可持久化线段树也就是 主席树 ^主席树 维护一下就行

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 80000+5;
const int M = N << 3;
const int n = 80000+5;
using namespace std;
 
int root[N];
int tr[M];
int ls[M],rs[M];
int sz;
 
void add(int l,int r,int x,int &y,int pos,int tmp)
{
    y = ++sz;
    if(l==r)
    {
        tr[y] = tmp;
        return;
    }
    ls[y] = ls[x];
    rs[y] = rs[x];
    int mid = (l+r)>>1;
    if(pos <= mid) add(l,mid,ls[x],ls[y],pos,tmp);
    else add(mid+1,r,rs[x],rs[y],pos,tmp);
}
 
int ask(int k,int l,int r,int pos)
{
    if(l==r){return tr[k];}
    int mid = (l+r)>>1;
    if(pos <= mid)return ask(ls[k],l,mid,pos);
    else return ask(rs[k],mid+1,r,pos);
}
 
char str[5];
int tmp[N];
 
inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9') {x = (x << 1) + (x<<3) + ch - '0';ch = getchar();}
    return x*f;
}
 
int main()
{
//  freopen("03.in","r",stdin);
    int T = read();
    for(int i=1,tt;i<=T;++i)
    {
        scanf("%s",str);tmp[i] = tmp[i-1];
        if(str[0] == 'a')tt = read(), add(1,n,root[i-1],root[i],++tmp[i],tt);
        else if(str[0] == 's') tmp[i]--,root[i] = root[i-1];
        else tt = read(), root[i] = root[tt-1],tmp[i] = tmp[tt-1];
        if(tmp[i] == 0)puts("-1");
        else printf("%d\n",ask(root[i],1,n,tmp[i]));
    }
}
 
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP