线段树
存储:
struct node{
int l,r;
int v;//维护的某个属性,例:区间的最大值
}tr[N * 4];//数组开四倍长度
pushup函数:
void pushup(int u)
{
tr[u].v = max(tr[u << 1].v,tr[u << 1 | 1].v);//父节点存储两个左右儿子的区间最大值的最大值
}
build函数:
void build(int u,int l,int r)//建立区间[l,r]的线段树
{
tr[u] = {l,r};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
pushup(u);
}
query函数:
int query(int u,int l,int r)//查询区间[l,r]
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
int v = 0;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) v = query(u << 1,l,r);
if(r > mid) v = max(v,query(u << 1 | 1,l,r));
return v;
}
modify函数:
void modify(int u,int x,int v)//单点修改,在x位置上修改值为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);
}
}
最大数
题目链接: https://www.acwing.com/problem/content/1277/
代码:
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 200010;
int m,p;
struct node{
int l,r;
int v;
}tr[N * 4];
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};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
pushup(u);
}
int query(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
int v = 0;
int mid = tr[u].l + tr[u].r >> 1;
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)
{
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;
//添加操作:向序列后添加一个数,序列长度变成 n+1;
cin>>m>>p;
build(1,1,m);//m个操作,最多添加m次,建m个坑位
while(m--)
{
char op;
int x;
cin>>op>>x;
if(op == 'Q')
{
last = query(1,n - x + 1,n);//查询前L个数,并将查询的数记录下来,以备添加时用
cout<<last<<endl;
}
else
{
//加入的数是 (t+a) mod p。其中,t 是输入的参数,a 是在这个添加操作之前最后一个询问操作的答案(如果之前没有询问操作,则 a=0)
modify(1,n + 1,(last + (LL)x) % p);//添加操作:向序列后添加一个数,序列长度变成 n+1;
n++;
}
}
return 0;
}