最后三个点RE了 命名开了long long.....QWQ

P3372 【模板】线段树 1

zbhujiaqi @ 2022-11-23 00:13:44

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <list>
#include <climits>
#include <stack>
#include <bitset>
#include <deque>
#define int long long
using namespace std ;

const int LONG = 1e5 + 5 ;

int n , m ; 
int num[100005] ;

inline int read()
{
    char ch = getchar() ; int flag = 1 ; int res = 0 ;
    while(ch < '0' || ch > '9'){if(ch == '-') flag = -1 ; ch = getchar() ; }
    while(ch >= '0' && ch <= '9'){res *= 10 ; res += ch - '0' ; ch = getchar() ; }
    return flag * res ; 
}

struct seg {
    long long l , r , sum = 0 , lazy = 0 ;
} a[400005];

void build (int k , int l , int r)
{
    a[k].l = l ; a[k].r = r ; a[k].lazy = 0 ;
    if(l == r){a[k].sum = num[l] ; return ; }
    int mid = (l + r) >> 1 ;
    build(k << 1 , l , mid ) ;
    build(k << 1 | 1 , mid + 1 , r ) ;
    a[k].sum = a[k << 1].sum + a[k << 1 | 1].sum ;
}

void pushdown(int k)
{
    if(a[k].lazy)
    {
        a[k << 1].sum += (a[k << 1].r - a[k << 1].l + 1) * a[k].lazy ;
        a[k << 1 | 1].sum += (a[k << 1 | 1].r - a[k << 1 | 1].l + 1) * a[k].lazy ;
        a[k << 1].lazy += a[k].lazy ;
        a[k << 1 | 1].lazy += a[k].lazy ;
        a[k].lazy = 0 ;
    }
}

void add(int k , int l , int r , int ql , int qr , long long x)
{
    if(ql <= l && qr >= r){a[k].sum += (r - l + 1) * 1ll*x ; a[k].lazy += 1ll*x ; return ;}
    pushdown(k) ;
    int mid = (l + r) >> 1 ;
    if(ql <= mid)add(k << 1 , l , mid , ql , qr , x) ;
    if(qr > mid)add(k << 1 | 1 , mid + 1 , r , ql , qr , x) ;
    a[k].sum = a[k << 1].sum + a[k << 1 | 1].sum ; 
}

long long summ(int k , int l , int r , int ql , int qr)
{
    pushdown(k) ;
    if(ql <= l && qr >= r){return a[k].sum ;}

    int mid = (l + r) >> 1 ; long long ans = 0 ;
    if(ql <= mid)ans += summ(k << 1 , l , mid , ql , qr) ;
    if(qr > mid)ans += summ(k << 1 | 1 , mid + 1 , r , ql , qr) ;
    return ans ;
}

signed main ()
{
    std::ios::sync_with_stdio(false);
    //freopen ( "xxx.in" , "r" , stdin) ;
    //freopen ( "xxx.out" , "w" , stdout) ;
    n = read() ; m = read() ;
    int i = 0 ;
    for(i = 1 ; i <= n ; i++)num[i] = read() ;

    build(1 , 1 , n) ;

    int x , y , z ;   
    while(m--)
    {
        int t ; t = read() ;
        //for(i = 1 ; i < 10 ; i++ )cout << a[i].sum << "  " ;
        //cout << endl ;
        if(t == 1)
        {
            x = read() ; y = read() ; z = read() ;
            add(1 , 1 , n , x , y , z) ;
        }
        else
        {
            x = read() ; y = read() ;
            long long ans = 0 ; ans = summ(1 , 1 , n , x , y) ;
            printf("%1lld\n" , ans) ;
       }
    }
    //fclose (stdin) ;
    //fclose (stdout) ;
    return 0 ;
}

by zbhujiaqi @ 2022-11-23 00:16:26

自己调了一晚上,实在蚌埠住了


by zdl777 @ 2022-11-23 00:24:16

long long summ(int k , int l , int r , int ql , int qr)
{
    pushdown(k) ;
    if(ql <= l && qr >= r){return a[k].sum ;}
    int mid = (l + r) >> 1 ; long long ans = 0 ;
    if(ql <= mid)ans += summ(k << 1 , l , mid , ql , qr) ;
    if(qr > mid)ans += summ(k << 1 | 1 , mid + 1 , r , ql , qr) ;
    return ans ;
}

pushdown放在判断是否覆盖整个区间的后面

void add(int k , int l , int r , int ql , int qr , long long x)
{
    if(ql <= l && qr >= r){a[k].sum += (r - l + 1) * 1ll*x ; a[k].lazy += 1ll*x ; return ;}
    pushdown(k) ;
    int mid = (l + r) >> 1 ;
    if(ql <= mid)add(k << 1 , l , mid , ql , qr , x) ;
    if(qr > mid)add(k << 1 | 1 , mid + 1 , r , ql , qr , x) ;
    a[k].sum = a[k << 1].sum + a[k << 1 | 1].sum ; 
}

by zdl777 @ 2022-11-23 00:25:31

到叶子节点之前,标记已经下传到叶子节点了,叶子节点不需要pushdown,在叶子节点pushdown可能越界


by zdl777 @ 2022-11-23 00:26:23

long long summ(int k , int l , int r , int ql , int qr)
{

    if(ql <= l && qr >= r){return a[k].sum ;}

    int mid = (l + r) >> 1 ; long long ans = 0 ;
    pushdown(k) ;
    if(ql <= mid)ans += summ(k << 1 , l , mid , ql , qr) ;
    if(qr > mid)ans += summ(k << 1 | 1 , mid + 1 , r , ql , qr) ;
    return ans ;
}

复制错了,是这个qaq


by zbhujiaqi @ 2022-11-23 07:55:32

@zdl777 太感谢啦!不过我还想问个问题:如果我在pushdown中加上一个判断是否为叶子节点,是否可行,还是说这样不是最优解,谢谢[双手合十]


by zbhujiaqi @ 2022-11-23 07:58:57

@zdl777

void pushdown(int k)
{
    if(a[k].l ==a[k].r ){a[k].lazy = 0 ; return ;}

    if(a[k].lazy)
    {
        a[k << 1].sum += (a[k << 1].r - a[k << 1].l + 1) * a[k].lazy ;
        a[k << 1 | 1].sum += (a[k << 1 | 1].r - a[k << 1 | 1].l + 1) * a[k].lazy ;
        a[k << 1].lazy += a[k].lazy ;
        a[k << 1 | 1].lazy += a[k].lazy ;
        a[k].lazy = 0 ;
    }
}

如上,实测能过


by zdl777 @ 2022-11-23 08:54:11

@zbhujiaqi 可以,但没必要www


by zbhujiaqi @ 2022-11-23 09:41:48

@zdl777 谢谢


|