关于线段树
  • 板块灌水区
  • 楼主ssl_lwz
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/9/23 10:02
  • 上次更新2023/11/2 18:36:52
查看原帖
关于线段树
484751
ssl_lwz楼主2023/9/23 10:02

能否帮我实现以下功能:

opt=1时 将l至r修改为0

opt=2时 查询l至r的和

求改,玄关,万分感谢!!!

这份代码的hack:

5 3

1 2 3 4 5

1 1 2

2 2 3

输出5

#include <bits/stdc++.h>
#define cal t[p]=t[p<<1]+t[p<<1|1];
#define int long long
using namespace std;

const int N = 1e6 + 10;

int n,a[N],t[N],m,lta[N];

void build(int p,int l,int r){
	if(l==r){
		t[p]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	cal
} 
void push_d(int p,int l,int r){
	if(lta[p]==0)  return;
	int mid=(l+r)>>1;
	lta[p<<1]=lta[p];
	lta[p<<1|1]=lta[p];
	t[p<<1]=lta[p]*(mid-l+1);
	t[p<<1|1]=lta[p]*(r-mid);
	lta[p]=0;
}
void add(int p,int l,int r,int x,int y,int k){
	if(l>y||r<x)  return;
	if(x<=l&&y>=r){
		t[p]=(r-l+1)*k;
		lta[p]=k;
		return;
	}
	push_d(p,l,r);
	int mid=(l+r)>>1;
	add(p<<1,l,mid,x,y,k);
	add(p<<1|1,mid+1,r,x,y,k);
	cal
}
int ser(int p,int l,int r,int x,int y){
	if(l>y||r<x)  return 0;
	if(l>=x&&r<=y){
		return t[p];
	}
	else{
		int mid=(l+r)>>1;
		push_d(p,l,r);
		return ser(p<<1,l,mid,x,y)+ser(p<<1|1,mid+1,r,x,y);
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  cin>>a[i];
	build(1,1,n);
	for(int i=1,x,y,lx,k;i<=m;i++){
		cin>>lx>>x>>y;
		if(lx==1){
			cin>>k;
			add(1,1,n,x,y,k);
		}
		else{
			cout<<ser(1,1,n,x,y)<<endl;
		}
	}
	return 0;
}


2023/9/23 10:02
加载中...