#include #include #include 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; }