\(BZOJ4695\). 最假女选手
一、题目描述
给定一个长度为 \(N\) 序列，编号从 \(1\) 到 \(N\) 。要求支持下面几种操作：
- 给一个区间\([L,R]\) 加上一个数\(x\)
- 把一个区间\([L,R]\) 里小于\(x\) 的数变成\(x\)
- 把一个区间\([L,R]\) 里大于\(x\) 的数变成\(x\)
- 求区间\([L,R]\)的和
- 求区间\([L,R]\)的最大值
- 求区间\([L,R]\)的最小值
输入
第一行一个整数 \(N\) 表示序列长度。
第二行 \(N\) 个整数 \(A_i\) 表示初始序列。
第三行一个整数 \(M\) 表示操作个数。
接下来 \(M\) 行，每行三或四个整数，第一个整数 \(Tp\) 表示操作类型，接下来 \(L,R,X\) 或 \(L,R\) 表述操作数。
\(1<=tp<=6,N,M<=5*10^5,|Ai|<=10^8\)
\(Tp=1\)时,\(|x|<=1000\)
\(Tp=2\)或\(3\)时，\(|x|<=10^8\)
输出
对于每个\(4,5,6\)类型的操作输出一行一个整数表示答案。
样例输入
2
1 2
2
2 1 2 2
4 1 2
样例输出
4
二、解题思路
线段树区间最值操作
吉老师的\(Segment\) \(tree\) \(Beats!\) 中的题。
维护:
- 区间最小值
- 最小值个数
- 严格次小值
- 最大值
- 最大值个数
- 严格次大值
- 区间和
- 区间加和标记
即可。。。
注意: 修改区间最小值时要注意其对最大值、严格次大值是否有影响，修改区间最大值时要注意其对最小值、严格次小值的影响。
想想都觉得麻烦。。。
时间复杂度 \(O(nlog^2n)\)
注意本题略微卡常，不能全用\(long\) \(long\)，只有区间和使用\(long\) \(long\)维护。
三、实现代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
//快读
char buf[1 << 23], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
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;
}
#define ls u << 1
#define rs u << 1 | 1
const int N = 500010;
const int INF = 0x3f3f3f3f;
int n, m;
struct Node {
int l, r;
int mx, cx; //最大值，最大值个数
int sx; //次大值
int mi, ci; //最小值，最小值个数
int si; //次小值
LL sum; //区间和
LL tag; // lazy tag,是不是有未消费掉的add修改标记
} 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);
}
}
//构建线段树
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);
}
//将区间内所有数字更新为 max(a[i],v)
bool update_max(int u, int v) {
//① 区间最小值都大于v,不需要进入区间
if (tr[u].mi >= v) return true;
//② 如果区间内数字都是一样的
if (tr[u].mx == tr[u].mi) {
tr[u].mx = tr[u].mi = v;
tr[u].cx = tr[u].ci = tr[u].r - tr[u].l + 1;
tr[u].sx = -INF, tr[u].si = INF;
tr[u].sum = (LL)tr[u].cx * v;
return true;
}
//③ 如果区间次小值大于v,只能更新最小值
if (tr[u].si > v) {
tr[u].sum += (LL)tr[u].ci * (v - tr[u].mi);
tr[u].mi = v;
tr[u].sx = max(tr[u].sx, v);
tr[u].mx = max(tr[u].mx, v);
return true;
}
//④ 以上情况都不是，那么讨论不清楚，只能是继续递归左右儿子，在子区间内尝试上面的三种情况更新
return false;
}
//将区间内所有数字更新为 min(a[i],v)
bool update_min(int u, int v) {
//① 区间最大值都小于v,不需要进入区间
if (tr[u].mx <= v) return true;
//② 如果区间内数字都是一样的
if (tr[u].mx == tr[u].mi) {
tr[u].mx = tr[u].mi = v;
tr[u].cx = tr[u].ci = tr[u].r - tr[u].l + 1;
tr[u].sx = -INF, tr[u].si = INF;
tr[u].sum = (LL)tr[u].cx * v;
return true;
}
//③ 如果区间次大值小于v,只能更新最大值
if (tr[u].sx < v) {
tr[u].sum -= (LL)tr[u].cx * (tr[u].mx - v);
tr[u].mx = v;
tr[u].si = min(tr[u].si, v);
tr[u].mi = min(tr[u].mi, v);
return true;
}
//④ 以上情况都不是，那么讨论不清楚，只能是继续递归左右儿子，在子区间内尝试上面的三种情况更新
return false;
}
//整体命中时，区间每个数都要加上v,修改u节点的统计信息，并且传递tag懒标记
void update_add(int u, int v) {
//① 最大值，最小值，次大值，次小值都会受到影响，都要加上v
tr[u].mx += v, tr[u].mi += v, tr[u].sx += v, tr[u].si += v;
//② 区间和也需要进行整体更新
tr[u].sum += (LL)v * (tr[u].r - tr[u].l + 1); //为防止乘法受成的int溢出，需要先强制转换为LL
//③ 区间加的tag懒标记需要标识在此区间上，并没有真的一路更新到叶子节点
tr[u].tag += v;
}
//向下传递懒标记，一般是有新的更新操作，或者，有了查询操作时才这样做
void pushdown(int u) {
if (tr[u].tag) { //如果区间加懒标记不为0，表示存在懒标记，需要通过update_add传递给左右儿子
//主要的目标有两个：1、根据懒标记实时更新左右儿子的统计信息；2、左右儿子继承写上父亲的区间加懒标记
update_add(ls, tr[u].tag), update_add(rs, tr[u].tag);
//传递完毕，父节点区间加懒标记清零
tr[u].tag = 0;
}
//其实本题的懒标记不只是区间加的tag,还有最大值tag和最小值tag,只不过没有显示的写出来
//① 如果父亲的最大值标签信息，比左儿子的最大值小，这就是有问题，需要用tr[u].mx 对左儿子取min操作
if (tr[ls].mx > tr[u].mx) update_min(ls, tr[u].mx);
//② 如果父亲的最大值标签信息，比右儿子的最大值小，这就是有问题，需要用tr[u].mx 对右儿子取min操作
if (tr[rs].mx > tr[u].mx) update_min(rs, tr[u].mx);
//③ 如果父亲的最小值标签信息，比左儿子的最小值大，这就是有问题，需要用tr[u].mi 对左儿子取max操作
if (tr[ls].mi < tr[u].mi) update_max(ls, tr[u].mi);
//④ 如果父亲的最小值标签信息，比右儿子的最小值大，这就是有问题，需要用tr[u].mi 对右儿子取max操作
if (tr[rs].mi < tr[u].mi) update_max(rs, tr[u].mi);
}
//区间加
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_add(u, v); //更新统计信息+修改tag懒标记
return;
}
//① 未完全命中，存在部分交集，先将以前的tag传递给左右儿子，再开始递归左右儿子
pushdown(u);
//② 分裂处理左右儿子
modify_add(ls, l, r, v), modify_add(rs, l, r, v);
//③ 因为子节点信息更新了，需要向上汇集统计信息
pushup(u);
}
//更新最大值操作，拆分成了modify_max+update_max两个函数
void modify_max(int u, int l, int r, int v) {
if (tr[u].l > r || tr[u].r < l) return; //无交集，直接返回
if (l <= tr[u].l && tr[u].r <= r) //如果区间完整命中
if (update_max(u, v)) return; //需要分类讨论，只有3种情况是可以进行更新的，其它情况只能继续分裂
//分裂
pushdown(u);
modify_max(ls, l, r, v), modify_max(rs, l, r, v);
pushup(u);
}
//更新最小值操作，拆分成了modify_min+update_min两个函数
void modify_min(int u, int l, int r, int v) {
if (l > tr[u].r || r < tr[u].l) return;
if (l <= tr[u].l && tr[u].r <= r)
if (update_min(u, v)) return;
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 (tr[u].l >= 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 (tr[u].l >= 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 (tr[u].l >= 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;
}