244 lines
9.3 KiB
C++
244 lines
9.3 KiB
C++
#include <cstdio>
|
||
#include <cstring>
|
||
#include <iostream>
|
||
using namespace std;
|
||
typedef long long LL;
|
||
const int N = 550000;
|
||
const int INF = 0x3f3f3f3f;
|
||
|
||
#define ls u << 1
|
||
#define rs u << 1 | 1
|
||
//快读
|
||
int read() {
|
||
int x = 0, f = 1;
|
||
char ch = getchar();
|
||
while (ch < '0' || ch > '9') {
|
||
if (ch == '-') f = -1;
|
||
ch = getchar();
|
||
}
|
||
while (ch >= '0' && ch <= '9') {
|
||
x = (x << 3) + (x << 1) + (ch ^ 48);
|
||
ch = getchar();
|
||
}
|
||
return x * f;
|
||
}
|
||
|
||
int n, m;
|
||
|
||
struct Node {
|
||
int l, r;
|
||
int mx, cx; //最大值，最大值个数
|
||
int sx; //次大值
|
||
int mi, ci; //最小值，最小值个数
|
||
int si; //次小值
|
||
LL sum; //区间和
|
||
int add1, add2, add3; //最小值增加，最大值增加，普通值增加
|
||
} tr[N << 2];
|
||
|
||
//向上推送统计信息，由左右儿子的统计信息更新父亲u的统计信息
|
||
void pushup(int u) {
|
||
tr[u].sum = tr[ls].sum + tr[rs].sum; //区间和
|
||
//更新最大值系列信息 mx,sx,cx
|
||
if (tr[ls].mx == tr[rs].mx) {
|
||
tr[u].mx = tr[ls].mx;
|
||
tr[u].cx = tr[ls].cx + tr[rs].cx;
|
||
tr[u].sx = max(tr[ls].sx, tr[rs].sx);
|
||
} else if (tr[ls].mx > tr[rs].mx) {
|
||
tr[u].mx = tr[ls].mx;
|
||
tr[u].cx = tr[ls].cx;
|
||
tr[u].sx = max(tr[ls].sx, tr[rs].mx);
|
||
} else if (tr[ls].mx < tr[rs].mx) {
|
||
tr[u].mx = tr[rs].mx;
|
||
tr[u].cx = tr[rs].cx;
|
||
tr[u].sx = max(tr[ls].mx, tr[rs].sx);
|
||
}
|
||
//更新最小值系列信息 mi,si,ci
|
||
if (tr[ls].mi == tr[rs].mi) {
|
||
tr[u].mi = tr[ls].mi;
|
||
tr[u].si = min(tr[ls].si, tr[rs].si);
|
||
tr[u].ci = tr[ls].ci + tr[rs].ci;
|
||
} else if (tr[ls].mi > tr[rs].mi) {
|
||
tr[u].mi = tr[rs].mi;
|
||
tr[u].ci = tr[rs].ci;
|
||
tr[u].si = min(tr[ls].mi, tr[rs].si);
|
||
} else if (tr[ls].mi < tr[rs].mi) {
|
||
tr[u].mi = tr[ls].mi;
|
||
tr[u].ci = tr[ls].ci;
|
||
tr[u].si = min(tr[ls].si, tr[rs].mi);
|
||
}
|
||
}
|
||
|
||
/*
|
||
k1:最小值增量,k2:最大值增量,k3:一般值增量
|
||
*/
|
||
void update(int u, int k1, int k2, int k3) {
|
||
/*
|
||
① 更新区间和
|
||
如果一个区间的值域很小（比如只有1或2个数），可能会发生一个值既是最大值又是次小值这种情况，也就是发生了数域的重叠.
|
||
这种情况要特判，分辨到底该被哪个标记作用。
|
||
*/
|
||
if (tr[u].mi == tr[u].mx) { // 只有一种值时，最大值等于最小值
|
||
// if (k1 == k3) k1 = k2;
|
||
// if (k2 == k3) k2 = k1;
|
||
|
||
// 不应被其他值的标记作用
|
||
if (k1 == k3)
|
||
k1 = k2;
|
||
else
|
||
k2 = k1;
|
||
tr[u].sum += (LL)k1 * tr[u].ci;
|
||
} else
|
||
//整体增量=最小值增量*个数+最大值增量*个数+普通值增量*个数
|
||
tr[u].sum += (LL)k1 * tr[u].ci + (LL)k2 * tr[u].cx + (LL)k3 * (tr[u].r - tr[u].l + 1 - tr[u].ci - tr[u].cx);
|
||
|
||
//② 更新次小
|
||
if (tr[u].si == tr[u].mx) //次小等于最大
|
||
tr[u].si += k2;
|
||
else if (tr[u].si != INF) //次小存在
|
||
tr[u].si += k3;
|
||
|
||
//③ 更新次大
|
||
if (tr[u].sx == tr[u].mi) //次大等于最小
|
||
tr[u].sx += k1;
|
||
else if (tr[u].sx != -INF) //次大存在
|
||
tr[u].sx += k3;
|
||
|
||
//④ 更新最小值，最大值
|
||
tr[u].mi += k1, tr[u].mx += k2;
|
||
|
||
//⑤ 向左右儿子传递懒标记add1,add2,add3
|
||
tr[u].add1 += k1, tr[u].add2 += k2, tr[u].add3 += k3;
|
||
}
|
||
|
||
//向下传递懒标记，一般是有新的更新操作，或者，有了查询操作时才这样做
|
||
void pushdown(int u) {
|
||
int mi = min(tr[ls].mi, tr[rs].mi);
|
||
int mx = max(tr[ls].mx, tr[rs].mx);
|
||
|
||
/*
|
||
k1:最小值增量,k2:最大值增量,k3:一般值增量
|
||
有三个lazy add标签，需要注意互相之间的影响关系:
|
||
① 修改区间最小值时要注意其对最大值、严格次大值的影响
|
||
② 修改区间最大值时要注意其对最小值、严格次小值的影响
|
||
*/
|
||
int k1, k2, k3 = tr[u].add3; //一般值没啥说道，直接传递给左右儿子就行
|
||
|
||
tr[ls].mi == mi ? k1 = tr[u].add1 : k1 = tr[u].add3; //左儿子中有最小值，k1=tr[u].add1,否则k1=tr[u].add3
|
||
tr[ls].mx == mx ? k2 = tr[u].add2 : k2 = tr[u].add3; //左儿子中有最大值，k2=tr[u].add2,否则k1=tr[u].add3
|
||
update(ls, k1, k2, k3); //标签纠正好了，可以更新左儿子了
|
||
|
||
//复读机
|
||
tr[rs].mi == mi ? k1 = tr[u].add1 : k1 = tr[u].add3; //右儿子中有最小值，k1=tr[u].add1,否则k1=tr[u].add3
|
||
tr[rs].mx == mx ? k2 = tr[u].add2 : k2 = tr[u].add3; //右儿子中有最大值，k2=tr[u].add2,否则k1=tr[u].add3
|
||
update(rs, k1, k2, k3); //标签纠正好了，可以更新右儿子了
|
||
|
||
//传递完了add lzay tag,重置为0，表示没的传了
|
||
tr[u].add1 = tr[u].add2 = tr[u].add3 = 0;
|
||
}
|
||
|
||
//构建线段树
|
||
void build(int u, int l, int r) {
|
||
tr[u].l = l, tr[u].r = r;
|
||
if (l == r) {
|
||
tr[u].mx = tr[u].mi = tr[u].sum = read(); //最大值，最小值，区间和
|
||
tr[u].cx = tr[u].ci = 1; //最大值个数=最小值个数=1
|
||
tr[u].sx = -INF; //没有次大值
|
||
tr[u].si = INF; //没有次小值
|
||
return;
|
||
}
|
||
int mid = (l + r) >> 1;
|
||
build(ls, l, mid), build(rs, mid + 1, r);
|
||
pushup(u);
|
||
}
|
||
|
||
//区间加
|
||
void modify_add(int u, int l, int r, int v) {
|
||
if (tr[u].l > r || tr[u].r < l) return; //无交集，直接返回
|
||
if (tr[u].l >= l && tr[u].r <= r) { //区间完整命中
|
||
update(u, v, v, v); //更新统计信息,最大值，最小值，一般值 都是一样的需要+v
|
||
return;
|
||
}
|
||
//① 未完全命中，存在部分交集，先将以前的tag传递给左右儿子，再开始递归左右儿子
|
||
pushdown(u);
|
||
//② 分裂处理左右儿子
|
||
modify_add(ls, l, r, v), modify_add(rs, l, r, v);
|
||
//③ 因为子节点信息更新了，需要向上汇集统计信息
|
||
pushup(u);
|
||
}
|
||
|
||
//区间修改最大值
|
||
void modify_max(int u, int l, int r, int v) {
|
||
if (tr[u].l > r || tr[u].r < l || v <= tr[u].mi) return; //如果区间无交集，或者，要更新的最大值还没有人家区间的最小值大，没有更新的必要
|
||
if (l <= tr[u].l && tr[u].r <= r && v < tr[u].si) { //如果区间完全命中，并且，v小于区间次小值，那么只能更新最小值
|
||
update(u, v - tr[u].mi, 0, 0);
|
||
//最小值被更新的大小=为add(v-tr[u].mi),如此，成功将设置为最小值操作转化为加法标签操作
|
||
return;
|
||
}
|
||
//① 未完全命中，存在部分交集，先将以前的tag传递给左右儿子，再开始递归左右儿子
|
||
pushdown(u);
|
||
//② 分裂处理左右儿子
|
||
modify_max(ls, l, r, v), modify_max(rs, l, r, v);
|
||
//③ 因为子节点信息更新了，需要向上汇集统计信息
|
||
pushup(u);
|
||
}
|
||
|
||
//区间修改最小值
|
||
void modify_min(int u, int l, int r, int v) {
|
||
if (tr[u].l > r || tr[u].r < l || v >= tr[u].mx) return; //如果区间无交集，或者，要更新的最小值还比人家区间的最大值还大，没有更新的必要
|
||
if (l <= tr[u].l && tr[u].r <= r && v > tr[u].sx) { //如果区间完全命中，并且，v大于区间次大值，那么只能更新最大值
|
||
update(u, 0, v - tr[u].mx, 0);
|
||
//最大值被更新的大小=为add(v-tr[u].mx),如此，成功将设置为最大值操作转化为加法标签操作
|
||
return;
|
||
}
|
||
//① 未完全命中，存在部分交集，先将以前的tag传递给左右儿子，再开始递归左右儿子
|
||
pushdown(u);
|
||
//② 分裂处理左右儿子
|
||
modify_min(ls, l, r, v), modify_min(rs, l, r, v);
|
||
//③ 因为子节点信息更新了，需要向上汇集统计信息
|
||
pushup(u);
|
||
}
|
||
|
||
//查询区间和
|
||
LL query_sum(int u, int l, int r) {
|
||
if (tr[u].l > r || tr[u].r < l) return 0;
|
||
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
|
||
pushdown(u);
|
||
return query_sum(ls, l, r) + query_sum(rs, l, r);
|
||
}
|
||
|
||
//区间最大值
|
||
int query_max(int u, int l, int r) {
|
||
if (tr[u].l > r || tr[u].r < l) return -INF;
|
||
if (l <= tr[u].l && tr[u].r <= r) return tr[u].mx;
|
||
pushdown(u);
|
||
return max(query_max(ls, l, r), query_max(rs, l, r));
|
||
}
|
||
|
||
//区间最小值
|
||
int query_min(int u, int l, int r) {
|
||
if (tr[u].l > r || tr[u].r < l) return INF;
|
||
if (l <= tr[u].l && tr[u].r <= r) return tr[u].mi;
|
||
pushdown(u);
|
||
return min(query_min(ls, l, r), query_min(rs, l, r));
|
||
}
|
||
|
||
int main() {
|
||
//文件输入输出
|
||
#ifndef ONLINE_JUDGE
|
||
freopen("BZOJ4695.in", "r", stdin);
|
||
#endif
|
||
n = read();
|
||
build(1, 1, n);
|
||
|
||
m = read();
|
||
while (m--) {
|
||
int op = read(), l = read(), r = read(), x;
|
||
if (op == 1) x = read(), modify_add(1, l, r, x); //区间加
|
||
if (op == 2) x = read(), modify_max(1, l, r, x); //区间修改max运算
|
||
if (op == 3) x = read(), modify_min(1, l, r, x); //区间修改min运算
|
||
if (op == 4) printf("%lld\n", query_sum(1, l, r)); //查询区间和
|
||
if (op == 5) printf("%d\n", query_max(1, l, r)); //查询区间最大值
|
||
if (op == 6) printf("%d\n", query_min(1, l, r)); //查询区间最小值
|
||
}
|
||
return 0;
|
||
} |