JZOJ 7685. 【2022.10.06冲剌NOIP2022模拟】奇怪的函数（function）

\(\text{Solution}\)

观察到关于 \(x\) 的函数在 \(n\) 个操作之后一定是这样的：

一段水平直线加上一段斜率为 \(1\) 的直线再加上一段水平直线

于是线段树维护这个分段函数即可

因为我是用斜率为 \(1\) 的直线的起点和终点坐标反应这个函数

所以合并分段函数的时候要处理退化成一条水平直线的情况

然而考场忘了判。。。

不过这个第一次写数据结构维护分段函数呢

当然码量更少且不需要合并函数的做法是分块啦

维护每个块的函数，一次修改直接 \(O(\sqrt n)\) 重构

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#define IN inline

using namespace std;

template <typename T>

IN void read(T &x) {

	x = 0; char ch = getchar(); int f = 0;

	for(; !isdigit(ch); f = (ch == '-' ? 1 : f), ch = getchar());

	for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());

	if (f) x = ~x + 1;

}

const int N = 1e5 + 5, len = 2e8;

int n, q;

#define ls (p << 1)

#define rs (ls | 1)

#define mid (l + r >> 1)

struct SegmentTree {

	int x0, x1, y0, y1;

	IN int F(int x) {return ((x <= x0) ? y0 : ((x >= x1) ? y1 : x - x0 + y0));}

	IN int nF_max(int y) {

		return ((y < y0 || y > y1) ? -1 : ((y == y0) ? x0 : ((y == y1) ? len : y - y0 + x0)));

	}

	IN int nF_min(int y) {

		return ((y < y0 || y > y1) ? -1 : ((y == y0) ? 1 : ((y == y1) ? x1 : y - y0 + x0)));

	}

}seg[N * 4];

IN void single(int p, int op, int val) {

	seg[p].x0 = seg[p].y0 = 1, seg[p].x1 = seg[p].y1 = len;

	if (op == 1) seg[p].y0 += val, seg[p].y1 += val;

	else if (op == 2) seg[p].x1 = seg[p].y1 = val;

	else seg[p].x0 = seg[p].y0 = val;

}

IN void pushup(int p) {

	seg[p].y0 = seg[rs].y0, seg[p].y1 = seg[rs].y1;

	seg[p].x0 = seg[ls].nF_max(seg[rs].x0);

	if (seg[p].x0 == -1) seg[p].x0 = seg[ls].x0, seg[p].y0 = seg[rs].F(seg[ls].y0);

	seg[p].x1 = seg[ls].nF_min(seg[rs].x1);

	if (seg[p].x1 == -1) seg[p].x1 = seg[ls].x1, seg[p].y1 = seg[rs].F(seg[ls].y1);

	if (seg[p].y0 == seg[p].y1) seg[p].x0 = seg[p].x1 = 1;

}

void build(int p, int l, int r) {

	if (l == r) {int op, val; read(op), read(val), single(p, op, val); return;}

	build(ls, l, mid), build(rs, mid + 1, r), pushup(p);

}

void modify(int p, int l, int r, int x, int op, int val) {

	if (l == r) return single(p, op, val), void();

	((x <= mid) ? modify(ls, l, mid, x, op, val) : modify(rs, mid + 1, r, x, op, val));

	pushup(p);

}

int main() {

	freopen("function.in", "r", stdin);

	freopen("function.out", "w", stdout);

	read(n), build(1, 1, n), read(q);

	for(int op, pos, val; q; --q) {

		read(op), read(pos);

		if (op == 4) printf("%d\n", seg[1].F(pos));

		else read(val), modify(1, 1, n, pos, op, val);

	}

}

巴特西

JZOJ 7685. 【2022.10.06冲剌NOIP2022模拟】奇怪的函数（function）

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章