题解 | #快速求和反应训练#

线段树模板题

#include<bits/stdc++.h>
using namespace std;
int n,q;
const int M=2e5+5;
typedef long long ll;
ll a[M];
ll tree[M<<2];
ll tag[M<<2];
ll ls(ll p){
	return p<<1;
}
ll rs(ll p){
	return p<<1|1;
}
void pushup(ll p){
	tree[p]=tree[ls(p)]+tree[rs(p)];
}
void pushdown(ll p,ll pl,ll pr){
	tag[ls(p)]=tag[rs(p)]=tag[p];
	ll mid=(pl+pr)>>1;
	tree[ls(p)]=tag[p]*(mid-pl+1);
	tree[rs(p)]=tag[p]*(pr-mid);
	tag[p]=0;
}
void build(ll p,ll pl,ll pr){
	if(pl==pr){
		tree[p]=a[pl];
		return;
	}
	ll mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	pushup(p); 
}
void update(ll p,ll pl,ll pr,ll L,ll R,ll d){
	if(L<=pl&&R>=pr){
		tag[p]=d;
		tree[p]=d*(pr-pl+1);
		return ;
	}
	if(tag[p]) pushdown(p,pl,pr);
	ll mid=(pl+pr)>>1;
	if(L<=mid)
		update(ls(p),pl,mid,L,R,d);
	if(R>mid)
		update(rs(p),mid+1,pr,L,R,d);
	pushup(p); 
}

ll query(ll p,ll pl,ll pr,ll L,ll R){
	ll res=0;
	if(L<=pl&&R>=pr){
		return tree[p];
	}
	if(tag[p])	pushdown(p,pl,pr);
	ll mid=(pl+pr)>>1;
	if(L<=mid)
		res+=query(ls(p),pl,mid,L,R);
	if(R>mid)
		res+=query(rs(p),mid+1,pr,L,R);
		
	return res;
}

int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=q;i++){
		int t;
		cin>>t;
		if(t==1){
			int ind,x;
			cin>>ind>>x;
			update(1,1,n,ind,ind,x);
			cout<<query(1,1,n,1,n)<<endl;
		}
		if(t==2){
			int x;
			cin>>x;
			update(1,1,n,1,n,x);
			cout<<query(1,1,n,1,n)<<endl;
		}
	}
	return 0;
}