Luogu P1198 [JSOI2008]最大数

时间:2022-01-11 08:50:13

  我会用高级(???)的单调栈来打这道题吗?

  线段树即可水过。

  假设这个数列刚开始所有数都是0,然后我们每次只要进行一个点的修改和区间求和即可。

  这不就是 线段树大法。

  只要用一个len记录一下当前数列长度即可

  (刚开始智障把求最大数打成求和了,还过样例了)

  CODE

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
const int N=,INF=;
LL tree[N*+],n,d,x,last,len;
char ch;
inline void read(LL &x)
{
x=; char ch=getchar(); int flag=;
while (ch<''||ch>'') { if (ch=='-') flag=-; ch=getchar(); }
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
x*=flag;
}
inline void write(LL x)
{
if (x<) putchar('-'),x=-x;
if (x/) write(x/);
putchar(x%+'');
}
inline LL max(LL a,LL b) { return a>b?a:b; }
inline void updata(LL root,LL l,LL r,LL id,LL add)
{
if (l==r)
{
if (l==id)
{
tree[root]=add;
return;
}
}
LL mid=l+r>>;
if (id<=mid) updata(root*,l,mid,id,add); else updata(root*+,mid+,r,id,add);
tree[root]=max(tree[root*],tree[root*+]);
}
inline LL query(LL root,LL l,LL r,LL ql,LL qr)
{
if (l>=ql&&r<=qr) return tree[root];
LL res=-INF,mid=l+r>>;
if (ql<=mid) res=max(res,query(root*,l,mid,ql,qr));
if (mid<qr) res=max(res,query(root*+,mid+,r,ql,qr));
return res;
}
int main()
{
read(n); read(d);
while (n--)
{
cin>>ch;
if (ch=='A')
{
read(x);
x+=last;
x%=d;
updata(,,N,++len,x);
} else
{
read(x);
last=query(,,N,len-x+,len);
write(last);
putchar('\n');
}
}
return ;
}