[洛谷 5280,loj 3043][ZJOI2019]线段树

题目链接

https://www.luogu.com.cn/problem/P5280

https://loj.ac/problem/3043

题解

我们按照题目中的伪代码,将能遍历到的点分为三类(遍历不到的点 \(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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据