洛谷P1198：https://www.luogu.org/problemnew/show/P1198
思路
一道水水的线段树 20分钟A掉
这道题只涉及到单点修改和区间查询 所以这道题甚至不用Lazy-Tag
每次加入一个新的点就是修改一个节点
总区间长为操作次数m （假设所有操作都为添加一个节点）
因此题目就简单多了
代码
#include<iostream>
using namespace std;
#define ll long long
#define Max 200000
#define INF 1e9+7
ll m,p,n,t;
ll maxn[Max<<
2];
//4倍数组
void build(ll s,ll v,ll l,ll r,ll k)
{
if(l==
r)
{
maxn[k]=v;
//叶子节点
return;
}
ll mid=(l+r)>>
1;
if(mid>=s) build(s,v,l,mid,k<<
1);
//当此点在mid前 只需要建mid前面的树
if(mid<s) build(s,v,mid+
1,r,k<<
1|
1);
//同上
maxn[k]=max(maxn[k<<
1],maxn[k<<
1|
1])%
p;
return;
}
ll query(ll x,ll y,ll l,ll r,ll k)
{
if(l>=x&&r<=y)
return maxn[k]%
p;
ll mid=(l+r)>>
1;
ll a1=-INF,b1=-INF;
//因为有负数 所以要设一个负的极小值
if(x<=mid) a1=query(x,y,l,mid,k<<
1)%p;
//左子树的最大值
if(y>mid) b1=query(x,y,mid+
1,r,k<<
1|
1)%p;
//右子树的最大值
return max(a1,b1);
//选一个最大的
}
int main()
{
cin>>m>>
p;
for(ll i=
1;i<=m;i++
)
{
char a;
ll b;
cin>>a>>
b;
if(a==
'A')
{
n++
;
build(n,(b+t)%p,
1,m,
1);
//n为当前是第几个节点 注意叠加t
}
if(a==
'Q')
{
t=query(n-b+
1,n,
1,m,
1);
//注意区间是[n-b+1,n] 因为是倒数的b个数
cout<<t<<
endl;
}
}
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9762192.html
