D
题目大意：
\(n\)座建筑排成一排，每座建筑的高度为\(h_i\)。\(\forall i \in [1,n]\)，找出满足下面条件的\(j\)的数量：
- 在建筑\(i\)到\(j\)中，没有建筑比\(j\)高的
- \(j \in [i+1,n]\)
\(n\leq 2 \times 10^5\)，\({h}\)是\(1\)到\(n\)的排列。
分析：
考虑\(i\)不好处理，我们改为考虑每个\(j\)可以贡献到哪些\(i\)：即若\(h_j<h_i\)，\(k\)从\(j-1\)开始，一直向左，直到\(h_k>h_j\)时，\(i\in [k+1,j-1]\)都会被贡献到（答案\(+1\)）。所以，我们只需要快速找到在每个\(j\)往左第一个大于\(h_j\)的位置。这只需要我们把所有的\(i\)按照\(h_i\)从大到小排序，然后用一个\(set\)维护即可。至于区间修改单点查询，差分数组即可处理。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, t, pos[200005], d[200005], h[200005], c[200005];
set < int > a;
int ask(int x)
{
auto p = a.lower_bound(x);
if (p == a.end()) return max(1, *(prev(p)));
return *(prev(p));
}
int main()
{
scanf("%d", &n); a.insert(0);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]), pos[h[i]] = i;
for (int i = n; i >= 1; i -- )
{
int l = ask(pos[i]), r = pos[i] - 1;
if (l == 0) l = 1;
a.insert(pos[i]);
if (l > r || r == 0) continue;
d[l] ++ , d[r + 1] -- ;
}
for (int i = 1; i <= n; i ++ ) d[i] += d[i - 1], printf("%d ", d[i]);
puts("");
return 0;
}
F
题目大意：
\(n\)个点的有向图共有\(n+m\)条边。\(\forall i \in [1,n]\)，\(i\)至\(i+1\)存在一条边（\(n+1\)对应\(1\)）。\(\forall i \in [1,m]\)，\(x_i\)至\(y_i\)存在一条边。求下列方案数：从点\(1\)开始，恰好走\(k\)步。答案对\(998244353\)取模。\(n,k\leq 2 \times 10^5,m\leq 50\)。无重边自环。
分析：
\(O((n+m)k)\)的dp是显然的，但是无法通过。注意到虽然有\(n+m\)条边，但是其中的\(n\)条边形式都是一致的，而\(m\)又很小，复杂度瓶颈在\(n\)。于是我们考虑固定这\(n\)条边不动，让\(n\)个点去动（即：某条边\((i,i+1)\)，把\(i+1\)当成\(i\)，这样就相当于自己转移到自己，即保留原来的值，就不用考虑这条边了）。设 \(d_i\) 为走到节点 \(i\) 的方案数。首先，为了处理方便，不妨将所有节点的标号减 \(1\)，这样旋转操作可以转化为标号取模操作（常用）。在将点整体移动的情况下，我们可以忽略对原环上边的转移。边 \((x,y)\) 在第 \(t\) 次转移时的实际效果是
\[d_{(y-t)\bmod n}\to d_{(y-t)\bmod n}+d_{(x-t+1)\bmod n} \]模拟一下即可得到上述转移。例如，\(n=8,(x,y)=(2,4),t=1\)时，实际转移效果为\((2,3)\)。这是因为我们把\(i+1\)当成了\(i\)。另外，由于所有操作需要同时进行，所以需要缓存值后再操作。
代码：
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n, m, k, add[55][2], x[55], y[55], dp[200005];
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i ++ ) scanf("%d%d", &x[i], &y[i]), x[i] -- , y[i] -- ;
dp[0] = 1;
for (int i = 1; i <= k; i ++ )
{
for (int j = 1; j <= m; j ++ ) add[j][0] = (y[j] - i % n + n) % n, add[j][1] = dp[(x[j] - i % n + 1 + n) % n];
for (int j = 1; j <= m; j ++ ) dp[add[j][0]] = (dp[add[j][0]] + add[j][1]) % mod;
}
int res = 0;
for (int i = 0; i < n; i ++ ) res = (res + dp[i]) % mod;
printf("%d\n", res);
return 0;
}