萌新求调线段树裸题

P1253 扶苏的问题

@[dkqwq](/user/311306) 还在吗
by 2018heyuyang @ 2022-08-04 20:06:45


```cpp #define nul -0x3f3f3f3f ``` 首先这东西会爆int 但是改为 ```cpp #define nul -1000000000000000000 ``` 或 ```cpp #define nul -1000000000000000000ll ``` 都没有问题,但我建议用最后一种 --- 其次在 ```cpp struct tree{ int l,r; ll maxx; ll add,change_to; }t[N];///////////////N*4 ``` 中,空间应开 N*4 最后还有一个问题,change和add的关系处理不正确
by 2018heyuyang @ 2022-08-04 20:14:02


还有一个,你change函数那里把pushup打成pushdown了
by 2018heyuyang @ 2022-08-04 20:15:32


@[2018heyuyang](/user/120634) 谢谢大佬
by dk_qwq @ 2022-08-04 20:44:18


@[2018heyuyang](/user/120634) 大佬能详细说说change和add的关系怎么处理吗
by dk_qwq @ 2022-08-04 20:47:50


你要让你的函数分清change和add两个事件哪个先发生,哪个后发生 @[dkqwq](/user/311306)
by 2018heyuyang @ 2022-08-04 20:56:45


然后统一标准 比如线段树一个节点 你的标准是add先发生,change后发生 那么pushdown是先下传add,然后change 然后修改操作也要标准一样,如果此时是add操作,然后你发现这里已经有一个change的标记了 这时你不能简单加一个add就走 因为以后这个函数是认为change先发生的
by 2018heyuyang @ 2022-08-04 21:00:07


此时的解决方法是把change下传,那么下面的节点认为change后发生,正确的
by 2018heyuyang @ 2022-08-04 21:03:32


当然换个标准,如果change先发生,add后发生 你add是随便加的,但是如果你进来一个change 但是你 add!=0 以后节点看到change和add都有就会先change后add,这就产生了错误
by 2018heyuyang @ 2022-08-04 21:05:08


所以change进来的时候 一个简单方法就是让add=0就行了
by 2018heyuyang @ 2022-08-04 21:06:23


| 下一页