[Acwing] 128. 编辑器 栈模拟+最大值

前言

hh,还是不够灵活 传送门 :

前言

其实只要想想就会想到使用双栈 :

分别为 : L e f t , R i g h t Left , Right Left,Right 表示光标左右两边的值

对于删除,移动光标等操作,无非就是对应了 p o p ( ) , p u s h ( ) pop(),push() pop(),push()

从一个栈 到 另一个栈

只不过这里有一个点,查询第 k k k大的前缀和,给我难住了

难道是优先队列来做 ? ? ? ,如 : 此题型传送门

想了想不该啊,显然瞄了一眼题解区,好家伙,直接在每次队左区间进行操作的时

候，我们都进行一次 d p dp dp即可,这样子就可以直接输出了(显然,当简单 d p dp dp 遇上 栈

我就不认识他了)

CODE

stack l, r;
int sum[N],f[N];

void solve()
{
    char op[2];
    cin>>op;

    if(*op == 'I')
    {
        int x;
        cin>>x;
        l.push(x);
        sum[l.size()] = sum[l.size()-1]+l.top();
        f[l.size()] = max(f[l.size()-1],sum[l.size()]);
    }
    if(*op == 'D'  && !l.empty())
    {
        l.pop();
    }

    if(*op == 'L' && !l.empty())
    {
        r.push(l.top());
        l.pop();
    }

    if(*op == 'R' && !r.empty())
    {
        l.push(r.top());
        r.pop();
        sum[l.size()] = sum[l.size()-1] + l.top();
        f[l.size()]  = max(f[l.size()-1],sum[l.size()]);
    }

    if(*op == 'Q')
    {
        int k;
        cin>>k;
        cout