由于是统计极大连续段（连续子区间）的个数，所以我们可以像DP计数一样，记录以x位置结束（区间右端点）的连续子区间个数f[x]。例如此题在初始情况下，由于数组内元素全为0，若长为3，则f[3]=1。
由于第 i 次操作将区间 [l, r] 赋值为 i ，所以每次操作后 l-1 与 l 、r+1 与 r 的值必定不同，所以每次修改后 f[l-1] 与 f[r] 的贡献值会增大，增加的个数则是倍增的个数，即 $_math_inline$2^{i-1}$math_inline_$
对于其余位置，每次修改后直接倍增*2即可。
Code
1#include <bits/stdc++.h>
2
3using namespace std;
4typedef long long ll;
5
6const int MAXN = 2019;
7const ll MOD = 20050321;
8
9int n, m;
10ll f[MAXN], p[MAXN];
11
12#define DEBUG cout << "The Array: " ; for(int i = 1; i <= n; ++i) cout << f[i] << ' '; cout << endl;
13int main(){
14 ios::sync_with_stdio(false);
15 cin.tie(0); cout.tie(0);
16
17 cin >> n >> m;
18 //cout << endl << "n: " << n << " m: " << m << endl << endl;
19 p[0] = 1; for(int i = 1; i <= m; ++i) p[i] = (p[i-1]*2) % MOD;
20 f[n] = 1;
21 //DEBUG; cout << endl;
22 for(int i = 1; i <= m; ++i){
23
24 int l, r; cin >> l >> r;
25 //cout << "l: " << l << " r: " << r << endl;
26
27 for(int j = 1; j < l-1; ++j) f[j] = (f[j]*2) % MOD;
28 for(int j = r+1; j <= n; ++j) f[j] = (f[j]*2) % MOD;
29
30 f[l-1] = (f[l-1] + p[i-1]) % MOD;
31 f[r] = (f[r] + p[i-1]) % MOD;
32 //DEBUG;
33 ll ans = 0;
34 for(int j = 1; j <= n; ++j) ans = (ans + f[j]) % MOD;
35 //cout << "The Ans: ";
36 cout << ans << endl;
37 }
38}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。