P4229 某位歌姬的故事 题解

\(n\le 9\times 10^8\)，显然复杂度不与 \(n\) 相关。\(m\le 500\)，显然可以接受 \(O(Tm^2)\) 的做法。对于 \([l,r]\)，考虑套路地将端点离散化，使得复杂度只和关键点个数有关。考虑对于 \([l,r,m]\)，离散化后被分成了 \(a_1,a_2,\cdots,a_p\) 段，那么这些段的最大值是好预处理的，且一定不会超过 \(m\)，且其中至少会有一个取到段中的最大值 \(m\)，于是发现对于一个最大值为 \(m\) 的区间如果在之前被放过一定取到了最大值为 \(m\) 的区间的最大值，那么设 \(dp_{i,j}\) 表示前 \(i\) 个段，最后 选择最大值 \(m\) 的位置是 \(j\)，则将 \(m\) 相同的分到一类，每次寻找前一个和其 \(m\) 相同的来转移即可。

代码的实现是较为繁琐的。

#include <bits/stdc++.h>
#define N 1005
#define int long long
#define mod 998244353
#define __(a) memset(a, 0, sizeof a)
using namespace std;
int T;
int n, q, A;
int ml[N], mr[N], mh[N];
int b[N << 1], tot;
int c[N], tc;
int mn[N];

int qpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1)
			ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}
int dp[N][N];
int pr[N];
void clr() {
	__(dp);
	__(ml);
	__(mr);
	__(mh);
	__(pr);
	__(b);
	__(c);
	tot = tc = 0;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
	while (T--) {
		clr();
		cin >> n >> q >> A;
		for (int i = 1; i <= q; i++) {
			cin >> ml[i] >> mr[i] >> mh[i];
			--ml[i];
			b[++tot] = ml[i];
			b[++tot] = mr[i];
			c[++tc] = mh[i];
		}
		b[++tot] = 0, b[++tot] = n;
		sort(b + 1, b + 1 + tot);
		tot = unique(b + 1, b + 1 + tot) - b - 1;
		sort(c + 1, c + 1 + tc);
		tc = unique(c + 1, c + 1 + tc) - c - 1;
		for (int i = 1; i <= tot; i++)
			mn[i] = A + 1;
		for (int i = 1; i <= q; i++) {
			ml[i] = lower_bound(b + 1, b + 1 + tot, ml[i]) - b + 1;
			mr[i] = lower_bound(b + 1, b + 1 + tot, mr[i]) - b;
			for (int j = ml[i]; j <= mr[i]; j++) 
				mn[j] = min(mn[j], mh[i]);
		}
		int ans = 1;
		for (int i = 2; i <= tot; i++) 
			if (mn[i] > A)
				ans = ans * qpow(A, b[i] - b[i - 1]) % mod;
		int fg = 0;
		for (int i = 1; i <= q; i++) {
			while (ml[i] <= mr[i] && mn[mr[i]] < mh[i])
				--mr[i];
			if (ml[i] > mr[i]) {
				cout << "0\n";
				fg = 1;
				break;
			}
			pr[mr[i]] = max(pr[mr[i]], ml[i]);
		}
		if (fg)
			continue;
		for (int i = 1; i <= tc; i++) {
			int lst = 1;
			dp[1][1] = 1;
			for (int j = 2; j <= tot; j++)
				if (mn[j] == c[i]) {
					memset(dp[j], 0, sizeof dp[j]);
					int tmp = qpow(c[i] - 1, b[j] - b[j - 1]);
					for (int k = pr[j]; k <= lst; k++)
						dp[j][k] = dp[lst][k] * tmp % mod;
					for (int k = 1; k <= lst; k++)
						dp[j][j] = (dp[j][j] + dp[lst][k]) % mod;
					dp[j][j] = dp[j][j] * ((qpow(c[i], b[j] - b[j - 1]) - tmp + mod) % mod) % mod;
					lst = j;
				}
			int as = 0;
			for (int j = 1; j <= lst; j++)
				as = (as + dp[lst][j]) % mod;
			ans = ans * as % mod;
		}
		cout << ans << "\n";
	}
	return 0;
}