P3372智慧做法RE0qwq

问题讨论区 普及段
1

image

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int sum;
    int lazy;
    int l;
    int r;
}tree[400005];
int n,a[100001],x,y,m,v,aa;
void jianshu(int id,int l,int r){
    tree[id].l=l;
    tree[id].r=r;
	if(l==r){
		tree[id].sum=a[l];
		return ;
	}
	int mid=(l+r)/2;
	jianshu(id*2,l,mid);
	jianshu(id*2+1,mid+1,r);
	tree[id].sum=(tree[id*2].sum+tree[id*2+1].sum);
}
void xiafa(int id){
    if(tree[id].lazy){
        tree[id*2].lazy+=tree[id].lazy;
        tree[id*2].sum+=(tree[id].lazy*(tree[id*2].r-tree[id*2].l+1));
        tree[id*2+1].lazy+=tree[id].lazy;
        tree[id*2+1].sum+=(tree[id].lazy*(tree[id*2+1].r-tree[id*2+1].l+1));
        tree[id].lazy=0;
    }
}
void qjgx(int id){
    if(tree[id].l<=x&&y>=tree[id].r){
        tree[id].lazy+=v;
        tree[id].sum+=v*(tree[id].r-tree[id].l+1);
    }
    xiafa(id);
    if(x<=tree[id*2].r) qjgx(id*2);
	if(y>=tree[id*2+1].l) qjgx(id*2+1);
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
int find(int id){
	if(tree[id].l<=x&&y>=tree[id].r) return tree[id].sum;
    xiafa(id);
	int ma=0;
	if(x<=tree[id*2].r) ma+=find(id*2);
	if(y>=tree[id*2+1].l) ma+=find(id*2+1);
	return ma;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	jianshu(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>aa;
		if(aa==2){
			cin>>x>>y;
			cout<<find(1)<<endl;
		}
		else{
			cin>>x>>y>>v;
			qjgx(1);
		}
	}
}

RE0qwq
P3372
题面
果然，线段树对于一个刚升到普及组的蒟蒻还是太超纲了。

2

bushi,有人吗?悬赏10个赞和一个解决方案

3

@卡皮巴拉 我表示疑惑 你真的是 @连晨皓 的小号吗？

4

是的

5

@卡皮巴拉 如果你是，你为什么要做线段树模板？

6

e…我自学一下线段树不行吗

7

这里判断错了

8

这里也错了

9

所以你的qjgx和find为啥不用mid??

10

@卡皮巴拉 为什么要自学？打开提高小班春季第三讲，你值得拥有！

11

关键是我也打不开呀qwq

12

开心了,RE0

#include<bits/stdc++.h>
using namespace std;
struct node{
    int sum;
    int lazy;
}tree[400005];
int n,a[100001],x,y,m,v,aa;
void jianshu(int id,int l,int r){
	if(l==r){
		tree[id].sum=a[l];
		return ;
	}
	int mid=(l+r)/2;
	jianshu(id*2,l,mid);
	jianshu(id*2+1,mid+1,r);
	tree[id].sum=(tree[id*2].sum+tree[id*2+1].sum);
}
void xiafa(int id,int l,int r){
    if(tree[id].lazy){
    	int mid=(l+r)/2;
        tree[id*2].lazy+=tree[id].lazy;
        tree[id*2].sum+=(tree[id].lazy*(mid-l+1));
        tree[id*2+1].lazy+=tree[id].lazy;
        tree[id*2+1].sum+=(tree[id].lazy*(r-mid+1));
        tree[id].lazy=0;
    }
}
void qjgx(int id,int l,int r){
    if(l<=x&&y>=r){
        tree[id].lazy+=v;
        tree[id].sum+=v*(r-l+1);
    }
    xiafa(id,l,r);
    int mid=(l+r)/2;
    if(x<=mid) qjgx(id*2,l,mid);
	if(y>mid) qjgx(id*2+1,mid+1,r);
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
int find(int id,int l,int r){
	if(l<=x&&y>=r) return tree[id].sum;
    xiafa(id,l,r);
	int ma=0,mid=(l+r)/2;
	if(x<=mid) ma+=find(id*2,l,mid);
	if(y>mid) ma+=find(id*2+1,mid+1,r);
	return ma;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	jianshu(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>aa;
		if(aa==2){
			cin>>x>>y;
			cout<<find(1,1,n)<<endl;
		}
		else{
			cin>>x>>y>>v;
			qjgx(1,1,n);
		}
	}
}
13

666，分开判断巨佬！！错了，快改！！

14

@卡皮巴拉 @卡皮巴拉

15

不用分开判断吧，而且我是蒟蒻！

16

我是说你分开判断了！！
改成这样啊，你都反了if(l<=x&&y<=r) return tree[id].sum;

17

e,你建树是不用存tree[id].l和tree[id].r么？？不然你后面更新用啥？？？

18

用lazy

19

RE0qwq

#include<bits/stdc++.h>
using namespace std;
struct node{
    int sum;
    int lazy;
}tree[400005];
int n,a[100001],x,y,m,v,aa;
void jianshu(int id,int l,int r){
	if(l==r){
		tree[id].sum=a[l];
		return ;
	}
	int mid=(l+r)/2;
	jianshu(id*2,l,mid);
	jianshu(id*2+1,mid+1,r);
	tree[id].sum=(tree[id*2].sum+tree[id*2+1].sum);
}
void xiafa(int id,int l,int r){
    if(tree[id].lazy){
    	int mid=(l+r)/2;
        tree[id*2].lazy+=tree[id].lazy;
        tree[id*2].sum+=(tree[id].lazy*(mid-l+1));
        tree[id*2+1].lazy+=tree[id].lazy;
        tree[id*2+1].sum+=(tree[id].lazy*(r-mid+1));
        tree[id].lazy=0;
    }
}
void qjgx(int id,int l,int r){
    if(l<=x&&y<=r){
        tree[id].lazy+=v;
        tree[id].sum+=v*(r-l+1);
    }
    xiafa(id,l,r);
    int mid=(l+r)/2;
    if(x<=mid) qjgx(id*2,l,mid);
	if(y>mid) qjgx(id*2+1,mid+1,r);
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
int find(int id,int l,int r){
	if(l<=x&&y<=r) return tree[id].sum;
    xiafa(id,l,r);
	int ma=0,mid=(l+r)/2;
	if(x<=mid) ma+=find(id*2,l,mid);
	if(y>mid) ma+=find(id*2+1,mid+1,r);
	return ma;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	jianshu(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>aa;
		if(aa==2){
			cin>>x>>y;
			cout<<find(1,1,n)<<endl;
		}
		else{
			cin>>x>>y>>v;
			qjgx(1,1,n);
		}
	}
}
20

不用的，只要递归传参就行了