根号分治

2024-05-07 | 阅读：次

===

Index

模板
区间加查询区间最小值
区间小于等于x的数量

模板

需要针对具体题目修改的部分

S: 待分块数据类型，一般是读入数据类型，按需选择int, long long, mint等。
T: 查询的答案数据类型
UNIT: 每个块的结果的单位元
op(x, y): 不同块的结果怎么合并，按需选择 sum, min, max等。
get_part(l, r): 零碎的块的结果统计，一般暴力遍历即可
get_all(l, r): 完整块的结果统计
update_part(l, r, x): 零碎的块更新，更新完需要维持整个块的性质
update_all(l, r, x): 完整的块更新，按需选择懒标记等，

template<int B_size = -1>
struct SqrtDecomposition{
  using S = int; // 待分块数据类型
  using T = int; // 答案数据类型
  vector<S> A;
  int B; // 分块大小
  int n; // 数组长度
  T UNIT;
  bool has_init;
  SqrtDecomposition(const int _n) : n(_n), has_init(false) {
    A.resize(_n);
    B = B_size == -1 ? sqrt(n) : B_size;
  }
  SqrtDecomposition(const vector<S>& v_) : has_init(false){
    A = v_;
    n = (int)(A.size());
    B = B_size == -1 ? sqrt(n) : B_size;
    init();
  }
  int get_end_from_start(int bucket_start) const {
    return bucket_start + B < n ? bucket_start + B : n;
  }
  int get_start_from_index(int idx) const {
    return idx - idx % B;
  }
  int get_end_from_index(int idx) const {
    return get_end_from_start(get_start_from_index(idx));
  }
  T op(const T &x, const T &y) const {
    return x+y;
  }
  void init(){
    has_init = true;
    UNIT=0;
    for (int i = 0, j = 0; i < n; i += B, j++) {
      ;
    }
  }
  T get_part(int l, int r) {
    
  }
  T get_all(int l, int r) {
  }
  void update_part(int l, int r, S x) {
    
  }
  void update_all(int l, int r, S x) {

  }
  void prod(int l, int r, S val) {
    if (!has_init) init();
    int x = l / B, y = (r - 1) / B;
    if (x == y) {
      update_part(l, r, val);
    } else {
      update_part(l, x * B + B, val);
      for (int i = x + 1; i < y; ++i) 
        update_all(i * B, i * B + B, val);
      update_part(y * B, r, val);
    }
  }
  T get(int l, int r) {
    if (!has_init) init();
    int x = l / B, y = (r - 1) / B;
    T res = UNIT;
    if (x == y) {
      res = op(res, get_part(l, r));
    } else {
      res = op(res, get_part(l, x * B + B));
      for (int i = x + 1; i < y; ++i) 
        res = op(res, get_all(i * B, i * B + B));
      res = op(res, get_part(y * B, r));
    }
    return res;
  }
};
// SqrtDecomposition<450> sd(n); 

区间加查询区间最小值

yukicoder 1234

长度为n的数组a，q次操作，分为两种类型

1 l r c : 对于 l <= i <= r 执行 a[i] += c
2 l r c : 求区间 [l,r]的最小值
1 <= n, q <= 1e5
-1e10 <= a[i] <= 1e10
-1e4 <= c <= 1e4

分析

可以线段树，这里讲分块思想，使用 lazy[i], mns[i] 维度每个块整体的加和，以及每个块的最小值。

时间复杂度 O(qsqrt(n))

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

using ll = long long;
template<int B_size = -1>
struct SqrtDecomposition{
  using S = long long; // 待分块数据类型
  using T = long long; // 答案数据类型
  vector<S> A;
  vector<long long> lazy, mns;
  int B; // 分块大小
  int n; // 数组长度
  T UNIT;
  bool has_init;
  SqrtDecomposition(const int _n) : n(_n), has_init(false) {
    A.resize(_n);
    B = B_size == -1 ? sqrt(n) : B_size;
  }
  SqrtDecomposition(const vector<S>& v_) : has_init(false){
    A = v_;
    n = (int)(A.size());
    B = B_size == -1 ? sqrt(n) : B_size;
    init();
  }
  int get_end_from_start(int bucket_start) const {
    return bucket_start + B < n ? bucket_start + B : n;
  }
  int get_start_from_index(int idx) const {
    return idx - idx % B;
  }
  int get_end_from_index(int idx) const {
    return get_end_from_start(get_start_from_index(idx));
  }
  T op(const T &x, const T &y) const {
    return min(x,y);
  }
  void init(){
    has_init = true;
    UNIT=1e18;
    int m=(n+B-1)/B;
    lazy.assign(m, 0);
    mns.resize(m);
    for (int i = 0, j = 0; i < n; i += B, j++) {
        mns[j] = *min_element(A.begin() + i, A.begin() + get_end_from_start(i));
    }
  }
  T get_part(int l, int r) {
    T res = 1e18;
    int b = l / B;
    for(int i=l;i<r;++i){
        if(A[i]+lazy[b]<res) res=A[i]+lazy[b];
    }
    return res;
  }
  T get_all(int l, int r) {
    return mns[l/B];
  }
  void update_part(int l, int r, S x) {
    int b = l / B;
    for (int i = l; i < r; ++i) {
        A[i] += x;
    }
    mns[b] = 1e18;
    for (int i = get_start_from_index(l); i < get_end_from_index(l); ++i) {
        mns[b] = min(mns[b], A[i] + lazy[b]);
    }
  }
  void update_all(int l, int r, S x) {
    lazy[l / B] += x;
    mns[l / B] += x;
  }
  void prod(int l, int r, S val) {
    if (!has_init) init();
    int x = l / B, y = (r - 1) / B;
    if (x == y) {
      update_part(l, r, val);
    } else {
      update_part(l, x * B + B, val);
      for (int i = x + 1; i < y; ++i) 
        update_all(i * B, i * B + B, val);
      update_part(y * B, r, val);
    }
  }
  T get(int l, int r) {
    if (!has_init) init();
    int x = l / B, y = (r - 1) / B;
    T res = UNIT;
    if (x == y) {
      res = op(res, get_part(l, r));
    } else {
      res = op(res, get_part(l, x * B + B));
      for (int i = x + 1; i < y; ++i) 
        res = op(res, get_all(i * B, i * B + B));
      res = op(res, get_part(y * B, r));
    }
    return res;
  }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n, q;
    cin >> n;
    SqrtDecomposition<350> s(n);
    for (auto &x : s.A){
        cin >> x;
    }
    s.init();
    cin >> q;
    for (int _i = 0; _i < q; ++_i) {
        int k, l, r, c;
        cin >> k >> l >> r >> c;
        l--;
        if (k == 1) {
            s.prod(l, r, c);
        } else {
            cout << s.get(l, r) << '\n';            
        }
    }
    return 0;
}

区间小于等于x的数量

spoj racetime

长度为n的数组a，q次操作，分为两种类型

C l r v : 查询区间小于等于v的元素数量
M i x : 赋值 a[i] = x
1 <= n, q <= 5e4
1 <= a[i], v <= 1e9

分析

维护每个块内有序，对于整块，可以二分查找小于等于某数的数量。

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

using ll = long long;

int V;
template<int B_size = -1>
struct SqrtDecomposition{
  using S = int; // 待分块数据类型
  using T = int; // 答案数据类型
  vector<S> A;
  vector<int> b;
  int B; // 分块大小
  int n; // 数组长度
  T UNIT;
  bool has_init;
  SqrtDecomposition(const int _n) : n(_n), has_init(false) {
    A.resize(_n);
    B = B_size == -1 ? sqrt(n) : B_size;
  }
  SqrtDecomposition(const vector<S>& v_) : has_init(false){
    A = v_;
    n = (int)(A.size());
    B = B_size == -1 ? sqrt(n) : B_size;
    init();
  }
  int get_end_from_start(int bucket_start) const {
    return bucket_start + B < n ? bucket_start + B : n;
  }
  int get_start_from_index(int idx) const {
    return idx - idx % B;
  }
  int get_end_from_index(int idx) const {
    return get_end_from_start(get_start_from_index(idx));
  }
  T op(const T &x, const T &y) const {
    return x+y;
  }
  void init(){
    has_init = true;
    UNIT=0;
    b=A;
    for (int i = 0, j = 0; i < n; i += B, j++) {
      sort(b.begin()+i, b.begin()+get_end_from_start(i));
    }
  }
  T get_part(int l, int r) {
    T res = 0;
    for(int i=l;i<r;++i){
      if(A[i]<=V){
        res++;
      }
    }
    return res;
  }
  T get_all(int l, int r) {
    return distance(b.begin()+l,upper_bound(b.begin()+l,b.begin()+r,V));
  }
  void update_part(int l, int r, S x) {
    int l1=get_start_from_index(l),r1=get_end_from_index(l);
    for(int i=l1; i<r1;++i){
      if(b[i]==A[l]){
        b[i]=x;
        while(i+1<r1&&b[i+1]<b[i]){
          swap(b[i],b[i+1]);i++;
        }
        while(i-1>=l1&&b[i-1]>b[i]){
          swap(b[i],b[i-1]);i--;
        }
        break;
      }
    }
    A[l]=x;
  }
  void update_all(int l, int r, S x) {

  }
  void prod(int l, int r, S val) {
    if (!has_init) init();
    int x = l / B, y = (r - 1) / B;
    if (x == y) {
      update_part(l, r, val);
    } else {
      update_part(l, x * B + B, val);
      for (int i = x + 1; i < y; ++i) 
        update_all(i * B, i * B + B, val);
      update_part(y * B, r, val);
    }
  }
  T get(int l, int r) {
    if (!has_init) init();
    int x = l / B, y = (r - 1) / B;
    T res = UNIT;
    if (x == y) {
      res = op(res, get_part(l, r));
    } else {
      res = op(res, get_part(l, x * B + B));
      for (int i = x + 1; i < y; ++i) 
        res = op(res, get_all(i * B, i * B + B));
      res = op(res, get_part(y * B, r));
    }
    return res;
  }
};
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n, q;
    cin>>n>>q;

    SqrtDecomposition<500> s(n);
    for (int i = 0; i < n; ++i) {
      cin >> s.A[i];
    }
    s.init();
    for (int _ = 0; _ < q; ++_) {
      char type;
      cin>>type;
      if (type == 'M') {
        int i;
        cin>>i>>V;
        i--;
        s.prod(i, i + 1, V);
      } else {
        int l, r;
        cin>>l>>r>>V;
        l--;
        int ans=s.get(l,r);
        printf("%d\n", ans);
      }
    }

    return 0;
}

king-yyf

king-yyf

根号分治

Index

模板

区间加查询区间最小值

区间小于等于x的数量