My Blogs
首先考虑如何比较简单的进行判定合法。每一次执行一个找最大值的过程（如果有多个最大值则取最右侧的），然后从这个位置把序列劈成两半，递归判定。
因为最大值的位置能走到序列的最左侧和最右侧，所以要求最大值的位置 $\lvert ((n-p)-(p-1))\rvert\leq 2$。
所以考虑区间 DP，设 $f_{i,j,k}$ 表示区间 $[i,j]$ 中最大值为 $k$ 的方案数。转移比较简单：
\[f_{i,j,k}=\sum_{p\;\mathrm{is}\;\mathrm{valid}}\sum_{x\leq k}f_{i,p-1,x}\sum_{y<k}f_{p+1,j,y}\]可以前缀和优化到 $\mathcal O(n^2)$。同时由于 $p$ 特殊的位置限制，所以可以把所有会访问到的区间搜出来，发现最多 $2000+$ 个区间，这样就有了 $50$ 分。
考虑进行优化。先观察上面方程的初值：
\[\begin{aligned} f_{i,i+1,x}&=1\\ f_{i,i,x}&=\max(0,\min(x,r_i)-l_i+1) \end{aligned}\]如果把 $\max$ 和 $\min$ 拆开，会得到分段的一次或零次关于 $x$ 的函数。所以每一个 $f_{i,j}$ 都是一个关于 $k$ 的不超过 $n$ 次的多项式（因为最多就是 $n$ 个一次函数相乘）。
拆开 $\max$ 和 $\min$ 之后有若干个值域的连续段。在连续段 $k\in[L,R]$ 内部，$f_{i,j}$ 关于 $k$ 的多项式相同。所以对于每个 $f_{i,j}$ 都会得到 $\mathcal O(n)$ 个分段函数。
上面的暴力 DP 瓶颈在于 $k$ 可能非常大，但是我们知道在同一连续段下它次数是 $\mathcal O(n)$ 的。而对于两个相邻的连续段 $[L,x]$ 和 $[x+1,R]$，后一个连续段只会用到前一个连续段 $k=x$ 处的 DP 值。（算 $k=x+1$ 的时候会用到）
所以对于每个连续段 $[L,R]$，可以先暴力算出前 $n+1$ 个点值（这在算 $k=L$ 时会用到 $L-1$ 处的点值），然后用拉格朗日插值求出其在 $x$ 处的点值。这样下一个区间需要用的信息就处理好了，可以继续处理下一段。
所以思路就比较明朗了：从小到大枚举连续段，然后暴力算出所有 $f_{i,j}$ 的前 $n+1$ 个点值，然后用拉插算出连续段最后一个数的点值，然后去算下一个连续段。DP 的总复杂度是 $\mathcal O(mn^2)$，其中 $m$ 为状态数，$2500$ 左右。
对于拉插，观察公式：
\[F(x_0)=\sum_{i=1}^{n+1}y_i\prod_{j\not=i}\frac{x_0-x_j}{x_i-x_j}\]可以先 $\mathcal O(n\log n)$ 或者 $\mathcal O(n)$ 预处理后面的 $\mathrm{prod}$，这样对于每个状态算的时候就是 $\mathcal O(n)$，所以这部分的总复杂度也是 $\mathcal O(mn^2)$。注意卡常。
一个小细节是可以把求出来 $R$ 的点值放到 DP 数组 $k=0$ 的位置，方便下一次暴力 DP 使用。代码目前（2024/4/17）是 优势非常小的 最优解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
int cnt=1,n,len,inv2[610],inv[610],v[310],a[310],b[310],f[2710][320],g[2710],L[2710],R[2710],id[310][310],numa[610];
queue<pii> q;
vector<pii> ve;
void dfs(int l,int r)
{
if(l>r)return;
if(l==r)return id[l][r]=l,void();
if(id[l][r])return;
id[l][r]=++cnt,ve.eb(mp(l,r));
for(int i=l;i<=r;++i)if(abs(2*i-l-r)<=2)dfs(l,i-1),dfs(i+1,r);
}
inline bool cmp(pii p1,pii p2){return p1.se-p1.fi>p2.se-p2.fi;}
inline void calc(int l,int r)
{
for(int i=1;i<=n;++i)
{
for(int j=l;j<=r;++j)
f[i][j-l+1]=min(b[i]-a[i]+1,max(0,j-a[i]+1));
}
for(int i=cnt;i>n;--i)
{
for(int j=1;j<=r-l+1;++j)f[i][j]=0;
if((R[i]-L[i]+1)&1)
{
int mid=(L[i]+R[i]-2)/2;
for(int j=max(1,a[mid]-l+1);j<=min(b[mid]-l+1,r-l+1);++j)
Madd(f[i][j],Cmul(f[id[L[i]][mid-1]][j],f[id[mid+1][R[i]]][j-1]));
++mid;
for(int j=max(1,a[mid]-l+1);j<=min(b[mid]-l+1,r-l+1);++j)
Madd(f[i][j],Cmul(f[id[L[i]][mid-1]][j],f[id[mid+1][R[i]]][j-1]));
++mid;
for(int j=max(1,a[mid]-l+1);j<=min(b[mid]-l+1,r-l+1);++j)
Madd(f[i][j],Cmul(f[id[L[i]][mid-1]][j],f[id[mid+1][R[i]]][j-1]));
}
else
{
int mid=(L[i]+R[i]-1)/2;
for(int j=max(1,a[mid]-l+1);j<=min(b[mid]-l+1,r-l+1);++j)
Madd(f[i][j],Cmul(f[id[L[i]][mid-1]][j],f[id[mid+1][R[i]]][j-1]));
++mid;
for(int j=max(1,a[mid]-l+1);j<=min(b[mid]-l+1,r-l+1);++j)
Madd(f[i][j],Cmul(f[id[L[i]][mid-1]][j],f[id[mid+1][R[i]]][j-1]));
}
for(int j=1;j<=r-l+1;++j)Madd(f[i][j],f[i][j-1]);
}
for(int i=1;i<=cnt;++i)f[i][0]=f[i][r-l+1];
}
inline void mian()
{
read(n),dfs(1,n),sort(ve.begin(),ve.end(),cmp),cnt=n,inv[0]=1;
for(int i=1;i<=600;++i)inv[i]=Cmul(inv[i-1],i);
inv[600]=power(inv[600],MOD-2);
for(int i=599;i>=1;--i)inv[i]=Cmul(inv[i+1],i+1);
for(auto p:ve)id[p.fi][p.se]=++cnt,L[cnt]=p.fi,R[cnt]=p.se;
for(int i=0;i<=310;++i)f[0][i]=1;
memcpy(inv2,inv,sizeof(inv));
for(int i=1;i<=600;++i)if(i&1)inv2[i]=Cdel(0,inv2[i]);
for(int i=1;i<=n;++i)read(a[i],b[i]),numa[++len]=a[i],numa[++len]=b[i]+1;
sort(numa+1,numa+1+len),len=unique(numa+1,numa+1+len)-numa-1;
int lim=n+1;
for(int k=1;k<len;++k)
{
if(numa[k+1]-numa[k]<=lim){calc(numa[k],numa[k+1]-1);continue;}
calc(numa[k],numa[k]+lim-1);
for(int i=1;i<=n;++i)f[i][0]=min(b[i]-a[i]+1,max(0,numa[k+1]-a[i]));
int all=1;
for(int j=1;j<=lim;++j)Mmul(all,numa[k+1]-numa[k]-j);
for(int j=1;j<=lim;++j)v[j]=Cmul(all,inv2[n+1-j],inv[j-1],power(numa[k+1]-numa[k]-j,MOD-2));
for(int i=n+1;i<=cnt;++i)
{
int s=0;
for(int j=1;j<=lim;++j)
Madd(s,Cmul(v[j],f[i][j]));
f[i][0]=s;
}
}
write(f[n+1][0]);
}