如题= =自用模板
所有区间均为前闭后开
混合操作

混合操作适用于区间和问题 无论乘数是正是负 而如果求的是区间最值问题 只有乘数为非负数才可以 否则得记录最大值和最小值 因为乘一个负数会改变区间一致性 如 100 是 100 和 -400的最大值 乘以负的停留在上层的lazy标记 那么就是-100 但其实最大值是400
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
class SegTree1{
long[]tree=new long[400050];
long[]lazy=new long[400050];
int n;
SegTree1(int n_){
this.n=1;
while(n<n_){
n*=2;
}
Arrays.fill(tree, Integer.MIN_VALUE);
Arrays.fill(lazy, Integer.MIN_VALUE);
}
void pushdown(int num,int l,int r){
if(lazy[num]!=Integer.MIN_VALUE){
tree[num*2+1]=lazy[num];
tree[num*2+2]=lazy[num];
lazy[num*2+1]=lazy[num];
lazy[num*2+2]=lazy[num];
lazy[num]=Integer.MIN_VALUE;
}
/*区间求和
if(lazy[num]!=0){
tree[num*2+1]+=lazy[num]*((r+l)/2-l);
tree[num*2+2]+=lazy[num]*(r-(r+l)/2);
lazy[num*2+1]+=lazy[num];
lazy[num*2+2]+=lazy[num];
lazy[num]=0;
}*/
}
void update(int num,int l,int r,long add,int x,int y){
if(r<=x||l>=y)return;
if(l<=x&&r>=y){
tree[num]=add;
lazy[num]=add;
return;
}
pushdown(num,x,y);
update(num*2+1,l,r,add,x,(x+y)/2);
update(num*2+2,l,r,add,(x+y)/2,y);
tree[num]=Math.max(tree[num*2+1],tree[num*2+2]);
}
void regupdate(int l,int r,int add){
update(0,l,r,add,0,n);
}
long regquery(int l,int r){
return query(0,l,r,0,n);
}
long query(int num,int l,int r,int x,int y){
if(r<=x||l>=y)return 0;
if(l<=x&&r>=y){
return tree[num];
}
pushdown(num,x,y);
long left=query(num*2+1,l,r,x,(x+y)/2);
long right=query(num*2+2,l,r,(x+y)/2,y);
return Math.max(left, right);
}
}
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
//混合操作
class SegTree{
long[]tree=new long[100050];
long[]lazyadd=new long[100050];
long[]lazymut=new long[100050];
long[]lazyset=new long[100050];
int n;
long NINF=-0x3f3f3f3f3f3f3f3fL;
void init(int n_){
this.n=1;
while(n<n_){
n*=2;
}
Arrays.fill(tree, 0);
Arrays.fill(lazyadd, 0);
Arrays.fill(lazymut, 1);
Arrays.fill(lazyset, NINF);
}
void pushdown(int num,int l,int r){
if(lazyset[num]!=NINF){
tree[num*2+1]=lazyset[num];
tree[num*2+2]=lazyset[num];
lazyset[num*2+1]=lazyset[num];
lazyset[num*2+2]=lazyset[num];
lazyadd[num*2+1]=0;
lazyadd[num*2+2]=0;
lazymut[num*2+1]=1;
lazymut[num*2+2]=1;
lazyset[num]=NINF;
}
if(lazymut[num]!=1){
tree[num*2+1]*=lazymut[num];
tree[num*2+2]*=lazymut[num];
lazymut[num*2+1]*=lazymut[num];
lazymut[num*2+2]*=lazymut[num];
lazyadd[num*2+1]*=lazymut[num];
lazyadd[num*2+2]*=lazymut[num];
lazymut[num]=1;
}
if(lazyadd[num]!=0){
tree[num*2+1]+=lazyadd[num];
tree[num*2+2]+=lazyadd[num];
lazyadd[num*2+1]+=lazyadd[num];
lazyadd[num*2+2]+=lazyadd[num];
lazyadd[num]=0;
}
}
void regadd(int l,int r,long add){
add(0,l,r,add,0,n);
}
void regmut(int l,int r,long mut){
mut(0,l,r,mut,0,n);
}
void regset(int l,int r,long set){
set(0,l,r,set,0,n);
}
long regquery(int l,int r){
return query(0,l,r,0,n);
}

long query(int num,int l,int r,int x,int y){
if(r<=x||l>=y)return NINF;
if(l<=x&&r>=y){
return tree[num];
}
pushdown(num,x,y);
long left=query(num*2+1,l,r,x,(x+y)/2);
long right=query(num*2+2,l,r,(x+y)/2,y);
return Math.max(left, right);
}
void mut(int num,int l,int r,long mut,int x,int y){
if(r<=x||l>=y) return;
if(l<=x&&r>=y){
tree[num]=tree[num]*mut;
if(lazyadd[num]!=0)lazyadd[num]=lazyadd[num]*mut;
lazymut[num]=lazymut[num]*mut;
return;
}
pushdown(num,x,y);
mut(num*2+1,l,r,mut,x,(x+y)/2);
mut(num*2+2,l,r,mut,(x+y)/2,y);
tree[num]=Math.max(tree[num*2+1],tree[num*2+2]);
}
void add(int num,int l,int r,long add,int x,int y){
if(r<=x||l>=y)return;
if(l<=x&&r>=y){
tree[num]=tree[num]+add;
lazyadd[num]=lazyadd[num]+add;
return;
}
pushdown(num,x,y);
add(num*2+1,l,r,add,x,(x+y)/2);
add(num*2+2,l,r,add,(x+y)/2,y);
tree[num]=Math.max(tree[num*2+1],tree[num*2+2]);
}
void set(int num,int l,int r,long set,int x,int y){
if(r<=x||l>=y)return;
if(l<=x&&r>=y){
tree[num]=set;
lazyadd[num]=0;
lazymut[num]=1;
lazyset[num]=set;
return;
}
pushdown(num,x,y);
set(num*2+1,l,r,set,x,(x+y)/2);
set(num*2+2,l,r,set,(x+y)/2,y);
tree[num]=Math.max(tree[num*2+1],tree[num*2+2]);
}
}