蒟蒻线段树求调
查看原帖
蒟蒻线段树求调
321647
阿炜楼主2022/10/15 19:16

输出的是一个极大的值

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
const int Maxx=100020;
int a[Maxx];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct STree{
	int  l,r;
	long long dat,add;
} t[Maxx*4+2];
void build(int l,int r,int p) //bulie tree
{
	t[p].l = l;
	t[p].r = r;
	if(l==r) {
		t[p].dat = a[l];
		return ;
	}
	int mid=l+r>>1;
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
	t[p].dat = t[p*2].dat + t[p*2+1].dat; //??????
}
void spread(int p){
	if(t[p].add ){
		t[p*2].dat+=t[p].add*(t[p*2].r-t[p*2].l+1);
		t[p*2+1].dat+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
		t[p*2].add+=t[p].add ;
		t[p*2+1].add+=t[p].add;
		t[p].add=0;//?????????????0
	}
}
void change(int p,int x,int y,int z)
{
	if(x<=t[p].l&&y>=t[p].r){
		t[p].dat+=(long long)z*(t[p].r-t[p].l+1);
		t[p].add+=z;
		return;
	}
	spread(p);
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid) change(p*2,x,y,z);
	if(y>mid) change(p*2+1,x,y,y);
	t[p].dat =t[p*2].dat+t[p*2+1].dat;
}
long long ask(int p,int x,int y)
{
	if(x<=t[p].l&&y>=t[p].r) return t[p].dat ;
	spread(p);
	int mid=t[p].l+t[p].r>>1;
	long long ans;
	if(x<=mid) ans+=ask(p*2,x,y);
	if(y>mid) ans+=ask(p*2+1,x,y);
	return ans;
}
int main()
{
	int n,m;
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	build(1,n,1);
	for(int i=1;i<=m;i++)
	{
		int q,x,y,z;
		q=read();
		if(q==1)
		{
			x=read();
			y=read();
			z=read();
			change(1,x,y,z);
		}else{
			x=read();
			y=read();
			cout<<ask(1,x,y)<<endl;
		}
	}
	return 0;
}
2022/10/15 19:16
加载中...