分块

分块顾名思义就是将一个数组分成很多个块，然后进行操作。比如给定一些数，每次将 $[l,r]$ 的区间中的每个数加上 $c$ 然后在询问 $[l,r]$ 的区间和是多少。

啊，好简单的线段树问题，可惜要用分块。不知道为什么我感觉线段树能做所有分块题目首先，我们明确要记录的东西有哪些。

①每个块的区间和。

②每个块的左右儿子

③懒标记

然后，我们想想分块的大小是多少。如果块很小，那么块的数量就会极多，那么我们查询或修改的时候就要找很多个块，会超时。

如果块很大，那么我们修改或查询的时候就要在一个块里遍历所有数字跟暴力没区别会超时。不由的让我想起了上次考试第一题我写了一个比暴力慢51倍的“优化”

那么，我们因该怎么决定快的大小呢？太大不行太小也不行，那么我们就取个中间值根号 $n$ 。这里有个小细节，最后一个块可能不是完整的所以要更改最后一个块的右端点。

void init(){
	len = sqrt(n);
	num = n / len;
	if(n % len == 0){
		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 ++){
		for(int j = L[i] ; j <= R[i] ; j ++){
			pos[j] = i;
			sum[i] += a[j];
		}
	}
}

然后我们先讲讲怎么查询再讲修改。假设我们要查询的是 $[2,8]$ 那么我们发现就可以将区间变成三个部分。左右的不完整区域和中间的完整区域。

对于中间的完整区域，每个块的和我们是知道的，那么直接遍历中间的完整块相加就可以了。而我们直达一个块的大小是根号 $n$ 那么我们就可以暴力两边不完整的块。记住要加上我们的懒标记哦。

还有我们分块的懒标记是不用下发的，否则你的时间不久超了吗？

int check(int l,int r){
	int p = pos[l];
	int q = pos[r];
	int ans = 0;
	if(p == q){
		for(int i = l ; i <= r ; i ++){
			ans += a[i];
		}
		return ans + lazy[p] * (r - l + 1);
	}else{
		for(int i = l ; i <= R[p] ; i ++){
			ans += a[i];
		}
		ans += (R[p] - l + 1) * lazy[p];
		for(int i = L[q] ; i <= r ; i ++){
			ans += a[i];
		}
		ans += (r - L[q] + 1) * lazy[q];
		p ++;
		q --;
		for(int i = p ; i <= q ; i ++){
			ans += sum[i] + lazy[i] * (R[i] - L[i] + 1);
		}
		return ans;
	}
}

那么对于修改，一样可以分成三个部分。左右的不完整区域和中间的完整区域。对于左右的不完整区域我们直接暴力即可。记得改总和。

对于中间的完整区域，我们直接懒标记这个块的所有元素要加上的一个值即可。

void change(int l,int r,int k){
	int p = pos[l];
	int q = pos[r];
	if(p == q){
		for(int i = l ; i <= r ; i ++){
			a[i] += k;
			sum[p] += k;
		}
	}else{
		for(int i = l ; i <= R[p] ; i ++){
			a[i] += k;
			sum[p] += k;
		}
		for(int i = L[q] ; i <= r ; i ++){
			a[i] += k;
			sum[q] += k;
		}
		p ++;
		q --;
		for(int i = p ; i <= q ; i ++){
			lazy[i] += k;
		}
	}
}

那么完整代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int L[500005],R[500005];
int sum[500005],lazy[500005];
int pos[500005];
int a[500005],len,num;
void init(){
	len = sqrt(n);
	num = n / len;
	if(n % len == 0){
		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 ++){
		for(int j = L[i] ; j <= R[i] ; j ++){
			pos[j] = i;
			sum[i] += a[j];
		}
	}
}
void change(int l,int r,int k){
	int p = pos[l];
	int q = pos[r];
	if(p == q){
		for(int i = l ; i <= r ; i ++){
			a[i] += k;
			sum[p] += k;
		}
	}else{
		for(int i = l ; i <= R[p] ; i ++){
			a[i] += k;
			sum[p] += k;
		}
		for(int i = L[q] ; i <= r ; i ++){
			a[i] += k;
			sum[q] += k;
		}
		p ++;
		q --;
		for(int i = p ; i <= q ; i ++){
			lazy[i] += k;
		}
	}
}
int check(int l,int r){
	int p = pos[l];
	int q = pos[r];
	int ans = 0;
	if(p == q){
		for(int i = l ; i <= r ; i ++){
			ans += a[i];
		}
		return ans + lazy[p] * (r - l + 1);
	}else{
		for(int i = l ; i <= R[p] ; i ++){
			ans += a[i];
		}
		ans += (R[p] - l + 1) * lazy[p];
		for(int i = L[q] ; i <= r ; i ++){
			ans += a[i];
		}
		ans += (r - L[q] + 1) * lazy[q];
		p ++;
		q --;
		for(int i = p ; i <= q ; i ++){
			ans += sum[i] + lazy[i] * (R[i] - L[i] + 1);
		}
		return ans;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	init();
	while(n --){
		int opt,l,r,c;
		cin >> opt >> l >> r >> c;
		if(opt == 0){
			change(l , r , c);
		}else{
			cout << check(r , r) << "\n";
		}
	}
	return 0;
}

U522569 ١١(❛ᴗ❛)【分块】-区间修改，区间小值查询

老师其他三题都是模板所以我跳过了本题要我们求一个区间内小于某个值的个数。对于每一个块，我们该如何快速求解小于的个数呢？如果直接枚举这个块内的数字时间上就是暴力，过不了。

在我们学过的算法之中有哪些算法能够快速求小于某个值的个数呢？很显然是二分，二分找到最大的符合条件的值后，这个值的大小值排名就是个数，因为其他的排名低的都更小了。

但是，我们发现因为二分需要排序，如果每个块我们都排序时间是不是太高了。因此，我们决定让一开始的块内的数字就是有序的，那么我们还要用一个 $vector$ 记录。

散块部分，我们直接暴力修改即可，反正一个块又不大。记得将 $vector$ 改变且排序。

进阶部分的第一题因为与这题类似所以我放一起讲了。这道题目求大于等于的部分个数，我们知道了有多少个数知道了小于部分的个数求大于等于的个数直接减去就可以了。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int L[500005],R[500005];
int sum[500005],lazy[500005];
int pos[500005];
int a[500005],len,num;
vector<int>E[500005];
void init(){//初始化
	len = sqrt(n);
	num = n / len;
	if(n % len == 0){
		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 ++){
    //这里不用将 a 排序否则修改的时候会改成其他的
		for(int j = L[i] ; j <= R[i] ; j ++){
			pos[j] = i;
			sum[i] += a[j];
			E[i].push_back(a[j]);//将a[j]放入块内
		}
		sort(E[i].begin() , E[i].end());//排序方便二分
	}
}
void cc(int l,int r,int k){//暴力将不完整的块增加
	for(int i = l ; i <= r ; i ++){
		a[i] += k;
	}
	E[pos[l]].clear();
	for(int i = L[pos[l]] ; i <= R[pos[l]] ; i ++){
		E[pos[l]].push_back(a[i]);
	} 
	sort(E[pos[l]].begin(), E[pos[l]].end());//排序方便二分
	return;
}
void change(int l,int r,int k){
	int p = pos[l];
	int q = pos[r];
	if(p == q){
		cc(l , r , k);
	}else{
		cc(l , R[p] , k);
		cc(L[q] , r , k);
		p ++;
		q --;
		for(int i = p ; i <= q ; i ++){
			lazy[i] += k;//懒标记
		}
	}
}
int ch(int l,int r,int k){//暴力查找不完整块的个数
	int cnt = 0;
	for(int i = l ; i <= r ; i ++){
		if(a[i] + lazy[pos[l]] < k){
			cnt ++;
		}
	}
	return cnt;
}
int check(int l,int r,int k){
	int p = pos[l];
	int q = pos[r];
	int ans = 0;
	if(p == q){
		ans += ch(l , r , k);
	}else{
		ans += ch(l , R[p] , k);
		ans += ch(L[q] , r , k);
		p ++;
		q --;
		for(int i = p ; i <= q ; i ++){
			ans += lower_bound(E[i].begin(), E[i].end() , k - lazy[i]) - E[i].begin();//二分知道排名排名就是个数
		}
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	init();
	while(n --){
		int opt,l,r,c;
		cin >> opt >> l >> r >> c;
		if(opt == 0){
			change(l , r , c);
		}else{
			cout << check(l , r , c * c) << "\n";
		}
	}
	return 0;
}

P3793 由乃救爷爷

首先，一看题目区间最大值没有修改，老师老师 $st$ 表直接启动。一看空间 $(nlogn)$ 可以开。一交 $MLE$。知周所众， $c++$ 只能开 $(2e8)$ 空间炸了。所以这题卡 $c++$。

在来想分块，很容易发现从维护区间和变成直接维护区间最大值。但是，时间 $O(nsqrt(n))$ 时间炸了。怎么办呢？一个时间炸一个空间炸，那就结合起来不就不会炸了吗？

$st_{i,j}$ 表示以 $i$ 作为起点长度是 $2^j$ 的分块区间最大值。什么意思呢？就是 $st$ 表维护分块的区间最大值，将每个块看成这个块内的最大值。这样就变成了长度是根号 $n$ 的数组。 $st$ 表空间就不会炸了。

但是，旁边的散块怎么半呢？有什么优化的办法吗？我们发现每个散块都是连接这完整的块的。所以散块部分就是一个前缀最大值和后缀最大值。那么我们也维护一下就可以了。

code

#include<bits/stdc++.h>
using namespace std;
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
int n,m;
unsigned s;
int a[30000007];
int lg[30000007],p[30000005],q[30000005];
int st[5005][15];
int L[5005],R[5005],pos[30000007];
int num;
unsigned long long ans;
int query(int l,int r){
	if(l > r)return 0;
	int k = lg[r - l + 1];
	return max(st[l][k] , st[r - (1 << k) + 1][k]);
}
void init(){
	int len = sqrt(n);
	num = n / len;
	if(n % len != 0)num ++;
	for(int i = 1 ; i <= num ; i ++){
		L[i] = (i - 1) * len + 1;
		R[i] = i * len;
	}
	for(int i = 1 ; i <= num ; i ++){
		for(int j = L[i] ; j <= R[i] ; j ++){
			pos[j] = i;
			st[i][0] = max(st[i][0] , a[j]);
		}
		p[L[i]] = a[L[i]];
		q[R[i]] = a[R[i]];
		for(int j = L[i] + 1 ; j <= R[i] ; j ++){
			p[j] = max(p[j - 1] , a[j]);
		}
		for(int j = R[i] - 1 ; j >= L[i] ; j --){
			q[j] = max(q[j + 1] , a[j]);
		}
	}
	for(int i = 2 ; i <= num ; i ++){
		lg[i] = lg[i >> 1] + 1;
	}
	for(int j = 1 ; (1 << j) <= num ; j ++){
		for(int i = 1 ; i + (1 << j) - 1 <= num ; i ++){
			st[i][j] = max(st[i][j - 1] , st[i + (1 << j - 1)][j - 1]);
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m >> s;
	srand(s);
	for(int i = 1 ; i <= n ; i ++){
		a[i] = read();
	}
	init();
	while(m --){
		int l = read() % n + 1,r = read() % n + 1;
		if(l > r)swap(l , r);
		int x = pos[l];
		int y = pos[r];
		int tmp = 0;
		if(x == y){
			for(int i = l ; i <= r ; i ++){
				tmp = max(tmp , a[i]);
			}
		}else{
			tmp = query(x + 1 , y - 1);
			tmp = max(tmp , max(q[l] , p[r]));
		}
		ans += tmp;
	}
	cout << ans;
	return 0;
}

P4879 ycz的妹子

如果没有第三个操作我相信所有人都会。那么第三个操作时难在哪里呢？做的时候你就会发现，它难在要有袜子的城市的第 $x$ 座。那么，我们因该怎么解决呢？

我们知道，既然我们可以维护每个块内的权值和，最大值，那么我们为什么不能维护每个块内的有袜子的人的个数呢？这是不是也可以维护？

因此我们再建一个数组维护每个块有几座有袜子的城市。那么，我们就可以将要找的答案的区间大小缩小到一个块内。那么我们就可以直接暴力这个块内的所有城市找到第 $x$ 座有袜子的城市了。

因此，我们还要一个数组记录每个城市是否有袜子，那么一个用来确定时那个块，一个具体确定时那座城市。那么，就有了几个要注意的点。

因为一开始就有 $5e5$ 座城市所以提前标记那些城市有袜子，而不是再预处理的时候认为 $5e5$ 座城市都有袜子。第二和第三个操作记得更新袜子的数量和情况。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[1000005];
int x[1000005],y[1000005],pos[1000005];
int sum[1000005];
int gs[1000005],num,len;
bool vis[1000005];
void init(){
	len = sqrt(n);
	num = n / len;
	if(n % len != 0){
		num ++;
	}
	for(int i = 1 ; i <= num ; i ++){
		x[i] = (i - 1) * len + 1;
		y[i] = i * len;
	}
	y[num] = n;
	for(int i = 1 ; i <= num ; i ++){
		for(int j = x[i] ; j <= y[i] ; j ++){
			pos[j] = i;
			sum[i] += a[j];
			if(vis[j])gs[i] ++;
		}
	}
	return;
} 
void change(int l,int r,int c){
	int p = pos[l];
	int q = pos[r];
	if(p == q){
		for(int i = l ; i <= r ; i ++){
			if(!vis[i])continue;
			a[i] += c;
		}
		sum[p] += (r - l + 1) * c;
		return;
	}else{
		for(int i = l ; i <= y[p] ; i ++){
			if(!vis[i])continue;
			a[i] += c;
			sum[p] += c;
		} 
		for(int i = x[q] ; i <= r ; i ++){
			if(!vis[i])continue;
			a[i] += c;
			sum[q] += c;
		}
		return;
	}
}
int check(int l,int r){
	int p = pos[l];
	int q = pos[r],ans = 0;
	if(p == q){
		for(int i = l ; i <= r ; i ++){
			ans += a[i];
		}
		return ans;
	}else{
		for(int i = l ; i <= y[p] ; i ++){
			ans += a[i];
		} 
		for(int i = x[q] ; i <= r ; i ++){
			ans += a[i];
		}
		p ++;
		q --;
		for(int i = p ; i <= q ; i ++){
			ans += sum[i];
		}
		return ans;
	}
}
void cc(int l,int c){
	int p = pos[l];
	sum[p] -= a[l];
	a[l] = c;
	sum[p] += c;
	if(!vis[l]){
		gs[p] ++;
	}
	vis[l] = 1;
}
void ch(int l){
	int ans = 0;
	for(int i = 1 ; i <= num ; i ++){
		ans += gs[i];
		if(ans >= l){
			ans -= gs[i];
			for(int j = x[i] ; j <= y[i] ; j ++){
				if(vis[j]){
					ans ++;
				}
				if(ans == l){
					vis[j] = 0;
					sum[i] -= a[j];
					a[j] = 0;
					gs[i] --;
					break;
				}
			}
			break;
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
		vis[i] = 1;
	}
	n = 5e5;
	init();
	while(m --){
		char opt;
		int l,r,c; 
		cin >> opt;
		if(opt == 'C'){
			cin >> l >> c;
			change(l , l , -c);
		}else if(opt == 'I'){
			cin >> l >> c;
			cc(l , c);
		}else if(opt == 'D'){
			cin >> l;
			ch(l);
		}else{
			cout << check(1 , n) << "\n";
		}
	}
	return 0;
}

P4109 [HEOI2015] 定价

首先，我们来找一下规律。我们知道末尾的 $0$ 越多答案越小，如果 $0$ 的个数一样我们才会去考虑 $5$ 的情况。那么，一下区间的答案如下：

我们可以将上方的每个区间看成一个块。那么，我们的块维护的就是答案。我们只要在这些情况中找最小值即可。

然后，散块部分，我们知道一个块的大小是 $10000$ 那么，散块部分的大小一定是小于 $10000$ 的。再看一眼数据范围 $T <= 100$。

那么，我们对于散块部分就可以直接暴力。完整块扫过去就可以了。因为 $L,R <= 10^9$ 一个块大小 $10^4$ 再乘上 $100$ 刚好 $10^7$.

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,len;
int get_len(int x){
	while(x % 10 == 0){
		x /= 10;
	}
	int a = 0;
	int tmp = x;
	while(x != 0){
		a ++;
		x /= 10;
	}
	if(tmp % 10 == 5){
		return 2 * a - 1;
	}
	return 2 * a;
}
int check(int l,int r){
	int ans = 1e9;
	int val;
	int x = l / len + 1;
	int y = r / len + 1;
	if(x == y){
		for(int i = l ; i <= r ; i ++){
			int res = get_len(i);
			if(res < ans){
				ans = res;
				val = i;
			}
		}
	}else{
		for(int i = l ; i < x * len ; i ++){
			int res = get_len(i);
			if(res < ans){
				ans = res;
				val = i;
			}
		}
		for(int i = (y - 1) * len ; i <= r ; i ++){
			int res = get_len(i);
			if(res < ans){
				ans = res;
				val = i;
			}
		}
		for(int i = x * len ; i < (y - 1) * len ; i += len){
			int res = get_len(i);
			if(res < ans){
				ans = res;
				val = i;
			}
		}
	}
	return val;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
	len = 1e4;
	while(n --){
		int l,r;
		cin >> l >> r;
		cout << check(l , r) << "\n";
	}
	return 0;
}

P5356 [Ynoi Easy Round 2017] 由乃打扑克

我们初看题目发现，好像做过欸。但是，这道题目要求第 $k$ 个数的值。但是我们以前只讲了求小于 $c$ 的个数啊。那么，我们可不可以枚举 $c$ 呢？

第 $k$ 个数字，我们可以找 $k - 1$ 的 $c$ 是多少啊，然后 $c + 1$ 不就变成了排名第 $k$ 的数字的值了吗？然后，我们发现 $c$ 越大个数越多。

那么，这不就是一个单调性吗？因此我们还可以二分优化一下。然后获得了 $30pts$ 的好成绩。还要优化，怎么优化？

我们想想一开始的二分边界真的要达到极限吗？有些时候是不用的毕竟假设给你一堆 $1$ 你的二分边界要 $-2e9 \ 2e9$ 吗？所以二分的边界只要用最大和最小即可。

然后，还有一个优化。回顾代码，我们发现经常有一个排序，这个排序难道每次都要吗？我们发现如果整个块加上一个值，那么不用再排序。因此我们标记一下那些块才能排序。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9;
int n,m;
int L[1000005],R[1000005];
int lazy[1000005];
int pos[1000005];
int a[1000005],len,num;
vector<int>E[1000005];
bool vis[1000005];
void init(){
	len = sqrt(n);
	num = n / len;
	if(n % len == 0){
		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 ++){
		for(int j = L[i] ; j <= R[i] ; j ++){
			pos[j] = i;
			E[i].push_back(a[j]);
		}
		sort(E[i].begin() , E[i].end());
	}
}
int check(int l,int r,int k){
	int p = pos[l];
	int q = pos[r];
	int ans = 0;
	if(p == q){
		for(int i = l ; i <= r ; i ++){
			if(a[i] + lazy[p] < k){
				ans ++;
			}
		}
		return ans;
	}
	for(int i = l ; i <= R[p] ; i ++){
		if(a[i] + lazy[p] < k){
			ans ++;
		}
	}
	for(int i = L[q] ; i <= r ; i ++){
		if(a[i] + lazy[q] < k){
			ans ++;
		}
	}
	for(int i = p + 1 ; i <= q - 1 ; i ++){
		if(E[i][0] >= k - lazy[i]){
			continue;
		}
		int tmp = E[i].size() - 1;
		if(E[i][tmp] < k - lazy[i]){
			ans += R[i] - L[i] + 1;
			continue; 
		} 
		ans += lower_bound(E[i].begin() , E[i].end() , k - lazy[i]) - E[i].begin();
	}
	return ans;
}
void EA(int p){
	E[p].clear();
	for(int i = L[p] ; i <= R[p] ; i ++){
		a[i] += lazy[p];
		E[p].push_back(a[i]);
	}
	sort(E[p].begin() , E[p].end());
	lazy[p] = 0;
	vis[p] = 0;
	return;
}
void update(int l,int r,int k){
	int p = pos[l];
	int q = pos[r];
	if(p == q){
		for(int i = l ; i <= r ; i ++){
			a[i] += k;
		}
		vis[p] = 1;
		return;
	}
	for(int i = p + 1 ; i <= q - 1 ; i ++){
		lazy[i] += k;
	}
	for(int i = l ; i <= R[p] ; i ++){
		a[i] += k;
	}
	for(int i = L[q] ; i <= r ; i ++){
		a[i] += k;
	}
	vis[p] = vis[q] = 1;
}
int query(int l,int r,int k){
	int lt = INF;
	int rt = -INF;
	int p = pos[l];
	int q = pos[r];
	for(int i = p ; i <= q ; i ++){
		if(vis[i]){
			EA(i);
		}
		lt = min(lt , E[i][0] + lazy[i]);
		rt = max(rt , E[i][E[i].size() - 1] + lazy[i]);
	}
	lt --;
	rt ++;
	if(k > r - l + 1){
		return -1;
	}
	while(lt + 1 < rt){
		int mid = (lt + rt) / 2;
		int tmp = check(l , r , mid);
		if(tmp > k - 1){
			rt = mid;
		}else{
			lt = mid;
		}
	}
	return rt - 1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	init();
	while(m --){
		int opt;
		int x,y,c;
		cin >> opt >> x >> y >> c;
		if(opt == 2){
			update(x , y , c);
		}else{
			cout << query(x , y , c) << "\n";
		}
	}
	return 0;
}

P3203 [HNOI2010] 弹飞绵羊

本题是问几次能弹出去。可是我们将整个数组分成了许多个块。那么我们转换一下记录每个块中的元素几步能弹到下一个块。下一个块的编号是什么。

那么，查询的时候我们顶多也就是把所有的块跑一边。那么，修该操作怎么弄呢？老师老师，这个要把当前编号连接的所有点都跑一遍更行答案。

但是呢注意看我们存储的信息。几步能跑到下一个块。你再上一个块用 $x$ 步跑到当前位置，我改变当前位置的答案更上一个块有什么关系？顶多也就是当前块内一些经过当前点的答案改变而已。所以修改也是根号的。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[200005];
int x[200005],y[200005],pos[200005];
int sum[200005],lazy[200005];
int to[200005],step[200005];
void init(){
	int len = sqrt(n);
	int num = n / len;
	if(n % len != 0){
		num ++;
	}
	for(int i = 1 ; i <= num ; i ++){
		x[i] = (i - 1) * len + 1;
		y[i] = i * len;
	}
	y[num] = n;
	for(int i = 1 ; i <= num ; i ++){
		for(int j = x[i] ; j <= y[i] ; j ++){
			pos[j] = i;
			sum[i] += a[j];
		}
	}
	for(int i = n ; i >= 1 ; i --){
		to[i] = a[i] + i;
		if(to[i] > y[pos[i]]){
			step[i] = 1;
		}else{
			step[i] = step[to[i]] + 1;
			to[i] = to[i + a[i]];
		}
	}
	return;
} 
int check(int x){
	int ans = 0;
	while(x <= n){
		ans += step[x];
		x = to[x];
	}
	return ans;
}
void change(int l,int r){
	a[l] = r;
	for(int i = y[pos[l]] ; i >= x[pos[l]] ; i --){
		to[i] = i + a[i];
		if(to[i] > y[pos[i]]){
			step[i] = 1;
		}else{
			step[i] = step[to[i]] + 1;
			to[i] = to[i + a[i]];
		}	
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	int m;
	cin >> m;
	init();
	while(m --){
		int opt,l,r,c;
		cin >> opt >> l;
		l ++;
		if(opt == 1){
			cout << check(l) << "\n";
		}else{
			cin >> r;
			change(l , r);
		}
	}
	return 0;
}