hdu 4699 Editor 模拟

  1. 云栖社区>
  2. 博客>
  3. 正文

hdu 4699 Editor 模拟

jxy 2013-08-24 00:55:00 浏览557
展开阅读全文

    多校10,1004 比赛的时候一直想构造个伸展树,结果写挫了。赛后发现其实就两个栈,顿时感觉被虐成渣了


/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>
using namespace std;
stack<int> a,b;
int sum[1000005];
int Max[1000005];
int now;
int main()
{
    int Q;
    while(~scanf("%d",&Q))
    {
        while(!a.empty())a.pop();
        while(!b.empty())b.pop();
        int i,t;
        char c;
        sum[0]=0;
        Max[0]=-1E9;
        now=0;
        for(i=0;i<Q;i++)
        {
            getchar();
            c=getchar();
            switch(c)
            {
                case 'I':
                    scanf("%d",&t);
                    a.push(t);
                    now++;
                    sum[now]=sum[now-1]+t;
                    Max[now]=max(Max[now-1],sum[now]);
                    break;
                case 'D':
                    if(!a.empty())
                    {
                        a.pop();
                        now--;
                    }
                    break;
                case 'L':
                    if(!a.empty())
                    {
                        b.push(a.top());a.pop();
                        now--;
                    }
                    break;
                case 'R':
                    if(!b.empty())
                    {
                        a.push(b.top());b.pop();
                        now++;
                        sum[now]=sum[now-1]+a.top();
                        Max[now]=max(Max[now-1],sum[now]);
                    }
                    break;
                case 'Q':
                    scanf("%d",&t);
                    printf("%d\n",Max[t]);
                    break;
            }
        }

    }
}


网友评论

登录后评论
0/500
评论
jxy
+ 关注