P13508 [OOI 2024] Burenka and Pether

首先直接在序列上不好做，因为要时刻考虑跳到的点

\le a_v

。

所以转而从值域考虑，令

(u, v) \to (a_u, a_v)

，设

b_i

为

i

在

a

中的位置。然后对于一个数

x

，我们能求出一个

c_x

表示在序列上，位置

b_x

能跳到所有位置在

[b_x + 1, c_x]

之间且值

> x

的数，可以并查集 + set 求出。

那么现在一组询问

(x, y)

，我们的策略是：每次

x

跳到最大的一个

z

满足

z \le y

且

b_z \in [b_x + 1, c_x]

。

发现有

z \le y

的限制，无法直接倍增优化。

但是我们可以分治。具体地，设当前分治区间为

[l, r]

，把所有跨过中点（即

x \le mid, y > mid

）的询问的询问的

x

一直往右跳直到

> mid

为止，然后递归进子问题。这样的好处是，除了最后跳到

> mid

的那一步，我们不用考虑

z \le y

的限制，只用无脑跳到最远即可。

大致的思路就差不多是这样。具体实现，考虑对每个

x \in [l, mid]

求出

to_x, f_x

分别表示

x

往右能跳到的

\le mid

最远点和

> mid

的最近点。对于一个跨过中点的询问

(x, y)

，不断令

x \to to_x

直到

f_x \le y

（这一步可以倍增优化），然后求出

x

能跳到的

[mid + 1, y]

之间最大的

\le y

的点（这一步可以扫描线 + 线段树二分）。

每个询问只会在

\log n

个分治区间被考虑。时间复杂度

O((n + q) \log^2 n)

。

代码

CPP

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

namespace IO {
	const int maxn = 1 << 20;
	
	char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

	inline char gc() {
		return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
	}

	template<typename T = int>
	inline T read() {
		char c = gc();
		T x = 0;
		bool f = 0;
		while (c < '0' || c > '9') {
			f |= (c == '-');
			c = gc();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c ^ 48);
			c = gc();
		}
		return f ? ~(x - 1) : x;
	}
	
	inline int reads(char *s) {
		char c = gc();
		int len = 0;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c) && c != -1) {
			s[len++] = c;
			c = gc();
		}
		s[len] = '\0';
		return len;
	}
	
	inline string reads() {
		char c = gc();
		string s;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c) && c != -1) {
			s += c;
			c = gc();
		}
		return s;
	}

	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	
	struct Flusher {
		~Flusher() {
			flush();
		}
	} AutoFlush;

	inline void pc(char ch) {
		if (oS == obuf + maxn) {
			flush();
		}
		*oS++ = ch;
	}

	template<typename T>
	inline void write(T x) {
		static char stk[64], *tp = stk;
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != stk) {
			pc((*--tp) | 48);
		}
	}
	
	inline void write(const char *s) {
		for (int i = 0; s[i]; ++i) {
			pc(s[i]);
		}
	}
	
	template<typename T>
	inline void writesp(T x) {
		write(x);
		pc(' ');
	}
	
	template<typename T>
	inline void writeln(T x) {
		write(x);
		pc('\n');
	}
}

using IO::read;
using IO::reads;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 300100;
const int logn = 20;
const int inf = 0x3f3f3f3f;

int n, m, q, a[maxn], fa[maxn], b[maxn], c[maxn], ans[maxn], f[maxn];
vector<int> vc[maxn];

struct que {
	int o, x, y;
} qq[maxn];

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int to[logn][maxn], st[logn][maxn], g[logn][maxn];
pii ls[maxn];

inline int qmax(int l, int r) {
	if (l > r) {
		return 0;
	}
	int k = __lg(r - l + 1);
	return max(st[k][l], st[k][r - (1 << k) + 1]);
}

inline int qmin(int l, int r) {
	if (l > r) {
		return inf;
	}
	int k = __lg(r - l + 1);
	return min(st[k][l], st[k][r - (1 << k) + 1]);
}

namespace SGT {
	int mn[maxn << 2];
	
	void build(int rt, int l, int r) {
		mn[rt] = inf;
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
	}
	
	void update(int rt, int l, int r, int x, int y) {
		mn[rt] = min(mn[rt], y);
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		(x <= mid) ? update(rt << 1, l, mid, x, y) : update(rt << 1 | 1, mid + 1, r, x, y);
	}
	
	int find(int rt, int l, int r, int ql, int qr, int x) {
		if (ql > qr || mn[rt] > x) {
			return -1;
		}
		if (l == r) {
			return l;
		}
		int mid = (l + r) >> 1;
		if (qr > mid) {
			int t = find(rt << 1 | 1, mid + 1, r, ql, qr, x);
			if (t != -1) {
				return t;
			}
		}
		if (ql <= mid) {
			int t = find(rt << 1, l, mid, ql, qr, x);
			if (t != -1) {
				return t;
			}
		}
		return -1;
	}
}

void dfs(int l, int r, vector<int> Q) {
	if (Q.empty()) {
		return;
	}
	int mid = (l + r) >> 1;
	vector<int> L, R, U;
	for (int i : Q) {
		if (qq[i].y <= mid) {
			L.pb(i);
		} else if (qq[i].x > mid) {
			R.pb(i);
		} else {
			U.pb(i);
		}
	}
	for (int i = l; i <= mid; ++i) {
		to[0][i] = 0;
	}
	int tot = 0;
	for (int i = l; i <= mid; ++i) {
		ls[++tot] = pii(b[i], i);
	}
	sort(ls + 1, ls + tot + 1);
	for (int i = 1; i <= tot; ++i) {
		st[0][i] = ls[i].scd;
	}
	for (int j = 1; (1 << j) <= tot; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= tot; ++i) {
			st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		}
	}
	for (int i = l; i <= mid; ++i) {
		int x = upper_bound(ls + 1, ls + tot + 1, pii(b[i], i)) - ls;
		int y = upper_bound(ls + 1, ls + tot + 1, pii(c[i], n + 1)) - ls - 1;
		to[0][i] = qmax(x, y);
		if (to[0][i] <= i) {
			to[0][i] = 0;
		}
	}
	tot = 0;
	for (int i = mid + 1; i <= r; ++i) {
		ls[++tot] = pii(b[i], i);
	}
	sort(ls + 1, ls + tot + 1);
	for (int i = 1; i <= tot; ++i) {
		st[0][i] = ls[i].scd;
	}
	for (int j = 1; (1 << j) <= tot; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= tot; ++i) {
			st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		}
	}
	for (int i = l; i <= mid; ++i) {
		int x = upper_bound(ls + 1, ls + tot + 1, pii(b[i], i)) - ls;
		int y = upper_bound(ls + 1, ls + tot + 1, pii(c[i], n + 1)) - ls - 1;
		f[i] = g[0][i] = qmin(x, y);
	}
	for (int j = 1; j < logn; ++j) {
		for (int i = l; i <= mid; ++i) {
			to[j][i] = to[j - 1][to[j - 1][i]];
			g[j][i] = min(g[j - 1][i], g[j - 1][to[j - 1][i]]);
		}
	}
	for (int i = l; i <= mid; ++i) {
		vector<int>().swap(vc[i]);
	}
	for (int i : U) {
		int x = qq[i].x, y = qq[i].y, z = 0;
		if (f[x] <= y) {
			vc[qq[i].x].pb(i);
			continue;
		}
		for (int j = logn - 1; ~j; --j) {
			if (to[j][x] && g[j][x] > y) {
				z += (1 << j);
				x = to[j][x];
			}
		}
		if (f[x] > y) {
			ans[i] = 0;
			continue;
		}
		ans[i] += z;
		qq[i].x = x;
		vc[qq[i].x].pb(i);
	}
	tot = 0;
	for (int i = l; i <= r; ++i) {
		ls[++tot] = pii(b[i], i);
	}
	sort(ls + 1, ls + tot + 1, greater<pii>());
	SGT::build(1, mid + 1, r);
	for (int i = 1; i <= tot; ++i) {
		int j = ls[i].scd;
		if (j > mid) {
			SGT::update(1, mid + 1, r, j, b[j]);
		} else {
			for (int k : vc[j]) {
				int x = qq[k].x, y = qq[k].y;
				int z = SGT::find(1, mid + 1, r, mid + 1, y, c[x]);
				assert(z != -1);
				++ans[k];
				qq[k].x = z;
				if (z < y) {
					R.pb(k);
				}
			}
		}
	}
	dfs(l, mid, L);
	dfs(mid + 1, r, R);
}

void solve() {
	n = read();
	m = read();
	read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		b[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		fa[i] = i;
	}
	set<int> S;
	for (int i = 1; i <= n; ++i) {
		auto it = S.insert(b[i]).fst;
		if (next(it) != S.end() && *next(it) - b[i] <= m) {
			fa[b[i]] = *next(it);
		}
		if (it != S.begin() && b[i] - *prev(it) <= m) {
			fa[*prev(it)] = b[i];
		}
		c[i] = min(n, find(b[i]) + m);
	}
	q = read();
	vector<int> Q;
	for (int i = 1; i <= q; ++i) {
		qq[i].o = read();
		qq[i].x = a[read()];
		qq[i].y = a[read()];
		if (qq[i].x < qq[i].y) {
			Q.pb(i);
		}
	}
	dfs(1, n, Q);
	for (int i = 1; i <= q; ++i) {
		if (qq[i].o == 1) {
			ans[i] = min(ans[i], 1);
		}
		writeln(ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Info

P13508 [OOI 2024] Burenka and Pether

文章操作

相关推荐

评论

P13508 [OOI 2024] Burenka and Pether