bzoj5007: TCP协议

Description

在如今的网络中，TCP是一种被广泛使用的网络协议，它在传输层提供了可靠的通信服务。众所周知，网络是存在

时延的，例如用户先后向服务器发送了两个指令op1和op2，并且希望服务器先处理指令op1，再处理指令op2；但由

于网络时延，这两个指令可能会失序到达，而导致服务器先执行了指令op2，这是我们不希望看到的。TCP协议拥有

将失序到达的报文按顺序重组的功能，一种方法是给每一个报文打上一个时间戳。而你今天要实现的功能比这个要

简单很多。我们需要你维护一个服务器，这个服务器的功能是一个简单的栈，你会接收三种用户的指令：

push x t --- 表示将x元素入栈，这条指令的时间戳为t

pop t --- 表示将栈顶元素弹出，这条指令的时间戳为t

peak t --- 用户询问现在栈顶元素的值，这条指令的时间戳为t

当一条时间戳为t的指令到达时，你需要进行如下处理：

1.将所有之前执行的时间戳大于t的push和pop指令全部撤销

2.执行当前这条指令

3.按时间戳顺序重新执行在第1步被撤销的指令

注意你不需要撤销以及重新执行之前已经执行过的peak指令

也就是说每一条peak指令只有在它到达的时候会被执行一次。

我们保证每一条指令的时间戳都是唯一的；

若你在需要执行一条pop指令时发现当前栈为空，则当前你可以忽略这条指令。

Input

第一行包含一个整数n，表示指令总数。

接下来n行按指令到达服务器的顺序给出每一条指令，有三种类型

push x t

pop t

peak t

1 <= n <= 300000，0 <= x，t <= 1000000000

Output

对于每一条peak指令，输出对应的答案占一行；若栈为空，输出-1。

用线段树维护操作对应的括号序列的前缀和（push=1,pop=-1,peak=0,未执行=0），查询相当于查询一个位置向左第一个小于指定值的位置。

#include<bits/stdc++.h>

const int N=;

char buf[N*],*ptr=buf;

int _(){

    int x=;

    while(*ptr<)++ptr;

    while(*ptr>)x=x*+*ptr++-;

    return x;

}

int n,ts[N],qs[N][],tp=,vs[N];

int _x,_a,_p;

int min(int a,int b){return a<b?a:b;}

struct node{

    node*lc,*rc;

    int L,R,M;

    int mn,a;

    void add(int x){

        mn+=x,a+=x;

    }

    void dn(){

        if(a){

            lc->add(a);

            rc->add(a);

            a=;

        }

    }

    void up(){

        mn=min(lc->mn,rc->mn);

    }

    void add(){

        if(_x<=L)return add(_a);

        dn();

        if(_x<=M)lc->add();

        rc->add();

        up();

    }

    int at(){

        if(L==R)return mn;

        dn();

        return (_x<=M?lc:rc)->at();

    }

    bool find(){

        if(mn>=_a)return ;

        if(L==R)return _p=R+,;

        dn();

        if(_x>M&&rc->find())return ;

        return lc->find();

    }

}ns[N*],*np=ns,*rt;

node*build(int L,int R){

    node*w=np++;

    w->L=L,w->R=R;

    if(L<R){

        int M=w->M=L+R>>;

        w->lc=build(L,M);

        w->rc=build(M+,R);

    }

    return w;

}

int $(int x){

    return std::lower_bound(ts,ts+tp,x)-ts;

}

int main(){

    fread(buf,,sizeof(buf),stdin);

    n=_();

    ts[tp++]=-;

    for(int i=;i<=n;++i){

        qs[i][]=_();

        qs[i][]=_();

        if(qs[i][]==)ts[tp++]=qs[i][]=_();

        else ts[tp++]=qs[i][];

    }

    std::sort(ts,ts+tp);

    rt=build(,tp-);

    vs[]=-;

    for(int i=;i<=n;++i){

        if(qs[i][]==){

            _x=$(qs[i][]);

            vs[_x]=qs[i][];

            _a=,rt->add();

        }else if(qs[i][]==){

            _x=$(qs[i][]);

            _a=-,rt->add();

        }else{

            _x=$(qs[i][]);

            _a=rt->at();

            _p=;

            rt->find();

            printf("%d\n",vs[_p]);

        }

    }

    return ;

}

巴特西

bzoj5007: TCP协议

Description

Input

Output

最新文章

热门文章