有一个条件没看到（每次覆盖的数一定是最大的）
我们在这道题中可以只去维护断点（数与数不同的地方）
而由于新的区间覆盖的数字一定是不同于以前的数字，所以这个端点就比较好维护.
对于序列 $p$，覆盖 $[L,R]$ 显然 $1$ ~ $L-2$，$R+1$ ~ $n$ 断点不改变，$L-1$ 与 $R$ 成为新的断点.
那么我们令 $SUM[i]$ 表示前 $1$ ~ $2^i$ 个序列中 $i$ 位置的断点总和.
那么经过依次新的操作，就按照上述方式更新一下 $SUM$ 数组即可.
大概是：
$1$ ~ $L-2$ 与 $R+1$ ~ $n$ 乘以 2 （不变 + 复制）
$L-1$ 与 $R$ 加上 $2^{i-1}$ （对于一半的数组加上新断点）
code:
#include <bits/stdc++.h>
#define ll long long
#define mod 20050321
#define N 2006
#define setIO(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
int p[N],SUM[N],tmp[N],n,m;
int main()
{
// setIO("input");
p[0]=1;
for(int i=1;i<N;++i)
p[i]=(ll)p[i-1]*2%mod;
scanf("%d%d",&n,&m);
SUM[0]=SUM[n]=1;
for(int i=1;i<=m;++i)
{
int L,R;
scanf("%d%d",&L,&R);
for(int j=0;j<L-1;++j) (SUM[j]*=2)%=mod;
for(int j=R+1;j<=n;++j) (SUM[j]*=2)%=mod;
(SUM[L-1]+=p[i-1])%=mod;
(SUM[R]+=p[i-1])%=mod;
int ans=0;
for(int j=0;j<=n;++j) (ans+=SUM[j])%=mod;
printf("%d\n",(ans-p[i]+mod)%mod);
}
return 0;
}
原文：https://www.cnblogs.com/guangheli/p/12747558.html