tofacebook.com -专业IT技术社区 BZOJ 1012 [JSOI2008]最大数maxnumber Web程序【tofacebook.com】 - tofacebook.com-专业IT技术社区
82°

BZOJ 1012 [JSOI2008]最大数maxnumber Web程序【tofacebook.com】

标签:algo   out   har   ++   turn   res   namespace   number   val   

看到题的第一眼,我问LLJ大佬,这是不是主席树模板题呀,然后被大佬无情地嘲笑了。

又思考了一下,感觉树套树可做,我大概是傻了吧。

LLJ说,题解是单调队列啊。

我觉得他说的十分有道理。

裸的单调队列。

技术分享
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<queue> #include<vector> typedef long long LL; using namespace std; const int maxn=200000+299; int m,mod,t,x,que[maxn],val[maxn],tot,now; char op[5]; int ef(int l,int r,int x) { int res=0; while(l<=r) { int mid=(l+r)>>1; if(que[mid]>=now-x+1) { res=val[que[mid]]; r=mid-1;} else l=mid+1; } return res; } int main() { //freopen(".in","r",stdin); //freopen(".out","w",stdout);
    scanf("%d%d",&m,&mod); while(m--) { scanf("%s%d",&op,&x); if(op[0]==A) { x=(x+t)%mod;  now++; while(tot&&val[que[tot]]<=x) { tot--; } que[++tot]=now; val[now]=x; } else { t=ef(1,tot,x); printf("%d\n",t); } } return 0; }
View Code

 

BZOJ 1012 [JSOI2008]最大数maxnumber

标签:algo   out   har   ++   turn   res   namespace   number   val   

原文地址:http://www.cnblogs.com/Achenchen/p/7531897.html


本文由百家号/熊掌号作者上传并发布,百家号仅提供信息发布平台。文章仅代表作者个人观点,不代表百度立场。

已有 0 条评论

    我有话说: