#include<iostream>
using namespace std;
const int N = 2e5 + 5;
typedef long long LL;
//线段树的结点, 最大空间开4倍
struct Node{
int l, r;
int v; //最大值
}tr[N * 4];
int m, p;
//u为当前线段树的结点编号
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);
}
//查询以u为根节点,区间[l, r]中的最大值
int query(int u, int l, int r) {
// Tl-----Tr
// L-------------R
//1.不必分治,直接返回
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;
// Tl----m----Tr
// L-------------R
//2.需要在tr的左区间[Tl, m]继续分治
if(l <= mid) v = query(u << 1, l, r);
// Tl----m----Tr
// L---------R
//3.需要在tr的右区间(m, Tr]继续分治
if(r > mid) v = max(v, query(u << 1 | 1, l, r));
// Tl----m----Tr
// L-----R
//2.3涵盖了这种情况
return v;
}
//u为结点编号,更新该结点的区间最大值
void modify(int u, int x, int v) {
if(tr[u].l == tr[u].r) tr[u].v = v; //叶节点,递归出口
else {
int mid = tr[u].l + tr[u].r >> 1;
//分治处理左右子树, 寻找x所在的子树
if(x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
//回溯,拿子结点的信息更新父节点, 即pushup操作
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
}
int main()
{
//n表示树中的结点个数, last保存上一次查询的结果
int n = 0, last = 0;
cin >> m >> p;
//初始化线段树, 结点的区间最多为[1, m]。
build(1, 1, m);
while(m--)
{
char op;
cin >> op;
if(op == 'A') //添加结点
{
int t;
cin >> t;
//在n + 1处插入
modify(1, n + 1, ((LL)t + last) % p);
//结点个数+1
n++;
}
else
{
int L;
cin >> L;
//查询[n - L + 1, n]内的最大值,u = 1,即从根节点开始查询
last = query(1, n - L + 1, n);
cout << last << endl;
}
}
return 0;
}
为啥在查询区间里面只用给右区间找最大值 左区间不需要
因为是两个if语句,如果左区间有,会先在左区间找,返回v是左区间最大值,然后如果右区间有的话那么会再去右区间找,返回值和v比较大小,其实就是省略的写法而已
orz
build函数里的第一行:tr[u]={l,r}为什么我在本地运行出黄字,正式比赛允许这样写吗
;w;
虽然初始化列表易于使用,但它有两个缺点:
如果有某个成员未被初始化,那么在这种情况下,跟随在该成员后面的成员都不能初始化。
如果结构体包括任何诸如字符串之类的对象,那么在许多编译器上它都将无法运行。
黄色是warning,不是error,就是提醒你要小心,不能有三个属性,只初始化两个,可能会造成错误,但不是一定会造成错误,错误的风险自行承担。相比于构造函数,无疑列表形式更方便,只要我们小心使用,就是OK。
好的 感谢
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
int m, p, last, n;
struct node
{
int l, r;
int v;
} tr[4 * N];
void build(int rt, int l, int r)
{
// cout << “111” << endl;
tr[rt] = {l, r};
if (l == r)
return;
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
}
//查询l-r区间的最大值
int query(int rt, int l, int r) // u是拥有的区间,l-r是查询的区间
{
if (tr[rt].l >= l && tr[rt].r <= r) //所拥有的区间小于要查询的区间
return tr[rt].v;
int mid = tr[rt].l + tr[rt].r >> 1;
int v = 0;
if (l <= mid)
v = query(rt << 1, l, r);
if (r > mid)
v = max(v, query(rt << 1 | 1, l, r));
return v;
}
void modify(int rt, int x, int v) //将以rt为根节点的线段树的x节点值修改为v
{
if (tr[rt].l == tr[rt].r)
tr[rt].v = v;
else
{
int mid = tr[rt].l + tr[rt].r >> 1;
if (x <= mid)
modify(rt << 1, x, v);
else
modify(rt << 1 | 1, x, v);
tr[rt].v = max(tr[rt << 1].v, tr[rt << 1 | 1].v);
}
}
int main()
{
scanf(“%d%d”, &m, &p);
build(1, 1, m);
while (m–)
{
char c;
scanf(“%c”, &c);
if (c == ‘Q’)
{
int l;
scanf(“%d”, &l);
last = query(1, n - l + 1, n);
printf(“%d\n”, last);
}
else
{
int t;
scanf(“%d”, &t);
modify(1, n + 1, ((LL)t + last) % p);
n++;
}
}
}
你要不要自己看看你发的是什么东西
hhhhhhhh
那个个大佬可以看一眼这个歌代码哪里错了qwq
请问query函数的意义可以这样理解吗 更新以u为根结点的值为x节点的值
请问query函数的意义可以这样理解吗 更新以u为根结点的值为x节点的值
这题可以用树状数组来写吧
可以把tr[ ]维护的区间和改成最值就可以
好像不可以 因为最大值不能做减法
强的,但是这道题还能用st表来写
st表不能吧
可以的
https://www.acwing.com/solution/content/132664/
宁甚至逼我写了个题解(逃
dalao们 modify操作中,叶子结点不需要维护最大值嘛 为什么可以直接修改,而不是这样子写 if(tr[u].l==x&&tr[u].r==x) tr[u].v=max(tr[u].v,v);
添加操作,不用维护
叶子节点只有一个数
为啥query里递归左右两边l , r都不变呢,递归左边不应该是(l,mid)吗
query 里面的[l, r]是需要查询的区间,需要根据线段树的节点信息来算出,所以变化的只是线段树的节点,而查询区间始终不需要改变。不知道这样有没有说清楚?
改变后为什么是错误的呀。大佬可以点播一下码。想不明白为什么不能改
$l、r$ 是查询的区间,是始终不变的,要改变的是树中的节点。
二分的过程我们可以不用写出来。
详细的写法你可以看一下 OI Wiki 的写法:
带师modify要加long long 现在数据会溢出
谢谢指正,已修改