社区讨论
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 条回复,欢迎继续交流。
正在加载回复...