HDU 4699 Editor 维护栈

维护两个栈,分别存光标前和光标后的数

再维护前缀和的栈和前缀和最大值的栈

注意一下左移,右移,删除到顶了就不操作了

5个操作

I x : 光标处插入x -----> s1.push(x)

D : 光标前删除 -----> s1.pop()

L : 光标左移 -----> s2.push(s1.top()) s1.pop()

R : 光标右移 -----> s1.push(s2.top()) s2.pop()

Q k : 输出前k个数前缀和最大值

/********************* Template ************************/

#include <set>

#include <map>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <queue>

#include <stack>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cassert>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <fstream>

#include <numeric>

#include <iomanip>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define EPS         1e-8

#define MAXN        1000050

#define MOD         (int)1e9+7

#define PI          acos(-1.0)

#define DINF        (1e10)

#define LINF        ((1LL)<<50)

#define INF         (0x3f3f3f3f)

#define max(a,b)    ((a) > (b) ? (a) : (b))

#define min(a,b)    ((a) < (b) ? (a) : (b))

#define max3(a,b,c) (max(max(a,b),c))

#define min3(a,b,c) (min(min(a,b),c))

#define BUG         cout<<"BUG! "<<endl

#define line        cout<<"--------------"<<endl

#define L(t)        (t << 1)

#define R(t)        (t << 1 | 1)

#define Mid(a,b)    ((a + b) >> 1)

#define lowbit(a)   (a & -a)

#define FIN         freopen("in.txt","r",stdin)

#define FOUT        freopen("out.txt","w",stdout)

#pragma comment     (linker,"/STACK:102400000,102400000")

// typedef long long LL;

// typedef unsigned long long ULL;

// typedef __int64 LL;

// typedef unisigned __int64 ULL;

// LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; }

// LL lcm(LL a,LL b){ return a*b/gcd(a,b); }

/*********************   F   ************************/

int pstack[MAXN],sstack[MAXN];

int pre[MAXN];

int pmax[MAXN];

int main()

{

    //FIN;

    //FOUT;

    int n ;

    while(~scanf("%d",&n)){

        int now1 = ,now2 = ;

        while(n--){

            char ch;

            int a;

            getchar();

            scanf("%c",&ch);

            if(ch == 'I'){

                scanf("%d",&a);

                pstack[now1] = a;

                pre[now1] = (now1 == ) ? a : (pre[now1-]+a);

                pmax[now1] = (now1 == ) ? a : max(pmax[now1-],pre[now1]);

                now1++;

            }else if(ch == 'D'){

                if(now1 == ) continue;

                now1--;

            }else if(ch == 'L'){

                if(now1 == ) continue;

                sstack[now2] = pstack[now1-];

                now1--;

                now2++;

            }else if(ch == 'R'){

                if(now2 == ) continue;

                pstack[now1] = sstack[now2-];

                pre[now1] = (now1 == ) ? sstack[now2-] : (pre[now1-]+sstack[now2-]);

                pmax[now1] = (now1 == ) ? sstack[now2-] : max(pmax[now1-],pre[now1]);

                now2--;

                now1++;

            }else if(ch == 'Q'){

                scanf("%d",&a);

                printf("%d\n",pmax[a-]);

            }

        }

    }

    return ;

}

秒客网

HDU 4699 Editor 维护栈

相关文章