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 谢谢