目录
显示
题目链接
https://www.luogu.com.cn/problem/P5280
题解
我们按照题目中的伪代码，将能遍历到的点分为三类（遍历不到的点 \(tag\) 不变，所以不作讨论）：
- 完全覆盖的点：这个点对应的区间是指定询问区间的子集。
- 完全没覆盖的点：这个点对应的区间和指定询问区间的交集为空。
- 半覆盖的点：不属于上述两类的点。
根据代码，递归遍历到半覆盖的点时会继续向下遍历，而遇到其他两类点时会终止遍历。
写成代码的形式是这样的：
void update(int rt,int cl,int cr,int l,int r)
{
if(r<cl||cr<l)return;//完全没覆盖的点
if(l<=cl&&cr<=r)//完全覆盖的点
{
tag[rt]=1;
return;
}
//半覆盖的点
pushdown(rt);//显然这里被更新的点下面都会遍历到
int mid=(cl+cr)>>1;
update(rt<<1,cl,mid,l,r);
update(rt<<1|1,mid+1,cr,l,r);
}
因为线段树只会复制，形态不会改变，因此我们可以在一棵线段树里维护每个节点的信息。
设 \(f_i\) 表示 \(i\) 号节点 \(tag\) 的期望值。
（所有节点的期望值加起来，再乘以树的总数，就可以得到所求答案了）
我们分类讨论下：
- 对于完全覆盖的点：经过修改后这个点的 \(tag\) 一定为 \(1\)，从而有 \(f_i=(f_i+1)/2\)；
- 对于半覆盖的点：因为有 pushdown，这个点的 \(tag\) 一定为零，从而有 \(f_i=f_i/2\)；
- 对于完全没覆盖的点：仅凭现有的信息无法计算。一个完全没覆盖的点是否打上 \(tag\)，取决于这个点到根节点的路径上是否存在一个有 \(tag\) 的点（这样就可以通过 pushdown 的方式使该点获取到 \(tag\)），我们需要多维护一些信息来进行计算。
于是我们设 \(g_i\) 表示 \(i\) 号节点到根节点的路径上有 \(tag\) 的概率。
继续分类讨论：
- 对于完全覆盖的点：经过修改后该点一定有 \(tag\)，从而该点所在子树的所有点都有 \(g_i=(g_i+1)/2\)；
- 对于半覆盖的点：其到根节点的所有点标记都已经下放，从而没有标记，即 \(g_i=g_i/2\)；
- 对于完全没覆盖的点：如果其到根节点的路径上有 \(tag\)，则这个点会带上 \(tag\)，否则这个点以及这个点到根节点的路径上都没有标记，即 \(f_i=(f_i+g_i)/2\)（根据上面的描述，\(g_i\) 的值不会改变）。
我们发现一次修改操作最多更新 \(O(\log n)\) 个 \(f\) 的值，但是 \(g\) 的值最坏情况下（因为有对一个子树内所有点的更新操作）会更新 \(O(n)\) 个。
为了防止这种事情发生，我们需要打标记来处理“修改一个子树的 \(g\) 值”这一操作。
向 \(i\) 号点下放一个修改 \(x\) 次的标记的时候，将 \(g_i\) 作如下处理：
$$g_i=(g_i+2^x-1)/2^x$$
这样这题就做完了。
下面这份代码目前在 loj 上跑的是最快的。
#include <iostream>
#include <algorithm>
#define MOD 998244353
#define INV2 499122177
using namespace std;
struct seg
{
long long f,g,s,tag;
}s[800005];
long long p[100005],invp[100005];
void pushup(int rt)
{
s[rt].s=(s[rt<<1].s+s[rt<<1|1].s+s[rt].f)%MOD;
}
void pushdown(int rt)
{
int tag=s[rt].tag;
s[rt<<1].tag+=tag;
s[rt<<1|1].tag+=tag;
s[rt<<1].g=(s[rt<<1].g+p[tag]-1)*invp[tag]%MOD;
s[rt<<1|1].g=(s[rt<<1|1].g+p[tag]-1)*invp[tag]%MOD;
s[rt].tag=0;
}
void update(int rt,int cl,int cr,int l,int r)
{
if(cr<l||r<cl)
{
s[rt].f=(s[rt].f+s[rt].g)*INV2%MOD;
pushup(rt);
return;
}
if(l<=cl&&cr<=r)
{
s[rt].f=(s[rt].f+1)*INV2%MOD;
s[rt].g=(s[rt].g+1)*INV2%MOD;
s[rt].tag++;
pushup(rt);
return;
}
s[rt].f=s[rt].f*INV2%MOD;
s[rt].g=s[rt].g*INV2%MOD;
pushdown(rt);
int mid=(cl+cr)>>1;
update(rt<<1,cl,mid,l,r);
update(rt<<1|1,mid+1,cr,l,r);
pushup(rt);
}
int main()
{
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
p[0]=invp[0]=1;
for(int i=1;i<=m;i++)
{
p[i]=p[i-1]*2%MOD;
invp[i]=invp[i-1]*INV2%MOD;
}
int cnt=0;
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int l,r;
cin>>l>>r;
update(1,1,n,l,r);
cnt++;
}
else cout<<s[1].s*p[cnt]%MOD<<endl;
}
return 0;
}