专栏文章

分块1

HHhy140516
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miol912t
此快照首次捕获于
2025/12/02 21:02
3 个月前
此快照最后确认于
2025/12/02 21:02
3 个月前
查看原文

基础

分块就是把一个序列分成很多块，然后查询、修改时，对于整个块进行修改。
需要注意的是，分块只是一种思想，而不是一种算法。
写分块时，一般把长度设为 n\sqrt{n}，当然，也有的题卡这个数，所以需要一些调整。
发现如果一整块都要修改时，如果都修改，时间很慢，所以用懒标记记录整个块的加减情况。

例题

U522567 ١١(❛ᴗ❛)【分块】-区间修改，单点查询（数据需要加强）

这道题是分块的板子。
我们把块的长度是 n\sqrt{n}，把每个块的情况统计清楚，初始化结束。
对于查询，分为前块、中块和后块，前块和后块进行暴力修改，否则用懒标记。
查询时就是值加上懒标记。
CPP
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 1e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct Edge
{
	int v , nxt ;
}edge[kMaxN] ;
struct node
{
  int u , v ;
}Node[kMaxN] ;
int n , m ;
int cnt , scc , tim ;
int L[kMaxN] , R[kMaxN] , sum[kMaxN] , a[kMaxN] , pos[kMaxN] , lazy[kMaxN] ;
bool vis[kMaxN] ;
stack<int> st ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
void init(int n)
{
	int len = sqrt(n) ;
	int 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] = min(R[num] , n) ;
	for( int i = 1 ; i <= num ; i++ )
	{
		for( int j = L[i] ; j <= R[i] ; j++ )
		{
			sum[i] += a[j] ;
			pos[j] = i ;
		}
	}
}
void update(int l , int r , int c)
{
	int p = pos[l] , q = pos[r] ;
	if(p == q)
	{
		for( int i = l ; i <= r ; i++ )
		{
			a[i] += c ;
		}
		sum[p] += (r - l + 1) * c ;
	}
	else
	{
		for( int i = l ; i <= R[p] ; i++ )
		{
			a[i] += c ;
		}
		sum[p] += (R[p] - l + 1) * c ;
		for( int i = L[q] ; i <= r ; i++ )
		{
			a[i] += c ;
		}
		sum[q] += (r - L[q] + 1) * c ;
		for( int i = p + 1 ; i < q ; i++ )
		{
			lazy[i] += c ;
		}
	}
}
int query(int r)
{
	int q = pos[r] ;
	return a[r] + lazy[q] ;
}
void work()
{
  cin >> n ;
  for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
  init(n) ;
  for( int i = 1 ; i <= n ; i++ )
  {
  	int op , l , r , c ;
  	cin >> op >> l >> r >> c ;
  	if(op == 0) update(l , r , c) ;
  	else cout << query(r) << "\n" ;
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

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

除了查询其他相同。
查询时和改的时候相同分成三段，前面直接暴力加答案，后面类似。中间的话，这一整块的和都要加起来，可以提前求解。
注意要把懒标记算进去。
CPP
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 5e4 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct Edge
{
	int v , nxt ;
}edge[kMaxN] ;
struct node
{
  int u , v ;
}Node[kMaxN] ;
int n , k ;
int L[kMaxN] , R[kMaxN] , sum[kMaxN] , a[kMaxN] , pos[kMaxN] , lazy[kMaxN] ;
vector<int> G[kMaxN] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
void init(int n)
{
	int len = sqrt(n) ;
	int 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] = min(R[num] , n) ;
	for( int i = 1 ; i <= num ; i++ )
	{
		for( int j = L[i] ; j <= R[i] ; j++ )
		{
			G[i].push_back(a[j]) ;
			pos[j] = i ;
		}
		sort(G[i].begin() , G[i].end()) ;
	}
}
void update(int l , int r , int c)
{
	int p = pos[l] , q = pos[r] ;
	if(p == q)
	{
		for( int i = l ; i <= r ; i++ )
		{
			a[i] += c ;
		}
		G[p].clear() ;
		for( int i = L[p] ; i <= R[p] ; i++ ) G[p].push_back(a[i]) ;
        sort(G[p].begin() , G[p].end()) ;
	}
	else
	{
		for( int i = l ; i <= R[p] ; i++ )
		{
			a[i] += c ;
		}
		G[p].clear() ;
		for( int i = L[p] ; i <= R[p] ; i++ ) G[p].push_back(a[i]) ;
        sort(G[p].begin() , G[p].end()) ;
		for( int i = L[q] ; i <= r ; i++ )
		{
			a[i] += c ;
		}
		G[q].clear() ;
		for( int i = L[q] ; i <= R[q] ; i++ ) G[q].push_back(a[i]) ;
        sort(G[q].begin() , G[q].end()) ;
		for( int i = p + 1 ; i < q ; i++ )
		{
			lazy[i] += c ;
		}
	}
}
int query(int l , int r , int x)
{
	int p = pos[l] , q = pos[r] , cnt = 0 ;
	if(p == q)
	{
		for( int i = l ; i <= r ; i++ )
		{
			cnt += (a[i] + lazy[p] < x) ;
		}
	}
	else
	{
		for( int i = l ; i <= R[p] ; i++ )
		{
			cnt += (a[i] + lazy[p] < x) ;
		}
		for( int i = L[q] ; i <= r ; i++ )
		{
			cnt += (a[i] + lazy[q] < x) ;
		}
		for( int i = p + 1 ; i < q ; i++ )
		{
			cnt += lower_bound(G[i].begin() , G[i].end() , x - lazy[i]) - G[i].begin() ;
		}
	}
	return cnt ;
}
void work()
{
  cin >> n ;
  for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
  init(n) ;
  for( int i = 1 ; i <= n ; i++ )
  {
  	int op ;
  	cin >> op ;
  	if(op == 0) 
		{
			int l , r , c ;
			cin >> l >> r >> c ;
			update(l , r , c) ;
		}
  	else 
		{
			int l , r , x ;
			cin >> l >> r >> x ;
			cout << query(l , r , x * x) << "\n" ;
		}
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

P2357 守墓人

与上题一摸一样。
对于 22 和 33 的询问，就是进行 11 到 11 的区间修改。
CPP
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 2e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct Edge
{
	int v , nxt ;
}edge[kMaxN] ;
struct node
{
  int u , v ;
}Node[kMaxN] ;
int n , k ;
int L[kMaxN] , R[kMaxN] , sum[kMaxN] , a[kMaxN] , pos[kMaxN] , lazy[kMaxN] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
void init(int n)
{
	int len = sqrt(n) ;
	int 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] = min(R[num] , n) ;
	for( int i = 1 ; i <= num ; i++ )
	{
		for( int j = L[i] ; j <= R[i] ; j++ )
		{
			sum[i] += a[j] ;
			pos[j] = i ;
		}
	}
}
void update(int l , int r , int c)
{
	int p = pos[l] , q = pos[r] ;
	if(p == q)
	{
		for( int i = l ; i <= r ; i++ )
		{
			a[i] += c ;
		}
		sum[p] += (r - l + 1) * c ;
	}
	else
	{
		for( int i = l ; i <= R[p] ; i++ )
		{
			a[i] += c ;
		}
		sum[p] += (R[p] - l + 1) * c ;
		for( int i = L[q] ; i <= r ; i++ )
		{
			a[i] += c ;
		}
		sum[q] += (r - L[q] + 1) * c ;
		for( int i = p + 1 ; i < q ; i++ )
		{
			lazy[i] += c ;
		}
	}
}
int query(int l , int r)
{
	int p = pos[l] , q = pos[r] , ans = 0 ;
	if(p == q)
	{
		for( int i = l ; i <= r ; i++ )
		{
			ans += a[i] ;
		}
		ans += (r - l + 1) * lazy[p] ;
	}
	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] ;
		for( int i = p + 1 ; i < q ; i++ )
		{
			ans += sum[i] ;
			ans += (R[i] - L[i] + 1) * lazy[i] ;
		}
	}
	return ans ;
}
void work()
{
  cin >> n >> k ;
  for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
  init(n) ;
  for( int i = 1 ; i <= k ; i++ )
  {
  	int op ;
  	cin >> op ;
  	if(op == 1) 
		{
			int l , r , c ;
			cin >> l >> r >> c ;
			update(l , r , c) ;
		}
		else if(op == 2)
		{
			int c ;
			cin >> c ;
			update(1 , 1 , c) ;
		}
		else if(op == 3)
		{
			int c ;
			cin >> c ;
			update(1 , 1 , -c) ;
		}
		else if(op == 5) cout << query(1 , 1) << "\n" ;
  	else 
		{
			int l , r ;
			cin >> l >> r ;
			cout << query(l , r) << "\n" ;
		}
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

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

发现前缀和没啥用了，改为预处理分块内的值的升序序列。
修改时，前块和后块修改后暴力更改；中块改懒标记即可。
查询时，前块和后块修改后暴力求值；中块二分即可，记得还有懒标记。
CPP
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 5e4 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct Edge
{
	int v , nxt ;
}edge[kMaxN] ;
struct node
{
  int u , v ;
}Node[kMaxN] ;
int n , k ;
int L[kMaxN] , R[kMaxN] , sum[kMaxN] , a[kMaxN] , pos[kMaxN] , lazy[kMaxN] ;
vector<int> G[kMaxN] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
void init(int n)
{
	int len = sqrt(n) ;
	int 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] = min(R[num] , n) ;
	for( int i = 1 ; i <= num ; i++ )
	{
		for( int j = L[i] ; j <= R[i] ; j++ )
		{
			G[i].push_back(a[j]) ;
			pos[j] = i ;
		}
		sort(G[i].begin() , G[i].end()) ;
	}
}
void update(int l , int r , int c)
{
	int p = pos[l] , q = pos[r] ;
	if(p == q)
	{
		for( int i = l ; i <= r ; i++ )
		{
			a[i] += c ;
		}
		G[p].clear() ;
		for( int i = L[p] ; i <= R[p] ; i++ ) G[p].push_back(a[i]) ;
        sort(G[p].begin() , G[p].end()) ;
	}
	else
	{
		for( int i = l ; i <= R[p] ; i++ )
		{
			a[i] += c ;
		}
		G[p].clear() ;
		for( int i = L[p] ; i <= R[p] ; i++ ) G[p].push_back(a[i]) ;
        sort(G[p].begin() , G[p].end()) ;
		for( int i = L[q] ; i <= r ; i++ )
		{
			a[i] += c ;
		}
		G[q].clear() ;
		for( int i = L[q] ; i <= R[q] ; i++ ) G[q].push_back(a[i]) ;
        sort(G[q].begin() , G[q].end()) ;
		for( int i = p + 1 ; i < q ; i++ )
		{
			lazy[i] += c ;
		}
	}
}
int query(int l , int r , int x)
{
	int p = pos[l] , q = pos[r] , cnt = 0 ;
	if(p == q)
	{
		for( int i = l ; i <= r ; i++ )
		{
			cnt += (a[i] + lazy[p] < x) ;
		}
	}
	else
	{
		for( int i = l ; i <= R[p] ; i++ )
		{
			cnt += (a[i] + lazy[p] < x) ;
		}
		for( int i = L[q] ; i <= r ; i++ )
		{
			cnt += (a[i] + lazy[q] < x) ;
		}
		for( int i = p + 1 ; i < q ; i++ )
		{
			cnt += lower_bound(G[i].begin() , G[i].end() , x - lazy[i]) - G[i].begin() ;
		}
	}
	return cnt ;
}
void work()
{
  cin >> n ;
  for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
  init(n) ;
  for( int i = 1 ; i <= n ; i++ )
  {
  	int op ;
  	cin >> op ;
  	if(op == 0) 
		{
			int l , r , c ;
			cin >> l >> r >> c ;
			update(l , r , c) ;
		}
  	else 
		{
			int l , r , x ;
			cin >> l >> r >> x ;
			cout << query(l , r , x * x) << "\n" ;
		}
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...