BZOJ1012最大数 [JSOI2008] 单调栈+二分

时间：2022-02-18 19:27:57

正解:单调栈+二分查找(or,线段树?

解题报告:

拿的洛谷的链接quq

今天尝试学习了下单调栈,然后就看到有个博客安利了这个经典例题?于是就去做了,感觉还是帮助了理解趴quqqqqq

这题,首先,一个很显然的点是,我们要维护一个单调递减的栈

这样想,如果有一个数,有另一个数比它大还在它右边,那显然它的存在是没有意义的(就像,比你强还比你小的oier,你是注定打不过的)

那如果我们读入了一个数,它左边有比它小的数.这些数就都没有存在的意义了嘛,我们就一一弹掉

你没有发现!这个的过程!就!很栈嘛!

好滴那按照我目前的理解来说这个就是,单调栈,,,趴?

然后就做完了

唯一要注意的就,询问的时候我们肯定是根据位置来找的嘛,然后我,很傻不拉几的,一个个找,,,这就丧失了查找的意义啊!!!丧失了单调的意义啊!!!那那那那我们就没有充分利用,单调这个东西!

所以我们应该,二分查找

好了结束

(哦对了其实因为单调性我们在弹的时候也可以二分查找,但是不知为何我改进了一下之后WA了,,,然后我又懒得再研究哪儿错了而且它还不能下数据,,,然后我就懒得再进一步搞了,就这样趴quqqqqq

那就直接放代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i,x,y) for(register ll i=x;i<=y;++i)
#define my(i,x,y) for(register ll i=x;i>=y;--i)

ll m,d,top=,z[],wz[],t,cnt;

inline ll read()
{
    ;;
    '))ch=getchar();
    ;
    )+(x<<)+(ch^'),ch=getchar();
    return y?x:-x;
}

int main()
{
    m=read();d=read();
    rp(i,,m)
    {
        char ch=getchar();while(ch!='Q' && ch!='A')ch=getchar();
        ;t=lower_bound(wz+,wz+top+,l)-wz;printf("%lld\n",z[t]);t=z[t];}
         && z[top]<n)top--;z[++top]=n;wz[top]=++cnt;}
    }
    ;
}

好滴!完美滴结束!

相关文章