题解 P3203 【[HNOI2010]弹飞绵羊】

查看原题请戳这里
我们先来看一下这道题如果先转化成森林再处理的话，一共有如下几个操作：

• 删除一条边
• 加入一条边
• 查询两点间路径权值和

这不是一道LCT的题吗……
然而LCT代码复杂度太高了，这里我们来讲一下如何用分块来解决这道题。
首先，我们将这$n$个装置分成$\sqrt n$块，每块有$\sqrt n$个元素。然后，我们记录下每个元素跳出ta所在块所需要的步数以及ta会跳到哪里。然后，对于每次修改，我们就用$O(n)$的复杂度去修改一个块中所有元素的值；对于每次查询，我们就一个块一个块条。
时间复杂度：$O(\sqrt n)$
code：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define qwq printf("qwq\n");

using namespace std;

int read()
{
	register int x = 0,f = 1;register char ch;
	ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
	while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}

int n,m,x,y,z,a[200005],l[100005],r[100005],len,num,to[200005],cnt[200005],blog[200005];

void clannad(int k)
{
	for(int i = r[k]; i >= l[k]; i--)
	{
		blog[i] = k;
		if(i + a[i] > r[k]) to[i] = i + a[i],cnt[i] = 1;
		else to[i] = to[i + a[i]],cnt[i] = cnt[i + a[i]] + 1;
	}
}

void change(int k)
{
	int u = blog[k];
	for(int i = k; i >= l[u]; i--)
	{
		if(i + a[i] > r[u]) to[i] = i + a[i],cnt[i] = 1;
		else to[i] = to[i + a[i]],cnt[i] = cnt[i + a[i]] + 1;
	}
}

int query(int k,int sum)
{
	if(k > n) return sum;
	return query(to[k],sum + cnt[k]);
}

int main()
{
	n = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	len = sqrt(n);
	num = n / len;
	if(n % len) num++;
	for(int i = 1; i <= num; i++) l[i] = (i - 1) * len + 1,r[i] = i * len;
	r[num] = n;
	for(int i = 1; i <= num; i++) clannad(i);
	m = read();
	for(int i = 1; i <= m; i++)
	{
		x = read(); y = read() + 1;
		if(x == 1) printf("%d\n",query(y,0));
		if(x == 2)
		{
			z = read();
			a[y] = z;
			change(y);
		}
	}
    return 0;
}