首页 > 代码库 > BZOJ1012 JSOI2008 最大数maxnumber 线段树/栈+二分法
BZOJ1012 JSOI2008 最大数maxnumber 线段树/栈+二分法
题意：给定一个数列，要求维护：1、求倒数L个数中的最大值 2、在数列末尾插入（最近的1询问的答案+x）%D。其中初始序列为空。
法一：因为询问最多200000个，所以直接建一棵大小为M的线段树维护即可
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;struct Node{ int l,r,m; Node *lchild,*rchild; Node(){} Node(int _l,int _r):l(_l),r(_r),m(0),lchild(0),rchild(0){}}*Root;int N,M,D,x,t;char Order[6];void Pushup(Node *&x){ x->m=max(x->lchild->m,x->rchild->m);}void Build(Node *&x,int l,int r){ x=new Node(l,r); if(l==r) return; int m=(l+r)>>1; Build(x->lchild,l,m),Build(x->rchild,m+1,r);}void Update(Node *&x,int p,int v){ if(x->l==x->r){ x->m=v; return; } int m=(x->l+x->r)>>1; if(p<=m) Update(x->lchild,p,v); else Update(x->rchild,p,v); Pushup(x);}int Query(Node *&x,int l,int r){ if(l<=x->l && x->r<=r) return x->m; int m=(x->l+x->r)>>1,Ans=-1; if(l<=m) Ans=Query(x->lchild,l,r); if(m<r) Ans=max(Ans,Query(x->rchild,l,r)); return Ans;}int main(){ scanf("%d %d",&M,&D); Build(Root,1,M); for(int i=1,p;i<=M;i++){ scanf("%s",Order); if(Order[0]==‘Q‘){ cin >> p; cout << (t=Query(Root,N-p+1,N)) << endl; } else{ cin >> x; N++,Update(Root,N,(x+t)%D); } } return 0;}
法二：显然对于任意一个位置的数，其之前比它小的数在之后的询问中肯定没有贡献。所以维护一个单调栈，用二分来回答询问。
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <vector>using namespace std;#define ll long longconst int MAXN=200000+2;int M,N,s[MAXN],C,D,t,a[MAXN];char Order[6];int main(){ scanf("%d%d",&M,&D); while(M--){ int x; scanf("%s%d",Order,&x); if(Order[0]==‘Q‘){ int p=lower_bound(s+1,s+N+1,C-x+1)-s; printf("%d\n",t=a[s[p]]); } else{ x=(x+t)%D,a[++C]=x; while(N && a[s[N]]<=x) N--; s[++N]=C; } } return 0;}
BZOJ1012 JSOI2008 最大数maxnumber 线段树/栈+二分法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。