KevinHu0402 @ 2024-04-11 16:11:34
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
struct SegmentTree{
int l,r;
long long sum,add;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
}tree[maxn * 4];
int a[maxn],n,m;
void build(int p,int l,int r){
l(p) = l;
r(p) = r;
if(l == r){
sum(p) = a[l];
return;
}
int mid = (l + r) / 2;
build(p * 2,l,mid);
build(p * 2 + 1,mid + 1,r);
sum(p) = sum(p * 2) + sum(p * 2 + 1);
}
void push_down(int p){
if(add(p)){
sum(p * 2) += add(p) * (r(p * 2) - l(p * 2) + 1);
sum(p * 2 + 1) += add(p) * (r(p * 2 + 1) - l(p * 2 + 1) + 1);
add(p * 2) += add(p);
add(p * 2 + 1) += add(p);
add(p) = 0;
}
}
void change(int p,int l,int r,int d){
if(l <= l(p) && r >= r(p)){
sum(p) += (long long)d * (r(p) - l(p) + 1);
add(p) += d;
return;
}
push_down(p);
int mid = (l(p) + r(p)) / 2;
if(l <= mid) change(p * 2,l,r,d);
if(r > mid) change(p * 2 + 1,l,r,d);
sum(p) = sum(p * 2) + sum(p * 2 + 1);
}
long long query1(int p,int l,int r){//一次方查找
if(l <= l(p) && r >= r(p)) return sum(p);
push_down(p);
int mid = (l(p) + r(p)) / 2;
long long val = 0;
if(l <= mid) val += query1(p * 2,l,r);
if(r > mid) val += query1(p * 2 + 1,l,r);
return val;
}
long long query2(int p,int l,int r){//二次方查找
if(l <= l(p) && r >= r(p)) return sum(p);
push_down(p);
int mid = (l(p) + r(p)) / 2;
long long val = 0;
if(l <= mid) val += query2(p * 2,l,r) * query2(p * 2,l,r);
if(r > mid) val += query2(p * 2 + 1,l,r) * query2(p * 2 + 1,l,r);
return val;
}
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
int opt;
for(int i = 1;i < m;i++){
cin >> opt;
if(opt == 1){
int x,y,k;
cin >> x >> y >> k;
change(1,x,y,k);
}
if(opt == 2){
int x,y;
cin >> x >> y;
cout << query1(1,x,y) << endl;
}
}
return 0;
}by KevinHu0402 @ 2024-04-11 16:12:08
WA on 5,8
by mlvx @ 2024-04-11 16:39:59
@KevinHu0402 参考一下我的
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pl (p<<1)
#define pr (p<<1|1)
const int N=1e5+100;
struct Tree{ll lz,sum;}tr[N<<2];
int n,q,op,l,r,k,a[N];
void push_down(int p){tr[pl].lz+=tr[p].lz,tr[pr].lz+=tr[p].lz,tr[p].lz=0;}
void push_up(int l,int mid,int r,int p){tr[p].sum=tr[pl].sum+tr[pl].lz*(mid-l+1)+tr[pr].sum+tr[pr].lz*(r-mid);}
void update(int l,int r,int le,int ri,int v,int p){
if(l>=le&&r<=ri)return tr[p].lz+=v,void();
int mid=l+r>>1;
push_down(p);
if(le<=mid)update(l,mid,le,ri,v,pl);
if(ri>mid)update(mid+1,r,le,ri,v,pr);
push_up(l,mid,r,p);
}ll query(int l,int r,int le,int ri,int p){
if(l>=le&&r<=ri)return tr[p].sum+tr[p].lz*(r-l+1);
int mid=l+r>>1;ll ret=0;
push_down(p);
if(le<=mid)ret+=query(l,mid,le,ri,pl);
if(ri>mid)ret+=query(mid+1,r,le,ri,pr);
push_up(l,mid,r,p);
return ret;
}void build(int l,int r,int p){
if(l==r)return tr[p].sum=a[l],void();
int mid=l+r>>1;
build(l,mid,pl),build(mid+1,r,pr),tr[p].sum=tr[pl].sum+tr[pr].sum;;
}int main(){
cin>>n>>q;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,n,1);
while(q--){
scanf("%d",&op);
if(op==1)scanf("%d%d%d",&l,&r,&k),update(1,n,l,r,k,1);
if(op==2)scanf("%d%d",&l,&r),printf("%lld\n",query(1,n,l,r,1));
}return 0;
}by revolutionary_oier @ 2024-04-11 16:52:54
@KevinHu0402 在主函数中的for(int i=1;i<m;i++) 改为 for(int i=1;i<=m;i++)，就对了
by KevinHu0402 @ 2024-04-12 17:24:44
已关，谢谢