【线段树维护区间加等差数列】洛谷 P1438 无聊的数列
2021-08-21 21:41:00 # ACM

题链

方式一

将原数组差分，区间 $[L,R]$ 加等差数列变为：
  $1.$ 在原数组 $L$ 的位置 $+k$；
  $2.$ 在原数组 $[L+1,R]$ 的位置 $+d$；
  $3.$ 在原数组 $R+1$ 的位置 $-(d*(R-L)+k)$；
询问变为：求区间 $[1,pos]$ 的和；
线段树区间修改，区间求和； 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
    #define Pair pair<LL ,LL >
    #define ls rt<<1
    #define rs rt<<1|1
    #define PI acos(-1.0)
    #define eps 1e-13
    #define mod 998244353
    #define MAXN 50001
    #define MS 100005
    
int n,m;
int a[MS];
struct node{
	LL val;
	LL la;
}p[MS<<2];

void push_up(int rt){
	p[rt].val = p[ls].val + p[rs].val;
}

void push_down(int rt,int l,int r){
	if(p[rt].la){
		int m = l+r>>1;
		p[ls].val += p[rt].la*(m-l+1);
		p[rs].val += p[rt].la*(r-m);
		p[ls].la += p[rt].la;
		p[rs].la += p[rt].la;
		p[rt].la = 0;
	}
}

void build(int l,int r,int rt){
	if(l == r){
		p[rt].val = a[l] - a[l-1];
		return;
	}
	int m = l+r>>1;
	build(l,m,ls);
	build(m+1,r,rs);
	push_up(rt);
}

void modify(int L,int R,int l,int r,int rt,LL val){
	if(L <= l && r <= R){
		p[rt].val += val*(r-l+1);
		p[rt].la += val;
		return;
	}
	int m = l+r>>1;
	push_down(rt,l,r);
	if(m >= L) modify(L,R,l,m,ls,val);
	if(m <  R) modify(L,R,m+1,r,rs,val);
	push_up(rt);
}

LL query(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		return p[rt].val;
	}
	int m = l+r>>1;
	push_down(rt,l,r);
	LL ans = 0;
	if(m >= L) ans += query(L,R,l,m,ls);
	if(m <  R) ans += query(L,R,m+1,r,rs);
	return ans;
}

inline void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	build(1,n,1);
	while(m--){
		int op;
		cin >> op;
		if(op == 1){
			LL l,r,k,d;
			cin >> l >> r >> k >> d;
			modify(l,l,1,n,1,k);
			if(l+1<=r) modify(l+1,r,1,n,1,d);
			if(r+1<=n) modify(r+1,r+1,1,n,1,-(d*(r-l)+k));
		}
		else if(op == 2){
			int pos; cin >> pos;
			cout << query(1,pos,1,n,1) << "\n";
		}
	}
} 

int main() {
    ios::sync_with_stdio(false);
//	srand((unsigned)time(0));
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
    int ce = 1;
//    cin >> ce;
//    scanf("%d",&ce);
    while(ce--) solve();
    
    return 0;
}
/*


*/

方式二

在线段树上打永久标记，节点有两个信息，节点区间的首项以及公差，修改时维护节点首项公差即可；
例如：

数列：1 2 3 4 5，首项为 1，公差为 1；
数列：1 3 5 7 9，首项为 1，公差为 2；
将两个数列相加得到：
数列 2 5 8 11 14，首项为 2，公差为 3；

求和的时候带着标记向下求； 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
    #define Pair pair<LL ,LL >
    #define ls rt<<1
    #define rs rt<<1|1
    #define PI acos(-1.0)
    #define eps 1e-13
    #define mod 998244353
    #define MAXN 50001
    #define MS 100005
    
int n,m;
struct node{
	LL S,D;
}p[MS<<2];

void build(int l,int r,int rt){
	if(l == r){
		cin >> p[rt].S;
		return;
	}
	int m = l+r>>1;
	build(l,m,ls);
	build(m+1,r,rs);
}

void modify(int L,int R,int l,int r,int rt,LL valS,LL valD){
	if(L <= l && r <= R){
		p[rt].S += valS+(l-L)*valD;
		p[rt].D += valD;
		return;
	}
	int m = l+r>>1;
	if(m >= L) modify(L,R,l,m,ls,valS,valD);
	if(m <  R) modify(L,R,m+1,r,rs,valS,valD);
}

LL query(int pos,int l,int r,int rt,LL val){
	val += p[rt].S+1LL*(pos-l)*p[rt].D;
	if(l == r) return val;
	int m = l+r>>1;
	if(m >= pos) return query(pos,l,m,ls,val);
	else return query(pos,m+1,r,rs,val);
}

inline void solve(){
	cin >> n >> m;
	build(1,n,1);
	while(m--){
		int op;
		cin >> op;
		if(op == 1){
			LL l,r,k,d;
			cin >> l >> r >> k >> d;
			modify(l,r,1,n,1,k,d);
		}
		else if(op == 2){
			int pos; cin >> pos;
			cout << query(pos,1,n,1,0) << "\n";
		}
	}
} 

int main() {
    ios::sync_with_stdio(false);
//	srand((unsigned)time(0));
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
    int ce = 1;
//    cin >> ce;
//    scanf("%d",&ce);
    while(ce--) solve();
    
    return 0;
}
/*


*/
Prev
2021-08-21 21:41:00 # ACM
Next