JOISC2022 错误拼写 Sol

实在是绷不住了，做 JOISC 做到梦熊炼石原题，这下这下了。

限制

T_u\le T_v\ (u<v)

告诉你啥呢，告诉你这

[u, v]

这个区间要么全部相等，要么第一个相邻不同的位置是左边大于右边；

u>v

就是反过来，要么相等要么第一个相邻不同的位置左边小于右边。

考虑 dp，

f_{i,j}

表示考虑了

[i,n]

，

i

这个位置填的

j

这个字符。如果暴力转移就是枚举下一个不同的位置，判断合不合法并计算贡献。复杂度是

\Theta(n^2\Sigma)

。

你去想判断合不合法的过程是怎么样的，就是把所有左端点

\ge i

的限制区间全扔下标上，进行一个判断。那我们发现你

i

从右边来的时候，会增加一部分区间，改变一些位置的限制条件（即转移方式）。具体地，一个位置被转移的方式有：

不被覆盖
仅被 $u<v$ 的覆盖
仅被 $u>v$ 的覆盖
被两者同时覆盖

然后发现每个点的状态最多被改变

2

次。我们只要快速找到哪些点的覆盖状态发生了改变，用 set 维护每种状态的位置即可。复杂度

\Theta(n(\log n+\Sigma))

。

CPP

signed main() {
	n = read(), m = read();
	rep(i, 1, m) {
		int x = read(), y = read(), f = 0;
		if (x == y) continue;
		if (x > y) swap(x, y), f ^= 1;
		p[x].push_back({y, f});
	}
	rep(j, 0, 25) f[n][j] = 1, ge[j] = 1;
	se.insert(n);
	per(i, n - 1, 1) {
		for (pii j : p[i]) {
			int l = i, r = j.fs, fl = j.sc;
			if (fl) {
				auto it = se.lower_bound(l + 1);
				while (it != se.end() && *it <= r) {
					s1.insert(*it);
					rep(k, 0, 25) g1[k] += f[*it][k], ge[k] -= f[*it][k];
					se.erase(it++);
				}
				it = s0.lower_bound(l + 1);
				while (it != s0.end() && *it <= r) {
					s2.insert(*it);
					rep(k, 0, 25) g0[k] -= f[*it][k];
					s0.erase(it++);
				}
			} else {
				auto it = se.lower_bound(l + 1);
				while (it != se.end() && *it <= r) {
					s0.insert(*it);
					rep(k, 0, 25) g0[k] += f[*it][k], ge[k] -= f[*it][k];
					se.erase(it++);
				}
				it = s1.lower_bound(l + 1);
				while (it != s1.end() && *it <= r) {
					s2.insert(*it);
					rep(k, 0, 25) g1[k] -= f[*it][k];
					s1.erase(it++);
				}
			}
		}
		int s = 0;
		rep(j, 0, 25) (s += ge[j]) %= mod;
		rep(j, 0, 25) f[i][j] += (s - ge[j] % mod + mod) % mod;
		s = 0;
		per(j, 25, 0) {
			(f[i][j] += s) %= mod;
			(s += g0[j] % mod) %= mod;
		}
		s = 0;
		rep(j, 0, 25) {
			(f[i][j] += s) %= mod;
			(s += g1[j]) %= mod;
		}
		rep(j, 0, 25) f[i][j]++, f[i][j] %= mod;
		se.insert(i);
		rep(j, 0, 25) ge[j] += f[i][j];
	}
	int ans = 0;
	rep(j, 0, 25) (ans += f[1][j]) %= mod;
	write(ans);
    return 0;
}

JOISC2022 错误拼写 Sol

文章操作

相关推荐

评论

JOISC2022 错误拼写 Sol