线段树10pts

P1253 扶苏的问题

Fwio_ @ 2023-06-20 11:08:55

蒟蒻刚学线段树来搓这题,调了30min都没调出来,有没有大佬帮帮QwQ

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;
}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 Fwio_ @ 2023-06-20 16:11:43

@Link_Cut_Y emmm,我按您说的改了,可还是20pts


by Fwio_ @ 2023-06-20 16:12:04

Code:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1000010;
const long long INF = 1e9;
struct Node{
    int l , r;
    long long maxn , add , cover;
}tr[N << 2];
long long a[N] , n , m;
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] = Node{l , r , a[l] , 0 , 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 modify(int u , int l , int r , long long 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);
    }
}
void update(int u , int l , int r , long long x){
    if(tr[u].l >= l && tr[u].r <= r){
        tr[u].cover = x;
        tr[u].maxn = x;
        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 , x);
        else if(l > mid) update(u << 1 | 1 , l , r , x);
        else update(u << 1 , l , mid , x) , update(u << 1 | 1 , mid + 1 , r , x);
        pushup(u);
    }
}
long long 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;
    long long ans = -INF;
    if(r <= mid) ans = query(u << 1 , l , r);
    else if(l > mid) ans = query(u << 1 | 1 , l , r);
    else ans = max(max(query(u << 1 , l , mid) , ans) , query(u << 1 | 1 , mid + 1 , r));
    return ans;
}
int 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;
        cin >> opt;
        if(opt == 1){
            int l , r;
            long long x;
            scanf("%d%d%lld" , &l , &r , &x);
            update(1 , l , r , x);
        }
        else if(opt == 2){
            int l , r;
            long long x;
            scanf("%d%d%lld" , &l , &r , &x);
            modify(1 , l , r , x);
        }
        else{
            int l , r;
            scanf("%d%d" , &l , &r);
            printf("%lld\n" , query(1 , l , r));
        }
    }
    return 0;
}

by Link_Cut_Y @ 2023-06-20 16:13:44

@HVeo 我不是把 AC 代码发给你了吗?在上一页。


by Link_Cut_Y @ 2023-06-20 16:19:57

@HVeo 你的码风基本上没给你动,你对比对比哪里不一样就行了。


by Link_Cut_Y @ 2023-06-20 16:24:09

@HVeo pushdown 函数下放 add 有问题。

我调不动了。应该就只有这里的问题了。


by Fwio_ @ 2023-06-20 16:26:17

@Link_Cut_Y 太感谢您了,我好像懂为什么别人说线段树是最毒瘤的数据结构了


by Link_Cut_Y @ 2023-06-20 16:28:00

@HVeo 你听谁说的?

明明块状链表才是最毒瘤的数据结构/kk


by Fwio_ @ 2023-06-20 16:33:47

@Link_Cut_Y

块状链表是给一个链表分块吗,我没学过,问下您


by Fwio_ @ 2023-06-20 16:40:50

wtf,这是给人学的吗


by Link_Cut_Y @ 2023-06-20 16:58:12

@HVeo

你可以看一下我写的块状链表笔记:块状链表笔记

如果愿意,你可以留个赞。


上一页 | 下一页