题目描述
如何判断线段树每个节点需要存哪些信息:
1. 求某个区间的某种属性
2. 问什么就要存什么
3. 再存一些辅助信息
该题记录每个区间的最大值,得到左右两个区间的最大值,取一个max,即可得到最大值
线段树构建方法:(一般要开4*N)
struct Node
{
int l,r;
int v; //区间l,r中的最大值
}tr[N*4]
详细实现过程见注释
#include <iostream>
#include <cstring>
using namespace std;
const int N=200010;
int m,q;
struct Node
{
int l,r;
int v; //区间l,r中的最大值
}tr[N*4];
//由子节点的信息计算父节点的信息
void pushup(int u)
{
tr[u].v=max(tr[u<<1].v,tr[2*u+1].v);
}
void build(int u,int l,int r)
{
tr[u]={l,r};
if(l==r) return;
int mid=l+r>>1;
//左儿子:2x
build(u<<1,l,mid);
//右儿子:2x+1
build(u<<1|1,mid+1,r);
}
int query(int u,int l,int r)
{
//情况1:节点u的[u.l,u.r]已经包含在要查询的[l,r]中,直接返回
if(tr[u].l>=l && tr[u].r <=r) return tr[u].v;
//情况2:否则分治左右儿子
int mid=tr[u].l+tr[u].r>>1;
int v=0;
// Tl----m----Tr
// L-------------R
if(l<=mid) v=query(u<<1,l,r);
// Tl----m----Tr
// L---------R
//如l,r为[5,9],u.l,u.r为[6,10],需要在tr的右儿子(8, 10]继续分治
//而u的左儿子[6,8]已被包含,不用分治
//注意在更新右儿子的时候,需要对v取max操作,因为如果u.l,u.r为[1,5],此时
//目标区间为[5,9]会进入此分支,得到的query结果可能小于v
if(r>mid) v=max(v,query(u<<1|1,l,r));
return v;
}
void modify(int u,int x,int 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);
}
}
int main()
{
int n=0,last=0;
cin>>m>>q;
//初始化线段树, 结点的区间最多为[1, m]。
build(1,1,m);
while(m--)
{
char op;
int x;
cin>>op>>x;
if(op=='Q')
{
last=query(1,n-x+1,n);
cout<<last<<endl;
}
else
{
modify(1,n+1,(last+x)%q);
n++;
}
}
}