| 记录编号 |
600157 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HZOI 2015]聪聪的世界 |
最终得分 |
100 |
| 用户昵称 |
 LikableP |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
6.994 s |
| 提交时间 |
2025-04-18 21:58:56 |
内存使用 |
36.81 MiB |
显示代码纯文本
#include <cstdio>
#define ls(root) root << 1
#define rs(root) root << 1 | 1
#define isdigit(x) (x >= '0' && x <= '9')
typedef long long ll;
template <typename T>
T max(T x, T y) {
return x > y ? x : y;
}
template <typename T>
T min(T x, T y) {
return x < y ? x : y;
}
template <typename T>
T read() {
T sum = 0, fl = 1;
int ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
return sum * fl;
}
template <typename T>
void write(T x) {
if (x < 0) putchar('-'), x = -x;
static int sta[35];
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) putchar(sta[--top] + 48);
}
template <typename T>
void write(T x, char lst) {
write(x);
putchar(lst);
}
const int MAXN = 1e6 + 10;
struct NODE {
ll maxx, minn;
ll lazy;
} node[MAXN << 2];
int n, m;
ll a[MAXN];
void Merge(int root) {
node[root].maxx = max(node[ls(root)].maxx, node[rs(root)].maxx);
node[root].minn = min(node[ls(root)].minn, node[rs(root)].minn);
}
void Build(int root, int lt, int rt) {
if (lt == rt) {
node[root].maxx = node[root].minn = a[lt];
return ;
}
int mid = lt + ((rt - lt) >> 1);
Build(ls(root), lt, mid);
Build(rs(root), mid + 1, rt);
Merge(root);
}
void PushDown(int root, int lt, int rt) {
if (node[root].lazy) {
node[ls(root)].maxx += node[root].lazy;
node[ls(root)].minn += node[root].lazy;
node[ls(root)].lazy += node[root].lazy;
node[rs(root)].maxx += node[root].lazy;
node[rs(root)].minn += node[root].lazy;
node[rs(root)].lazy += node[root].lazy;
node[root].lazy = 0;
}
}
ll GetSingle(int root, int lt, int rt, int x) {
if (lt == rt) {
return node[root].maxx;
}
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
if (x <= mid) {
return GetSingle(ls(root), lt, mid, x);
} else {
return GetSingle(rs(root), mid + 1, rt, x);
}
}
void SetSingle(int root, int lt, int rt, int x, ll val) {
if (lt == rt) {
node[root].maxx = node[root].minn = val;
node[root].lazy = 0;
return ;
}
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
if (x <= mid) {
SetSingle(ls(root), lt, mid, x, val);
} else {
SetSingle(rs(root), mid + 1, rt, x, val);
}
Merge(root);
}
void AddSeq(int root, int lt, int rt, int lq, int rq, ll val) {
if (lt == lq && rt == rq) {
node[root].maxx += val;
node[root].minn += val;
node[root].lazy += val;
return ;
}
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
if (rq <= mid) {
AddSeq(ls(root), lt, mid, lq, rq, val);
} else if (lq > mid) {
AddSeq(rs(root), mid + 1, rt, lq, rq, val);
} else {
AddSeq(ls(root), lt, mid, lq, mid, val);
AddSeq(rs(root), mid + 1, rt, mid + 1, rq, val);
}
Merge(root);
}
ll QueryLessLeft(int root, int lt, int rt, int lq, int rq, ll val) {
if (node[root].minn >= val) {
return -1;
}
if (lt == rt) {
return node[root].minn;
}
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
if (rq <= mid) {
return QueryLessLeft(ls(root), lt, mid, lq, rq, val);
} else if (lq > mid) {
return QueryLessLeft(rs(root), mid + 1, rt, lq, rq, val);
} else {
ll resr = QueryLessLeft(rs(root), mid + 1, rt, mid + 1, rq, val);
return resr == -1 ? QueryLessLeft(ls(root), lt, mid, lq, mid, val) : resr;
}
}
ll QueryGreaterLeft(int root, int lt, int rt, int lq, int rq, ll val) {
if (node[root].maxx <= val) {
return -1;
}
if (lt == rt) {
return node[root].maxx;
}
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
if (rq <= mid) {
return QueryGreaterLeft(ls(root), lt, mid, lq, rq, val);
} else if (lq > mid) {
return QueryGreaterLeft(rs(root), mid + 1, rt, lq, rq, val);
} else {
ll resr = QueryGreaterLeft(rs(root), mid + 1, rt, mid + 1, rq, val);
return resr == -1 ? QueryGreaterLeft(ls(root), lt, mid, lq, mid, val) : resr;
}
}
ll QueryLessRight(int root, int lt, int rt, int lq, int rq, ll val) {
if (node[root].minn >= val) {
return -1;
}
if (lt == rt) {
return node[root].minn;
}
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
if (rq <= mid) {
return QueryLessRight(ls(root), lt, mid, lq, rq, val);
} else if (lq > mid) {
return QueryLessRight(rs(root), mid + 1, rt, lq, rq, val);
} else {
ll resl = QueryLessRight(ls(root), lt, mid, lq, mid, val);
return resl == -1 ? QueryLessRight(rs(root), mid + 1, rt, mid + 1, rq, val) : resl;
}
}
ll QueryGreaterRight(int root, int lt, int rt, int lq, int rq, ll val) {
if (node[root].maxx <= val) {
return -1;
}
if (lt == rt) {
return node[root].maxx;
}
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
if (rq <= mid) {
return QueryGreaterRight(ls(root), lt, mid, lq, rq, val);
} else if (lq > mid) {
return QueryGreaterRight(rs(root), mid + 1, rt, lq, rq, val);
} else {
ll resl = QueryGreaterRight(ls(root), lt, mid, lq, mid, val);
return resl == -1 ? QueryGreaterRight(rs(root), mid + 1, rt, mid + 1, rq, val) : resl;
}
}
int main() {
freopen("ccsworld.in", "r", stdin);
freopen("ccsworld.out", "w", stdout);
n = read<int>(), m = read<int>();
for (int i = 1; i <= n; ++i) {
a[i] = read<ll>();
}
Build(1, 1, n);
while (m--) {
int opt, x, y; ll w;
opt = read<int>();
if (opt == 1) {
x = read<int>();
ll val = GetSingle(1, 1, n, x);
write(QueryLessLeft(1, 1, n, 1, x - 1, val), '\n');
} else if (opt == 2) { // ?
x = read<int>();
ll val = GetSingle(1, 1, n, x);
write(QueryGreaterLeft(1, 1, n, 1, x - 1, val), '\n');
} else if (opt == 3) {
x = read<int>();
ll val = GetSingle(1, 1, n, x);
write(QueryLessRight(1, 1, n, x + 1, n, val), '\n');
} else if (opt == 4) { // ?
x = read<int>();
ll val = GetSingle(1, 1, n, x);
write(QueryGreaterRight(1, 1, n, x + 1, n, val), '\n');
} else if (opt == 5) {
x = read<int>(), y = read<int>();
ll valx = GetSingle(1, 1, n, x);
ll valy = GetSingle(1, 1, n, y);
SetSingle(1, 1, n, x, valy);
SetSingle(1, 1, n, y, valx);
} else if (opt == 6) {
x = read<int>(), y = read<int>(), w = read<ll>();
AddSeq(1, 1, n, x, y, w);
} else if (opt == 7) {
x = read<int>(), y = read<int>(), w = read<ll>();
AddSeq(1, 1, n, x, y, -w);
} else {
printf("QwQ\n");
}
}
return 0;
}