【线段树维护区间P次方和】HDU 2578 Transformation
2021-08-22 14:47:00 # ACM

题链

题目解析

题给操作包括：
  $1.$ 区间每个数 $+c$；
  $2.$ 区间每个数 $*c$；
  $3.$ 区间每个数变为 $c$；
  $4.$ 询问区间每个数的 $p$ 次方和 $(1<=p<=3)$；
三种操作都能转化为区间 $*k+b$ 的形式：
  $1.$ 区间每个数 $+c$ => $*1+c$
  $2.$ 区间每个数 $*c$；=> $*c+0$
  $3.$ 区间每个数变为 $c$；=> $*0+c$

考虑如何维护区间 $p$ 次方和；
将 $sum1,sum2,sum3$ 表示为区间和，平方和，次方和；
对于乘法操作：
  $1.$ $\sum_{i=l}^{r}a_ix = x\sum_{i=l}^{r}a_i$；
  $2.$ $\sum_{i=l}^{r}(a_ix)^2 = x^2\sum_{i=l}^{r}a_i^2$；
  $3.$ $\sum_{i=l}^{r}(a_ix)^3 = x^3\sum_{i=l}^{r}a_i^3$；
对于加法操作：
  $1.$ $\sum_{i=l}^{r}(a_i+x) = \sum_{i=l}^{r}a_i+(r-l+1)*x$；
  $2.$ $\sum_{i=l}^{r}(a_i+x)^2 = \sum_{i=l}^{r}a_i^2+2x\sum_{i=l}^{r}a_i+(r-l+1)x^2$；
  $3.$ $\sum_{i=l}^{r}(a_i+x)^3 = \sum_{i=l}^{r}a_i^3+3x\sum_{i=l}^{r}a_i^2+3x^2\sum_{i=l}^{r}a_i+(r-l+1)x^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
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
108
109
110
111
#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 10007
    #define MAXN 50001
    #define MS 100005
    
int n,m;
int a[MS];
struct node{
	LL sum1,sum2,sum3;
	LL add,mul;
}p[MS<<2];

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

void push_up(int rt){
	p[rt].sum1 = (p[ls].sum1 + p[rs].sum1)%mod;
	p[rt].sum2 = (p[ls].sum2 + p[rs].sum2)%mod;
	p[rt].sum3 = (p[ls].sum3 + p[rs].sum3)%mod;
}

void update(int rt,int l,int r,LL k,LL b){
	int len = r-l+1;
	if(k != 1){
		node t = p[rt];
		p[rt].sum3 = t.sum3*k*k*k%mod;
		p[rt].sum2 = t.sum2*k*k%mod;
		p[rt].sum1 = t.sum1*k%mod;
	}
	if(b){
		node t = p[rt];
		p[rt].sum3 = (t.sum3 + t.sum2*b*3 + t.sum1*b*b*3 + b*b*b*len)%mod;
		p[rt].sum2 = (t.sum2 + t.sum1*b*2 + b*b*len)%mod;
		p[rt].sum1 = (t.sum1 + b*len)%mod;
	}
	p[rt].mul = p[rt].mul*k%mod;
	p[rt].add = (p[rt].add*k+b)%mod; 
}

void push_down(int rt,int l,int r){
	int m = l+r>>1;
	update(ls,l,m,p[rt].mul,p[rt].add);
	update(rs,m+1,r,p[rt].mul,p[rt].add);
	p[rt].mul = 1, p[rt].add = 0;
}

void modify(int L,int R,int l,int r,int rt,int op,LL val){
	if(L <= l && r <= R){
		if(op == 1) update(rt,l,r,1,val);
		else if(op == 2) update(rt,l,r,val,0);
		else update(rt,l,r,0,val);
		return;
	}
	int m = l+r>>1;
	push_down(rt,l,r);
	if(m >= L) modify(L,R,l,m,ls,op,val);
	if(m <  R) modify(L,R,m+1,r,rs,op,val);
	push_up(rt);
}

LL query(int L,int R,int l,int r,int rt,int k){
	if(L <= l && r <= R){
		if(k == 1) return p[rt].sum1;
		else if(k == 2) return p[rt].sum2;
		else return p[rt].sum3;
	}
	int m = l+r>>1;
	push_down(rt,l,r);
	LL ans = 0;
	if(m >= L) ans = (ans + query(L,R,l,m,ls,k))%mod;
	if(m <  R) ans = (ans + query(L,R,m+1,r,rs,k))%mod;
	return ans;
}

void solve(){
	build(1,n,1);
	while(m--){
		int op,l,r,val;
		cin >> op >> l >> r >> val;
		if(op != 4) modify(l,r,1,n,1,op,val);
		else cout << query(l,r,1,n,1,val) << "\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(cin >> n >> m && n && m) solve();
    
    return 0;
}
/*


*/
Prev
2021-08-22 14:47:00 # ACM
Next