校运会的时候随手抽的题…
一句话题意
维护一个序列，初始为空，要求滋兹：
1.查询这个序列末尾$x$个数的最大值
2.设上一次查询的答案为$t$（如果还没查询$t=0$），在末尾插入一个数$(x+t)mod d$，$d$为给定常数
很容易想到用线段树做：记录序列的末尾，然后直接单点修改区间查询
本来想随便写完就过了的…然后一直爆零…
因为我写了一句
while(n--)
然后这题应该就没什么要注意的地方了233
贴代码
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=200005;const int INF=(~0u>>2);typedef long long lint;inline lint read(){ ???lint s=0,f=1;char c=getchar(); ???while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} ???while(c>=‘0‘&&c<=‘9‘){s=s*10+c-‘0‘;c=getchar();} ???return s*f;}lint n,d,x,t,cnt;lint tr[N<<2];char c;#define lson (node<<1)#define rson (node<<1|1)inline void push_up(int node){ ???tr[node]=max(tr[lson],tr[rson]);}inline int query(int node,int l,int r,int ql,int qr){ ???if(ql<=l&&r<=qr)return tr[node]; ???int mid=(l+r)>>1; ???int res=-INF; ???if(mid>=ql)res=max(res,query(lson,l,mid,ql,qr)); ???if(mid+1<=qr)res=max(res,query(rson,mid+1,r,ql,qr)); ???return res;}inline void modify(int node,int l,int ?r,int q,lint val){ ???if(l==r&&r==q) ???{ ???????tr[node]=val; ???????return; ???} ???int mid=(l+r)>>1; ???if(mid>=q)modify(lson,l,mid,q,val); ???if(mid+1<=q)modify(rson,mid+1,r,q,val); ???push_up(node);}int main(){ ???n=read();d=read(); ???t=cnt=0; ???????for(register int i=1;i<=n;i++) ???{ ???????scanf("\n%c",&c);x=read(); ???????if(c==‘Q‘) ???????{ ???????????t=query(1,1,n,max(1,(int)(cnt-x+1)),cnt); ???????????printf("%lld\n",t); ???????}else ???????{ ???????????????????????cnt++; ???????????modify(1,1,n,cnt,(t+x)%d); ???????} ???} ???return 0;}听说有单调栈的做法…有空来填坑
[日常摸鱼]JSOI2008最大数
原文地址：http://www.cnblogs.com/yoooshinow/p/7896069.html