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

数列分块入门7

题意概括

区间乘法，区间加法，单点询问。

写在前面

写过线段树模板2的童鞋应该很清楚了吧QAQ

由于*与Markdown冲突，所以用×代替o(*￣︶￣*)o

正题

我们把一个数表示为 a[i] × tg2[b[i]] + tg1[b[i]]。tg2表示乘法标记，tg1表示加法标记。

对于不完整的块，直接 a[i] = a[i] × tg2[b[i]] + tg1[b[i]] 将这个块的所有元素都还原，也就是将该块的标记下传。

对于完整的块

乘法：( a[i] × tg2[b[i]] + tg1[b[i]] ) × c = a[i] × (tg2[b[i]] × c) + (tg1[b[i]] × c) 也就是说，将tg1、tg2都乘c就可以了

加法：( a[i] × tg2[b[i]] + tg1[b[i]] ) + c = a[i] × tg2[b[i]] + (tg1[b[i]] + c) 也就是将tg1加上c

然后就很清楚了ヾ(ｏ･ω･)ﾉ

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define mod(x) (1ll * x) % 10007

int n, d;
int a[MAXN], b[MAXN], tg1[500], tg2[500];

inline void Push( int wh ){
	for ( int i = ( wh - 1 ) * d + 1; i <= wh * d; ++i ) a[i] = mod( 1ll * a[i] * tg2[wh] + tg1[wh] );
	tg1[wh] = 0; tg2[wh] = 1;
}

void Add( int l, int r, int c ){
	if ( b[l] == b[r] ){
		Push(b[l]);
		for ( int i = l; i <= r; ++i ) a[i] = mod( a[i] + c );
		return;
	}
	Push(b[l]);
	for ( int i = l; b[i] == b[l]; ++i ) a[i] = mod( a[i] + c );
	Push(b[r]);
	for ( int i = r; b[i] == b[r]; --i ) a[i] = mod( a[i] + c );
	for ( int i = b[l] + 1; i <= b[r] - 1; ++i ) tg1[i] = mod( tg1[i] + c );
}

void Mul( int l, int r, int c ){
	if ( b[l] == b[r] ){
		Push(b[l]);
		for ( int i = l; i <= r; ++i ) a[i] = mod( a[i] * c );
		return;
	}
	Push(b[l]);
	for ( int i = l; b[i] == b[l]; ++i ) a[i] = mod( a[i] * c );
	Push(b[r]);
	for ( int i = r; b[i] == b[r]; --i ) a[i] = mod( a[i] * c );
	for ( int i = b[l] + 1; i <= b[r] - 1; ++i ) tg1[i] = mod( tg1[i] * c ), tg2[i] = mod( tg2[i] * c );
}

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;
	}
	for ( int i = 1; i <= b[n]; ++i ) tg1[i] = 0, tg2[i] = 1;
	for ( int i = 1; i <= n; ++i ){
		int opt, l, r, c;
		scanf( "%d%d%d%d", &opt, &l, &r, &c );
		if ( opt == 0 ) Add( l, r, c );
		if ( opt == 1 ) Mul( l, r, c );
		if ( opt == 2 ) printf( "%d
", mod(a[r] * tg2[b[r]] + tg1[b[r]]) );
	}
	return 0;
}

总结

有多种操作时可以借助代数来分析~(＾ω＾)

数列分块系列目录