题解：P10516 数据结构

题意：

实现区间修改，单点加

val

，以及区间查询

sum

。

思路：

很明显，对于区间操作，我们选择线段树，具体记录数据如下：

CPP

struct segment{
	int l,r;
	//区间左右端点l,r
	int sum,minn;
    //区间和sum，区间最小值minn    
}t[N<<2];

对于操作 1，我们要记录区间区间 $\min$ ，通过与 $k$ 进行比较判断该区间是否进行修改（特判一下如果 $val$ 值为零就跳过，没必要进行无意的计算）。
对于操作 2，只需要找到对应的位置进行修改。
对于操作 3，计算统计好的区间 $sum$ 。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
inline void read(int &a){
	char ch;int f=1,k=0;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
	a=k*f;
}

struct segment{
	int l,r;
	int sum,minn;
}t[N<<2];

int a[N],b[N],n,m;

void push_up(int p){
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
	t[p].minn=min(t[p<<1].minn,t[p<<1|1].minn);
}
//建树 
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].minn=a[l]*b[l];
		t[p].sum=a[l]+b[l];
		return ;
	}
	int mid=l+r >>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
//op==1
void modify(int p,int l,int r,int k,int val){
	if(t[p].minn>k) return ;
	if(t[p].l==t[p].r){
		a[t[p].l]+=val,b[t[p].l]+=val;
		t[p].sum=a[t[p].l]+b[t[p].l];
		t[p].minn=a[t[p].l]*b[t[p].l];
		return ;
	}
	int mid=t[p].l+t[p].r>>1;
	if(l<=mid) modify(p<<1,l,r,k,val);
	if(r>=mid+1) modify(p<<1|1,l,r,k,val);
	push_up(p);
}

//op==2
void update(int p,int i,int x,int y){
	if(t[p].l==t[p].r){
		a[i]=x,b[i]=y;
		t[p].minn=x*y;
		t[p].sum=x+y;
		return ;
	}
	int mid=t[p].l+t[p].r>>1;
	if(i<=mid) update(p<<1,i,x,y);
	else if(i>=mid+1) update(p<<1|1,i,x,y);
	push_up(p);
}
//op==3
int query(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r){
		return t[p].sum;
	}
	int mid=t[p].l+t[p].r>>1,res=0;
	if(l<=mid) res+=query(p<<1,l,r);
	if(r>=mid+1) res+=query(p<<1|1,l,r);
	return res;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) read(b[i]);
	int op;
	build(1,1,n);
	while(m--){
		read(op);
		if(op==1){
			int l,r,k,t;
			read(l),read(r),read(k),read(t);
			if(!t) continue;
			modify(1,l,r,k,t);
		}
		else if(op==2){
			int i,x,y;
			read(i),read(x),read(y);
			update(1,i,x,y);
		}
		else if(op==3){
			int l,r;
			read(l),read(r);
			cout<<query(1,l,r)<<"\n";
		}
	} 
	return 0;
}

题解：P10516 数据结构

文章操作

题意：

思路：

Code

相关推荐

评论

题解：P10516 数据结构