默写线段树20分,跟正解对了发现没什么差别
查看原帖
默写线段树20分,跟正解对了发现没什么差别
363669
hwwqy楼主2022/8/9 23:15

求助,孩子已经疯了

#include<bits/stdc++.h>
#define int long long
#define ls x<<1
#define rs x<<1|1
#define MXN 100100
using namespace std;
int sum[MXN*8],tag[MXN*8],a[MXN],n,m;
void update(int l,int r,int x)
{
	if(l!=r)
	{
		sum[x]=sum[ls]+sum[rs];
	}
}
void build(int l,int r,int x)
{
	
	if(l==r)
	{
		sum[x]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	update(l,r,x);
}
void pushdown(int l,int r,int x)
{
	int mid=l+r>>1;
	if(tag[x]==0)return ;
	if(l!=r)
	{
		sum[ls]+=tag[x]*(mid-l+1);
		sum[rs]+=tag[x]*(r-mid);
		tag[ls]+=tag[x];
		tag[rs]+=tag[x];
	}
	tag[x]=0;
}
int query(int ql,int qr,int l,int r,int x)
{
	int mid=l+r>>1;
	pushdown(l,r,x);
	if(l==ql&&r==qr)return sum[x];
	if(qr<=mid)return query(ql,qr,l,mid,ls);
	else if(ql>mid)return query(ql,qr,mid+1,r,rs);
	else return query(ql,mid,l,mid,ls)+query(mid+1,qr,mid+1,r,rs);
}
void add(int ql,int qr,int l,int r,int x,int k)
{
	if(l>=ql&&r<=qr)
	{
		tag[x]+=k;
		sum[x]+=(r-l+1)*k;
		return;
	}
	int mid=l+r>>1;
	pushdown(l,r,x);
	if(qr<=mid)add(ql,qr,l,mid,ls,k);
	else if(ql>mid)add(ql,qr,mid+1,r,rs,k);
	else add(ql,mid,l,mid,ls,k),add(mid+1,qr,mid+1,qr,rs,k);
	update(l,r,x);
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n,1);
	//cout<<sum[1]<<endl;
	for(int i=1;i<=m;i++)
	{
		int x,y,k,cmd;
		cin>>cmd>>x>>y;
		if(cmd==1)
		{
			cin>>k;
			add(x,y,1,n,1,k);
		}
		else
		{
			cout<<query(x,y,1,n,1)<<endl;
		}
	}
    return 0;
}

2022/8/9 23:15
加载中...