AcWing1275 最大数
题面
同洛谷P1198。
思路
线段树建树,如果每次插入都重新建树的话很慢会 TLE ,不如我们提前开好空间然后插入的时候单点修改就好了。开多大呢?由于操作总共才次,因此开即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200010;
int m,p;
struct node
{
int l,r;
int v;
}tr[N<<2];
void pushup(int u)//由子节点信息更新父节点信息(最大值)
{
tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}
void build(int u,int l,int r)
{
tr[u]={l,r,0};
if(l==r) return;
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);//如果不是建空树记得pushup
}
int query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v;//树中线段被查询区间包含
int mid=(tr[u].l+tr[u].r)>>1;
int v=0;
if(l<=mid) v=query(u<<1,l,r);
if(r>mid) v=max(v,query(u<<1|1,l,r));
return v;
}
void modify(int u,int x,int v)//修改为x的线段u的值为v
{
if(tr[u].l==x&&tr[u].r==x) tr[u].v=v;
else
{
int mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(u);//更新
}
}
signed main()
{
int n=0,last=0;
scanf("%lld%lld",&m,&p);
build(1,1,m);//从1号点开始的1~m区间
int x;
char op[2];
while(m--)
{
scanf("%s%lld",op,&x);
if(*op=='Q')//取值符号,代表首元素的值
{
last=query(1,n-x+1,n);
printf("%lld\n",last);
}
else
{
modify(1,n+1,(last+x)%p);
n++;
}
}
return 0;
}