Submission #45345461

---

Source Code Expand

#include <atcoder/lazysegtree.hpp>
#include <atcoder/modint.hpp>
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/lazysegtree>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

using mint = atcoder::modint998244353;

const int N = 260000;
const int inf = 1e9;

int n, k;

int a[N];

int get_minf() {
	return -inf;
}

int get_pinf() {
	return inf;
}

int add(int x, int y) {
	return x + y;
}

int get_0() {
	return 0;
}

int get_max(int x, int y) {
	return max(x, y);
}

int get_min(int x, int y) {
	return min(x, y);
}

int sz[N];
int mx[N];
int mn[N];
int p[N];

int get(int x) {
	if (p[x] == x) {
		return x;
	}
	p[x] = get(p[x]);
	return p[x];
}

void merge(int x, int y) {
	x = get(x);
	y = get(y);
	if (x == y) {
		return;
	}
	if (sz[x] > sz[y]) {
		swap(x, y);
	}
	p[x] = y;
	sz[y] += sz[x];
	mn[y] = min(mn[y], mn[x]);
	mx[y] = max(mx[y], mx[x]);
}


int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		p[i] = i;
		mn[i] = i;
		mx[i] = i;
		sz[i] = 1;
	}
	vector<int> loc(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		--a[i];
		loc[a[i]] = i;
	}

	atcoder::lazy_segtree<int, get_max, get_minf, int, add, add, get_0> lx(n - k + 1);
	atcoder::lazy_segtree<int, get_max, get_minf, int, add, add, get_0> rx(n - k + 1);
	atcoder::lazy_segtree<int, get_min, get_pinf, int, add, add, get_0> len(n - k + 1);
	for (int i = 0; i + k <= n; ++i) {
		lx.set(i, i);
		rx.set(i, i + k);
		len.set(i, k);
	}

	atcoder::lazy_segtree<int, get_max, get_minf, int, add, add, get_0> go(n);
	for (int i = 0; i < n; ++i) {
		go.set(i, i);
	}

	mint ans = 1;

	auto find_loc = [&] (int l) {
		return go.max_right(0, [&] (int x) -> bool {
			return x < l;
		});
	};

	for (int val = 0; val < n; ++val) {
		while (len.all_prod() == 2) {
			int x = len.max_right(0, [&](int x) -> bool {
				return x > 2;
			});
			int l = lx.get(x);
			int r = rx.get(x);
			assert(r - l == 2);
			int a = find_loc(l);
			int b = find_loc(l + 1);
			merge(a, b);
			len.set(x, inf);
		}

		int lc = loc[val];
		int l = mn[get(lc)];
		int r = mx[get(lc)];
		l = go.prod(0, l) + 1;
		l = max(l, 0);
		r = go.prod(0, r + 1) + 1;

		ans *= (r - l);
		int lb = lx.max_right(0, [&](int x) -> bool {
			return x < r;
		});
		lx.apply(lb, n - k + 1, -1);
		len.apply(lb, n - k + 1, 1);

		int rb = rx.max_right(0, [&](int x) -> bool {
			return x <= l;
		});
		rx.apply(rb, n - k + 1, -1);
		len.apply(rb, n - k + 1, -1);

		go.set(lc, -inf);
		go.apply(lc + 1, n, -1);
	}

	cout << ans.val() << "\n";

	return 0;
}

Submission Info

Judge Result