「分块系列」数列分块入门5 解题报告

数列分块入门5

题意概括

区间开方，区间求和。

写在前面

这题需要更好地利用暴力QAQ 不暴力这题简直没法做~

还有注意下，由于不是同一时段的代码，所属分块之后都写成b而不是p了QAQ 希望谅解。

正题

因为每个数都不超过2 ^ 31 - 1,所以一个数开方5次，肯定会为1。

我们可以对这一性质加以利用好好暴力QAQ。

我们用一个数组v来记录当前块是否全为1,s记录这一块的和。当修改时，若该块全为1，就用不着更新了;如果不是，就暴力一次，直接把这块全开方了(别忘了更新s)，顺便判断是否全为1，对v进行更新。对于两边不完整块，还是老样子——暴力QAQ。

时间复杂度分析

我们把修改完整块和不完整块分开分析。

对于完整块，最多修改5次，因为前面分析过，修改5次肯定都为1了，所以上限为O(5n)。

对于不完整块，每次修改最多触及2次，所以上限为O(2n√n) 期间枚举完整块时间上限为O(n√n)。

最后加起来就是O(5n+3n√n) 满足复杂度要求。

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50005

int a[MAXN], s[300], b[MAXN];
bool v[300]; 
int n, d;

void modify( int x, int y ){
	if ( b[x] == b[y] ){
		for ( int i = x; i <= y; ++i ){
			s[b[x]] -= a[i]; a[i] = sqrt(a[i]); s[b[x]] += a[i];
		}
		return;
	}
	for ( int i = x; b[i] == b[x]; ++i ){
		s[b[x]] -= a[i]; a[i] = sqrt(a[i]); s[b[x]] += a[i];
	}//修改不完整块 更新 s 的值
	for ( int i = y; b[i] == b[y]; --i ){
		s[b[y]] -= a[i]; a[i] = sqrt(a[i]); s[b[y]] += a[i];
	}
	for ( int i = b[x] + 1; i <= b[y] - 1; ++i ){
		if ( !v[i] ){//满足全为1就别做了 不满足才做
			v[i] = 1;
			for ( int j = d * ( i - 1 ) + 1; b[j] == i; ++j ){
				s[i] -= a[j]; a[j] = sqrt(a[j]); s[i] += a[j];
				if ( a[j] > 1 ) v[i] = 0;//还是不满足QAQ
			}
		}
	}
}

int Get( int x, int y ){//很好理解 不解释了
	int ans(0);
	if ( b[x] == b[y] ){
		for ( int i = x; i <= y; ++i ) ans += a[i];
		return ans;
	}
	for ( int i = x; b[i] == b[x]; ++i ) ans += a[i];
	for ( int i = y; b[i] == b[y]; --i ) ans += a[i];
	for ( int i = b[x] + 1; i <= b[y] - 1; ++i ) ans += s[i];
	return ans;
}

int main(){
	scanf( "%d", &n ); d = sqrt(n);
	for ( int i = 1; i <= n; ++i ){
		scanf( "%d", &a[i] ); b[i] = ( i - 1 ) / d + 1;
		s[b[i]] += a[i];
	}
	for ( int i = 1; i <= n; ++i ){
		int opt, l, r, c; scanf( "%d%d%d%d", &opt, &l, &r, &c );
		if ( opt ) printf( "%d
", Get( l, r ) );
		else modify( l, r );
	}
	return 0;
}

数列分块系列目录