Fwio_ @ 2023-06-20 11:08:55
蒟蒻刚学线段树来搓这题,调了30min都没调出来,有没有大佬帮帮QwQ
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1000010;
int a[N] , n , m;
struct Node{
int l , r;
int sum , maxn , add;
}tr[N << 2];
void pushup(int u){
tr[u].sum += tr[u << 1].sum + tr[u << 1 | 1].sum;
tr[u].maxn = max(tr[u << 1].maxn , tr[u << 1 | 1].maxn);
}
void pushdown(int u){
if(tr[u].add){
tr[u << 1].add += tr[u].add , tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].add;
tr[u << 1 | 1].add += tr[u].add , tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].add;
tr[u].add = 0;
}
}
void build(int u , int l , int r){
if(l == r){
tr[u].l = l , tr[u].r = r;
tr[u].sum = a[l] , tr[u].maxn = a[l] , tr[u].add = 0;
return ;
}
else{
tr[u].l = l , tr[u].r = r;
int mid = l + r >> 1;
build(u << 1 , l , mid);
build(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
}
void update(int u , int l , int r , int k){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].maxn = k;
tr[u].sum = (tr[u].r - tr[u].l + 1) * k;
tr[u].add += k;
return ;
}
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) update(u << 1 , l , r , k);
else if(l > mid) update(u << 1 | 1 , l , r , k);
else update(u << 1 , l , mid , k) , update(u << 1 | 1 , mid + 1 , r , k);
pushup(u);
}
}
void modify(int u , int l , int r , int x){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].sum += (tr[u].r - tr[u].l + 1) * x;
tr[u].add += x;
tr[u].maxn += x;
return ;
}
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) modify(u << 1 , l , r , x);
else if(l > mid) modify(u << 1 | 1 , l , r , x);
else modify(u << 1 , l , mid , x) , modify(u << 1 | 1 , mid + 1 , r , x);
pushup(u);
}
}
int query(int u , int l , int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxn;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int maxn = 0;
if(r <= mid) maxn = query(u << 1 , l , r);
else if(l > mid) maxn = query(u << 1 | 1 , l , r);
else maxn = max(max(query(u << 1 , l , mid) , maxn) , query(u << 1 | 1 , mid + 1 , r));
return maxn;
}
int main(){
scanf("%d%d" , &n , &m);
for(int i = 1;i <= n;i++) scanf("%d" , &a[i]);
build(1 , 1 , n);
while(m--){
int opt;
scanf("%d" , &opt);
if(opt == 1){
int l , r , x;
scanf("%d%d%d" , &l , &r , &x);
update(1 , l , r , x);
}
else if(opt == 2){
int l , r , x;
scanf("%d%d%d" , &l , &r , &x);
modify(1 , l , r , x);
}
else{
int l , r;
scanf("%d%d" , &l , &r);
printf("%d\n" , query(1 , l , r));
}
}
return 0;
}
by QAQ__ @ 2023-06-20 12:06:24
@HVeo 区间赋值不能转换成区间加(后者是顺序无关的,前者不是),但是它们可以统一成
by Fwio_ @ 2023-06-20 12:24:05
@Link_Cut_Y 还在吗?又去学了一遍pushdown然后改了代码,改完之后是20pts Code:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1000010;
int a[N] , n , m;
struct Node{
int l , r;
int sum , maxn , add , cover;
}tr[N << 2];
void pushup(int u){
tr[u].maxn = max(tr[u << 1].maxn , tr[u << 1 | 1].maxn);
}
void pushdown(int u){
if(tr[u].cover != 0x3f3f3f3f){
tr[u << 1].cover = tr[u].cover , tr[u << 1].maxn = tr[u].cover;
tr[u << 1 | 1].cover = tr[u].cover , tr[u << 1 | 1].maxn = tr[u].cover;
tr[u].cover = 0x3f3f3f3f;
}
if(tr[u].add){
tr[u << 1].add += tr[u].add , tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].add;
tr[u << 1 | 1].add += tr[u].add , tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].add;
tr[u].add = 0;
}
}
void build(int u , int l , int r){
if(l == r){
tr[u].l = l , tr[u].r = r;
tr[u].sum = a[l] , tr[u].maxn = a[l] , tr[u].add = 0 , tr[u].cover = 0x3f3f3f3f;
return ;
}
else{
tr[u].l = l , tr[u].r = r;
int mid = l + r >> 1;
build(u << 1 , l , mid);
build(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
}
void update(int u , int l , int r , int k){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].sum = (tr[u].r - tr[u].l + 1) * k;
tr[u].maxn = k;
tr[u].cover = k;
tr[u].add = 0;
return ;
}
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) update(u << 1 , l , r , k);
else if(l > mid) update(u << 1 | 1 , l , r , k);
else update(u << 1 , l , mid , k) , update(u << 1 | 1 , mid + 1 , r , k);
pushup(u);
}
}
void modify(int u , int l , int r , int x){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].sum += (tr[u].r - tr[u].l + 1) * x;
tr[u].add += x;
tr[u].maxn += x;
return ;
}
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) modify(u << 1 , l , r , x);
else if(l > mid) modify(u << 1 | 1 , l , r , x);
else modify(u << 1 , l , mid , x) , modify(u << 1 | 1 , mid + 1 , r , x);
pushup(u);
}
}
int query(int u , int l , int r){
pushdown(u);
if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxn;
int mid = tr[u].l + tr[u].r >> 1;
int maxn = 0;
if(r <= mid) maxn = query(u << 1 , l , r);
else if(l > mid) maxn = query(u << 1 | 1 , l , r);
else maxn = max(max(query(u << 1 , l , mid) , maxn) , query(u << 1 | 1 , mid + 1 , r));
return maxn;
}
int main(){
scanf("%d%d" , &n , &m);
for(int i = 1;i <= n;i++) scanf("%d" , &a[i]);
build(1 , 1 , n);
while(m--){
int opt;
scanf("%d" , &opt);
if(opt == 1){
int l , r , x;
scanf("%d%d%d" , &l , &r , &x);
update(1 , l , r , x);
}
else if(opt == 2){
int l , r , x;
scanf("%d%d%d" , &l , &r , &x);
modify(1 , l , r , x);
}
else{
int l , r;
scanf("%d%d" , &l , &r);
printf("%d\n" , query(1 , l , r));
}
}
return 0;
}
by Link_Cut_Y @ 2023-06-20 13:52:47
@HVeo 我中午不在,现在才回来。
私信吧。
by Fwio_ @ 2023-06-20 13:56:01
@Link_Cut_Y en,好的
by Link_Cut_Y @ 2023-06-20 14:17:52
@HVeo
注意一下:答案可能会爆 int
,所以要开 long long
。
把 cover
的初值设置成 0X3F3F3F3F
可能会爆。建议开一个 INT = 1e12
。
在 query
的时候 maxn
初值应该设置成负无穷 -INF
而不是 0
。
不要维护 sum
标记!不要维护 sum
标记!不要维护 sum
标记!不要维护 sum
标记!
pushdown
函数里面 cover
标记下放的时候要把 add
重置成 0
。
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N = 1000010;
const int INF = 1e12;
int a[N] , n , m;
struct Node{
int l , r;
int maxn , add , cover;
}tr[N << 2];
void pushup(int u){
tr[u].maxn = max(tr[u << 1].maxn , tr[u << 1 | 1].maxn);
}
void pushdown(int u){
if(tr[u].cover != INF){
tr[u << 1].cover = tr[u].cover , tr[u << 1].maxn = tr[u].cover;
tr[u << 1 | 1].cover = tr[u].cover , tr[u << 1 | 1].maxn = tr[u].cover;
tr[u << 1].add = tr[u << 1 | 1].add = 0;
tr[u].cover = INF;
}
if(tr[u].add){
tr[u << 1].add += tr[u].add , tr[u << 1].maxn += tr[u].add;
tr[u << 1 | 1].add += tr[u].add , tr[u << 1 | 1].maxn += tr[u].add;
tr[u].add = 0;
}
}
void build(int u , int l , int r){
if(l == r) {
tr[u].l = l , tr[u].r = r;
tr[u].maxn = a[l] , tr[u].add = 0 , tr[u].cover = INF;
return ;
}
else{
tr[u].l = l , tr[u].r = r;
tr[u].maxn = -INF, tr[u].cover = INF;
int mid = l + r >> 1;
build(u << 1 , l , mid);
build(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
}
void update(int u , int l , int r , int k){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].maxn = k;
tr[u].cover = k;
tr[u].add = 0;
return ;
}
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) update(u << 1 , l , r , k);
else if(l > mid) update(u << 1 | 1 , l , r , k);
else update(u << 1 , l , mid , k) , update(u << 1 | 1 , mid + 1 , r , k);
pushup(u);
}
}
void modify(int u , int l , int r , int x){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].add += x;
tr[u].maxn += x;
return ;
}
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) modify(u << 1 , l , r , x);
else if(l > mid) modify(u << 1 | 1 , l , r , x);
else modify(u << 1 , l , mid , x) , modify(u << 1 | 1 , mid + 1 , r , x);
pushup(u);
}
}
int query(int u , int l , int r){
pushdown(u);
if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxn;
int mid = tr[u].l + tr[u].r >> 1;
int maxn = -INF;
if(r <= mid) maxn = query(u << 1 , l , r);
else if(l > mid) maxn = query(u << 1 | 1 , l , r);
else maxn = max(max(query(u << 1 , l , mid) , maxn) , query(u << 1 | 1 , mid + 1 , r));
return maxn;
}
signed main(){
scanf("%lld%lld" , &n , &m);
for(int i = 1;i <= n;i++) scanf("%lld" , &a[i]);
build(1 , 1 , n);
while(m--){
int opt;
scanf("%lld" , &opt);
if(opt == 1){
int l , r , x;
scanf("%lld%lld%lld" , &l , &r , &x);
update(1 , l , r , x);
}
else if(opt == 2){
int l , r , x;
scanf("%lld%lld%lld" , &l , &r , &x);
modify(1 , l , r , x);
}
else{
int l , r;
scanf("%lld%lld" , &l , &r);
printf("%lld\n" , query(1 , l , r));
}
}
return 0;
}
by Fwio_ @ 2023-06-20 15:38:12
@Link_Cut_Y emmm,其他都理解,这个为什么cover下放的时候要把add清0呢
by Link_Cut_Y @ 2023-06-20 16:04:34
@HVeo 因为你只要覆盖了,不管你原来 add
标记是多少,覆盖的都是同一个数。所以要把 add
清零。你也可以考虑不清零的情况。假设你不清零,那么 pushdown
进入下放 add
标记的时候,你就会在原来覆盖的基础上又加上 add
。这明显是不对的。
by Fwio_ @ 2023-06-20 16:05:34
@Link_Cut_Y 也就是说覆盖的优先级比增加高吗
by Link_Cut_Y @ 2023-06-20 16:05:57
@HVeo 是的。
by Link_Cut_Y @ 2023-06-20 16:06:17
@HVeo 必须要先下放覆盖然后才能下放 add
。