我是sb^^
用区间加、单点操作写的代码只用单点操作
H - Skyscraper
题意： 原数组
h
n
h_n
hn初始值均为0，给定数组
a
n
a_n
an是要求达到的值。现在可以选择下标
[
l
,
r
]
[l,r]
[l,r]进行区间
+
1
+1
+1的操作。
现在有两种操作：
1
l
r
k
1\ \ l \ \ r \ \ k
1 l r k表示对数组
a
l
,
a
l
+
1
,
.
.
.
.
,
a
r
a_l,a_{l+1},....\ ,a_r
al,al+1,.... ,ar进行
+
k
+k
+k的操作
2
l
r
2\ \ l \ \ r
2 l r表示询问要使得原数组
h
l
,
h
l
+
1
,
.
.
.
,
h
r
h_l,h_{l+1},\ ... \ ,h_r
hl,hl+1, ... ,hr恰好等于
a
l
,
a
l
+
1
,
.
.
.
.
,
a
r
a_l,a_{l+1},....\ ,a_r
al,al+1,.... ,ar的最小操作数
思路： 差分数组，设
d
i
=
a
i
−
a
i
−
1
d_i=a_{i}-a_{i-1}
di=ai−ai−1，可以这么思考
假如
d
i
≥
0
d_i\ge 0
di≥0，那么位置
i
i
i的高度必要一层层累上去，所以加入答案假如
d
i
<
0
d_i<0
di<0，那么位置
i
i
i的高度可以从前一个传过来，所以不用加到答案里 答案就是改变后的
a
l
+
∑
i
=
l
+
1
r
d
i
a_l+ \sum_{i=l+1}^{r} d_i
al+∑i=l+1rdi
这样思路就有了，维护两个数组：
经过操作
1
1
1进行区间加的数组
a
n
a_n
an在操作
1
1
1后只有单点
∗
2
*2
∗2(
d
l
+
k
,
d
r
+
1
−
k
d_l+k,d_{r+1}-k
dl+k,dr+1−k)改变的数组
d
n
d_n
dn
树状数组就能完成这两个操作。
用区间加、单点操作写的代码
LL a
[maxn
], n
, m
, ans
, d
[maxn
], c
[maxn
];
LL sum2
[maxn
], sum1
[maxn
];
LL
lowbit(LL x
) { return x
& (-x
); }
void update_bulk(LL i
, LL k
) {
LL x
= i
;
while (i
<= n
) {
sum1
[i
] += k
;
sum2
[i
] += k
* (x
- 1);
i
+= lowbit(i
);
}
}
LL
getsum_bulk(LL i
) {
LL res
= 0ll, x
= i
;
while (i
> 0) {
res
+= x
* sum1
[i
] - sum2
[i
];
i
-= lowbit(i
);
}
return res
;
}
void update(LL i
, LL k
) {
while (i
<= n
) {
c
[i
] += k
;
i
+= lowbit(i
);
}
}
LL
getsum(LL i
) {
LL res
= 0ll;
while (i
> 0) {
res
+= c
[i
];
i
-= lowbit(i
);
}
return res
;
}
void init() {
for (int i
= 0; i
<= n
+ 1; i
++) {
sum1
[i
] = 0ll; sum2
[i
] = 0ll; c
[i
] = 0ll;
}
}
int main() {
LL T
, op
;
LL l
, r
, k
;
scl(T
);
a
[0] = 0ll;
while (T
--) {
scl(n
); scl(m
);
init();
for (LL i
= 1; i
<= n
; i
++) {
scl(a
[i
]);
update_bulk(i
, a
[i
]);
if (i
< n
)update_bulk(i
+ 1, -a
[i
]);
d
[i
] = a
[i
] - a
[i
- 1];
if (d
[i
] > 0)update(i
, d
[i
]);
}
while (m
--) {
scl(op
);
if (op
== 1) {
scl(l
); scl(r
); scl(k
);
update_bulk(l
, k
);
update_bulk(r
+ 1, -k
);
if (d
[l
] > 0)update(l
, -1 * d
[l
]);
d
[l
] += k
;
if (d
[l
] > 0)update(l
, d
[l
]);
if (r
== n
)continue;
if (d
[r
+ 1] > 0)update(r
+ 1, -1 * d
[r
+ 1]);
d
[r
+ 1] -= k
;
if (d
[r
+ 1] > 0)update(r
+ 1, d
[r
+ 1]);
}
else {
scl(l
); scl(r
);
printf("%lld\n", getsum_bulk(l
) - getsum_bulk(l
- 1) + getsum(r
) - getsum(l
));
}
}
}
return 0;
}
只用单点操作
其实可以更加简单，因为
a
l
=
∑
i
=
1
l
d
i
a_l=\sum_{i=1}^{l} d_i
al=∑i=1ldi,所以只要维护两个数组，一个保证维护的数列为正，一个维护原差分数列。
LL a
[maxn
];
LL d
[maxn
];
LL c
[maxn
];
LL e
[maxn
];
LL n
, m
;
LL
lowbit(LL x
) { return x
& (-x
); }
void update(LL i
, LL k
, LL g
[]) {
while (i
<= n
) {
g
[i
] += k
;
i
+= lowbit(i
);
}
}
LL
getsum(LL i
, LL g
[]) {
LL res
= 0;
while (i
> 0) {
res
+= g
[i
];
i
-= lowbit(i
);
}
return res
;
}
void init() {
for (int i
= 0; i
<= n
+ 50; i
++) {
e
[i
] = 0; c
[i
] = 0;
}
}
int main() {
LL T
, op
;
LL l
, r
, k
;
scl(T
);
while (T
--) {
scl(n
); scl(m
);
init();
a
[0] = 0;
d
[0] = 0;
for (LL i
= 1; i
<= n
; i
++) {
scl(a
[i
]);
d
[i
] = a
[i
] - a
[i
- 1];
update(i
, d
[i
], e
);
if (d
[i
] > 0)update(i
, d
[i
], c
);
}
while (m
--) {
scl(op
); scl(l
); scl(r
);
if (l
> r
)swap(r
, l
);
if (op
== 1) {
scl(k
);
update(l
, k
, e
);
update(r
+ 1, -k
, e
);
if (d
[l
] > 0)update(l
, -1ll * d
[l
], c
);
d
[l
] += k
;
if (d
[l
] > 0)update(l
, d
[l
], c
);
if (d
[r
+ 1] > 0)update(r
+ 1, -1ll * d
[r
+ 1], c
);
d
[r
+ 1] -= k
;
if (d
[r
+ 1] > 0)update(r
+ 1, d
[r
+ 1], c
);
}
else {
printf("%lld\n", getsum(l
, e
) + getsum(r
, c
) - getsum(l
, c
));
}
}
}
return 0;
}
