[洛谷 3203][HNOI2010]弹飞绵羊

题目链接

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

题解

如果从 \(u\) 能弹到 \(v\)（将弹飞也视为一个点），就连一条 \(u \to v\) 的边。

容易发现最后会形成一棵树。

这棵树还带一些修改边的操作，于是需要用 LCT 维护。

然而我不会

---

考虑暴力分块的做法。

设 \(f_i\) 表示从 \(i\) 弹出所在块需要的步数，\(g_i\) 表示从 \(i\) 出发后弹出所在块到达的第一个点。

查询当然是一次跳一块，直到弹飞。

修改的话，对一个点的修改只会影响它所在的块，因此修改该块内的所有元素即可。

查询和修改操作的时间复杂度都是 \(O(\sqrt n)\)，总时间复杂度是 \(O(m \sqrt n)\)。

#include <cmath>
#include <iostream>
using namespace std;
int b[200005],l[200005],k[200005];
int f[200005],g[200005];
int n,m;
int query(int x)
{
 int ans=0;
 while(x<=n)
 {
  ans+=f[x];
  x=g[x];
 }
 return ans;
}
void update(int x,int y)
{
 k[x]=y;
 for(int i=l[b[x]+1]-1;i>=l[b[x]];i--)
  if(i+k[i]>=l[b[i]+1])
  {
   f[i]=1;
   g[i]=i+k[i];
  }
  else
  {
   f[i]=f[i+k[i]]+1;
   g[i]=g[i+k[i]];
  }
}
int main()
{
 cin>>n;
 int siz=sqrt(n);
 for(int i=1;i<=n;i++)
 {
  cin>>k[i];
  b[i]=(i-1)/siz+1;
  if(b[i]!=b[i-1])l[b[i]]=i;
 }
 l[b[n]+1]=n+1;
 for(int i=n;i;i--)
  if(i+k[i]>=l[b[i]+1])
  {
   f[i]=1;
   g[i]=i+k[i];
  }
  else
  {
   f[i]=f[i+k[i]]+1;
   g[i]=g[i+k[i]];
  }
 cin>>m;
 while(m--)
 {
  int op;
  cin>>op;
  if(op==1)
  {
   int x;
   cin>>x;
   x++;
   cout<<query(x)<<endl;
  }
  else
  {
   int x,y;
   cin>>x>>y;
   x++;
   update(x,y);
  }
 }
 return 0;
}