TLE求助
查看原帖
TLE求助
973480
封禁用户楼主2024/12/23 20:24
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m,w[maxn*4],a[maxn],x[maxn],y[maxn];
void pushup(int u){
	w[u]=w[u*2]+w[u*2+1];
	return;
}
void build(int u,int L,int R){
	if(L==R) w[u]=a[L];
	else{
		int mid=(L+R)>>1;
		build(u*2,L,mid);
		build(u*2+1,mid+1,R);
		pushup(u);
	}
	return;
}
bool inrange(int L,int R,int l,int r){
	return l<=L&&R<=r;
}
bool outrange(int L,int R,int l,int r){
	return L>r||R<l;
}
void maketag(int u,int add_x,int add_y,int len){
	x[u]+=add_x;
	y[u]+=add_y;
	int b=x[u]+y[u]*(len-1);
	w[u]+=(x[u]+b)*len/2;
}
void pushdown(int u,int L,int R,int add_x,int add_y){
	if(x[u]||y[u]){
		int mid=(L+R)>>1;
		maketag(u*2,x[u],y[u],mid-L+1);
		maketag(u*2+1,x[u],y[u],R-mid);
	} 
	x[u]=y[u]=0;
	return;
}
void update(int u,int L,int R,int l,int r,int add_x,int add_y){
	if(inrange(L,R,l,r)){
		maketag(u,add_x,add_y,R-L+1);
		return;
	}else{
		int mid=(L+R)>>1;
		pushdown(u,L,R,add_x,add_y);
		update(u*2,L,mid,l,r,add_x,add_y);
		update(u*2+1,mid+1,R,l,r,add_x,add_y);
		pushup(u);
	}
}
int query(int u,int L,int R,int k){
	if(L==k) return w[u];
	int mid=(L+R)>>1;
	pushdown(u,L,R,x[u],y[u]);
	query(u*2,L,mid,k);
	query(u*2+1,mid+1,R,k);
}
int main(){
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt;
		cin >> opt;
		if(opt==1){
			int l,r,k,d;
			cin >> l >> r >> k >> d;
			update(1,1,n,l,r,k,d);
		}else{
			int p;
			cin >> p;
			cout << query(1,1,n,p) << endl;
		}
	}
	return 0;
}
2024/12/23 20:24
加载中...