给定 (m) 个询问，每个询问是一个区间 ([l,r])，你需要通过自由地设定每个节点的 (mid)，设计一种“自适应线段树”，使得在这个线段树上跑这 (m) 个区间询问时，需要访问节点的次数最少。
Solution
对于询问 ([ql,qr]) 和结点 ([l,r])
- 如果 ([ql,qr]) 与 ([l,r]) 相交但不包含，贡献为 (1)
- 如果 ([ql,qr]) 包含 ([l,r])
- 如果 (l=r)，则贡献 (1)
- 如果 (l eq r)，则贡献 (-1) （将两个合并为一个，省了一次）
这样一来，我们需要考虑的内容就与树的结构无关，每个结点对应的贡献只和它自身的范围有关
我们可以预处理 (w[i][j]) 表示 ([i,j]) 这个结点产生的贡献，这个贡献可以用前缀和预处理出来
- 具体地，在 (i eq j) 时，([i,j]) 对于任意 ([1dots j,i dots n]-[idots t,tdots j])都产生了 (1) 的贡献，对任意 ([idots t,tdots j]) 都产生了 (-1) 的贡献
- 而在 (i=j) 时，产生 (1) 的贡献
设 (f[i][j]) 表示处理掉 ([i,j]) 这段区间的最小答案，那么
[f[i][j]=min_k (f[i][k]+f[k+1][j]) + w[i][j]
]
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1005;
int n,m,t1,t2,w[N][N],f[N][N],x[N];
void modify(int i,int j,int k,int l,int v) {
w[i][k]+=v;
w[i][l+1]-=v;
w[j+1][k]-=v;
w[j+1][l+1]+=v;
}
signed main() {
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++) {
cin>>t1>>t2;
modify(1,t2,t1,n,1);
modify(t1,t2,t1,t2,-2);
x[t1]+=2; x[t2+1]-=2;
}
for(int i=1;i<=n;i++) x[i]+=x[i-1];
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1];
}
}
for(int i=1;i<=n;i++) w[i][i]+=x[i], f[i][i]=w[i][i];
for(int l=2;l<=n;l++) {
for(int i=1;i+l-1<=n;i++) {
int j=i+l-1;
f[i][j]=1e14;
for(int k=i;k<j;k++) {
f[i][j]=min(f[i][k]+f[k+1][j],f[i][j]);
}
f[i][j]+=w[i][j];
}
}
cout<<f[1][n];
}