分块1

Hhy140516 · 2025-07-31 21:56:10 · 个人记录

基础

分块就是把一个序列分成很多块，然后查询、修改时，对于整个块进行修改。

需要注意的是，分块只是一种思想，而不是一种算法。

写分块时，一般把长度设为 \sqrt{n}，当然，也有的题卡这个数，所以需要一些调整。

发现如果一整块都要修改时，如果都修改，时间很慢，所以用懒标记记录整个块的加减情况。

例题

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

这道题是分块的板子。

我们把块的长度是 \sqrt{n}，把每个块的情况统计清楚，初始化结束。

对于查询，分为前块、中块和后块，前块和后块进行暴力修改，否则用懒标记。

查询时就是值加上懒标记。

//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 ١١(❛ᴗ❛)【分块】-区间修改，区间查询

除了查询其他相同。

查询时和改的时候相同分成三段，前面直接暴力加答案，后面类似。中间的话，这一整块的和都要加起来，可以提前求解。

注意要把懒标记算进去。

//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 守墓人

与上题一摸一样。

对于 2 和 3 的询问，就是进行 1 到 1 的区间修改。

//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 ١١(❛ᴗ❛)【分块】-区间修改，区间小值查询

发现前缀和没啥用了，改为预处理分块内的值的升序序列。

修改时，前块和后块修改后暴力更改；中块改懒标记即可。

查询时，前块和后块修改后暴力求值；中块二分即可，记得还有懒标记。

//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 ;
}