社区讨论

9分求大佬帮助(线段树)

P1438无聊的数列参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lojtvgsc
此快照首次捕获于
2023/11/04 17:14
2 年前
此快照最后确认于
2023/11/04 19:27
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int t[N << 2] , tag[N << 2] , k[N << 2];
int n , m , l , r , K , d , a[N];
void push_up(int p){
	t[p] = t[p << 1] + t[p << 1 | 1];
}
void add_tag(int p , int L , int R , int K , int d){
	tag[p] += d;
	k[p] += K;
	t[p] += (R - L + 1) * (K + K + (R - L) * d) / 2;
//	printf("p = %d , L = %d , R = %d , K = %d , d = %d , tag[%d] = %d , k[%d] = %d\n" , p , L , R , K , d , p , tag[p] , p , k[p]);
}
void push_down(int p , int L , int R){
	if(tag[p]){
		int mid = (L + R) >> 1;
		add_tag(p << 1 , L , mid , k[p] , tag[p]);
		add_tag(p << 1 | 1 , mid + 1 , R , k[p] + (mid - L + 1) * tag[p] , tag[p]);
		tag[p] = 0;
		k[p] = 0;
	}
}
void build(int p , int L , int R){
	if(L == R)t[p] = a[L];
	else {
		int mid = (L + R) >> 1;
		build(p << 1 , L , mid);
		build(p << 1 | 1 , mid + 1 , R);
		push_up(p);
	}
}
void updata(int p , int L , int R , int a , int b , int K , int d){
	if(a <= L && R <= b){
//		cout << 1 << endl; 
		add_tag(p , L , R , K , d);
	}
	else {
		push_down(p , L , R);
		int mid = (L + R) >> 1;
		if(a <= mid)updata(p << 1 , L , mid , a , b , K , d);
		if(b > mid)updata(p << 1 | 1 , mid + 1 , R , a , b , K + (mid - a + 1) * d , d);
		push_up(p);
	}
}
int query(int p , int L , int R , int a , int b){
	if(a <= L && R <= b){
		return t[p];
	}
	push_down(p , L , R);
	int mid = (L + R) >> 1;
	int res = 0;
	if(a <= mid)res = query(p << 1 , L , mid , a , b);
	if(b > mid)res += query(p << 1 | 1 , mid + 1 , R , a , b);
	return res;
}
signed main(){
	freopen("a.txt" , "r" , stdin);
	scanf("%lld%lld" , &n , &m);
	for(int i = 1;i <= n;i ++){
		scanf("%lld" , &a[i]);
	}
	build(1 , 1 , n);
	while(m --){
		int o;
		scanf("%lld" , &o);
		if(o == 1){
			scanf("%lld%lld%lld%lld" , &l , &r , &K , &d);
			updata(1 , 1 , n , l , r , K , d);
		}
		else {
			scanf("%lld" , &l);
			printf("%lld\n" , query(1 , 1 , n , l , l));
		}
	}
//	for(int i = 1;i <= n;i ++){
//		cout << query(1 , 1 , n , i , i) << " ";
//	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...