BZOJ 1012: [JSOI2008]最大数maxnumber 线段树

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1012

现在请求你维护一个数列,要求提供以下两种操作: 1、 查询操作。语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。限制:L不超过当前数列的长度。 2、 插入操作。语法:A n 功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。限制:n是非负整数并且在长整范围内。注意:初始时数列是空的,没有一个数。

Input

第一行两个整数,M和D,其中M表示操作的个数(M <= 200,000),D如上文中所述,满足(0

Output

对于每一个查询操作,你应该按照顺序依次输出结果,每个结果占一行。

算法分析:起初咋一看,可以用线段树做,于是就做了,迅速搞之,交之,WA...,为啥了,不应该呀,查代码,又交之,WA,,,无语中,后来突然想起了,C++提交得用lld呀,平常习惯了I64d了,买了个表的。

不过这道题可以用单调栈做,而且代码比线段树更简单。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
typedef long long LL;
const int maxn=+; LL M,D;
LL cnt,an[maxn],sum[maxn<<]; void PushUP(LL rt) {sum[rt]=max(sum[rt<<],sum[rt<<|]); } void build(LL l,LL r,LL rt)
{
sum[rt]=-inf;
if (l==r) return;
LL mid=(l+r)>>;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
PushUP(rt);
} void update(LL l,LL r,LL rt,LL p,LL value)
{
if (l==r) {sum[rt]=value;return; }
LL mid=(l+r)>>;
if (p<=mid) update(l,mid,rt<<,p,value);
else update(mid+,r,rt<<|,p,value);
PushUP(rt);
} LL query(LL l,LL r,LL rt,LL x,LL y)
{
if (x<=l && r<=y) return sum[rt];
LL mid=(l+r)>>;
LL ret=-inf;
if (y<=mid) ret=max(ret,query(l,mid,rt<<,x,y));
else if (x>mid) ret=max(ret,query(mid+,r,rt<<|,x,y));
else
{
ret=max(ret,query(l,mid,rt<<,x,y));
ret=max(ret,query(mid+,r,rt<<|,x,y));
}
PushUP(rt);
return ret;
} int main()
{
while (scanf("%lld%lld",&M,&D)!=EOF)
{
memset(sum,,sizeof(sum));
LL t=,N=M;
char ch[];
LL l,v;
cnt=;
build(,M,);
for (LL i= ;i<M ;i++)
{
scanf("%s",ch);
if (ch[]=='A')
{
scanf("%lld",&v);
v=(v+t)%D;
update(,N,,++cnt,v);
}
else
{
scanf("%lld",&l);
LL ans=query(,N,,cnt-l+,cnt);
printf("%lld\n",ans);
t=ans;
}
}
}
return ;
}
上一篇:Docker学习之Centos7下安装


下一篇:Node.js初探之hello world