loj数列分块入门(上)

简介: 数列分块入门入门 1-区间加法-单点查询入门 2-区间加法-区间查询入门 3-区间加法-单点查询入门 4-区间加法-区间查询入门 5-区间开方-区间查询

数列分块入门


入门 1-区间加法-单点查询


24ff5589ce924a7fb8647f805a4c99ad.png

ll n,a[maxn],lazy[maxn];
int main() {
  n = read;
  for(int i=1; i<=n; i++) a[i] = read;
  int blk = sqrt(n);
  for(int ii=1; ii<=n; ii++) {
    int op = read,l = read,r = read,c = read;
    if( op == 0) {
      for(int i=l; i<min(r+1,(l/blk+1)*blk); i++) {
        a[i] += c;
      }
      for(int i=l/blk+1; i<r/blk; i++) {
        lazy[i] += c;
      }
      if(l / blk != r / blk) {
        for(int i=r/blk*blk; i<=r; i++) a[i] += c;
      }
    } else {
      printf("%lld\n",a[r] + lazy[r/blk]);
    }
  }
  return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0
2
5
**/


入门 2-区间加法-区间查询


6e6026e88daa4d39957b647b1985ca54.png

const int maxn = 1e5 + 7;
ll n, a[maxn];
vector<ll> vet[maxn];
ll blk, lazy[maxn], b[maxn];
void reget(int id) {
    vet[id].clear();
    for (int i = (id - 1) * blk + 1; i <= min(n, id * blk); i++) {
        vet[id].push_back(a[i]);
    }
    sort(vet[id].begin(), vet[id].end());
}
void update(ll l, ll r, ll c) {
    for (int i = l; i <= min(b[l]*blk, r); i++)
        a[i] += c;
    reget(b[l]);
    if (b[l] != b[r]) {
        for (int i = (b[r] - 1) * blk + 1; i <= r; i++)
            a[i] += c;
        reget(b[r]);
    }
    for (int i = b[l] + 1; i <= b[r] - 1; i++) {
        lazy[i] += c;
    }
}
ll query(ll l, ll r, ll val) {
    ll ret = 0;
    for (int i = l; i <= min(b[l]*blk, r); i++) {
        if (a[i] + lazy[b[l]] < val)
            ++ ret;
    }
    if (b[l] != b[r]) {
        for (int i = (b[r] - 1) * blk + 1; i <= r; i++) {
            if (a[i] + lazy[b[r]] < val)
                ++ ret;
        }
    }
    for (int i = b[l] + 1; i <= b[r] - 1; i++) {
        int get = val - lazy[i];
        //      ret += upper_bound(vet[i].begin(),vet[i].end(),get) - lower_bound(vet[i].begin(),vet[i].end(),get);
        ret += lower_bound(vet[i].begin(), vet[i].end(), get) - vet[i].begin();
    }
    return ret;
}
int main() {
    n = read;
    for (int i = 1; i <= n; i++)
        a[i] = read;
    blk = sqrt(n);
    for (int i = 1; i <= n; i++) {
        b[i] = (i - 1) / blk + 1;
        vet[b[i]].push_back(a[i]);
    }
    for (int i = 1; i <= b[n]; i++)
        sort(vet[i].begin(), vet[i].end());
    for (int i = 1; i <= n; i++) {
        int op = read, l = read, r = read, c = read;
        if (op == 0)
            update(l, r, c);
        else
            printf("%lld\n", query(l, r, c * c));
    }
    return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2
3
0
2
**/


入门 3-区间加法-单点查询


86d3ffebdebe4a449b65d5b8897be280.png


const int maxn = 1e5 + 7;
ll n, a[maxn];
vector<ll> vet[maxn];
ll blk, lazy[maxn], b[maxn];
void reget(int id) {
    vet[id].clear();
    for (int i = (id - 1) * blk + 1; i <= min(n, id * blk); i++) {
        vet[id].push_back(a[i]);
    }
    sort(vet[id].begin(), vet[id].end());
}
void update(ll l, ll r, ll c) {
    for (int i = l; i <= min(b[l]*blk, r); i++)
        a[i] += c;
    reget(b[l]);
    if (b[l] != b[r]) {
        for (int i = (b[r] - 1) * blk + 1; i <= r; i++)
            a[i] += c;
        reget(b[r]);
    }
    for (int i = b[l] + 1; i <= b[r] - 1; i++) {
        lazy[i] += c;
    }
}
ll query(ll l, ll r, ll val) {
    ll ret = -1;
    for (int i = l; i <= min(b[l]*blk, r); i++) {
        if (a[i] + lazy[b[l]] < val)
            ret = max(ret, a[i] + lazy[b[l]]);
    }
    if (b[l] != b[r]) {
        for (int i = (b[r] - 1) * blk + 1; i <= r; i++) {
            if (a[i] + lazy[b[r]] < val)
                ret = max(ret, a[i] + lazy[b[r]]);
        }
    }
    for (int i = b[l] + 1; i <= b[r] - 1; i++) {
        ll get = val - lazy[i];
        vector<ll>::iterator l = lower_bound(vet[i].begin(), vet[i].end(), get);
        if (l == vet[i].begin())
            continue;
        l --;
        ret = max(ret, *l + lazy[i]);
    }
    return ret;
}
int main() {
    n = read;
    for (int i = 1; i <= n; i++)
        a[i] = read;
    blk = sqrt(n);
    for (int i = 1; i <= n; i++) {
        b[i] = (i - 1) / blk + 1;
        vet[b[i]].push_back(a[i]);
    }
    for (int i = 1; i <= b[n]; i++)
        sort(vet[i].begin(), vet[i].end());
    for (int i = 1; i <= n; i++) {
        int op = read, l = read, r = read, c = read;
        if (op == 0)
            update(l, r, c);
        else
            printf("%lld\n", query(l, r, c));
        //      debug(i);
    }
    return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
3
-1
**/


入门 4-区间加法-区间查询


61c58380409f49ae95f89b3068249050.png


ll n,a[maxn];
ll blk,lazy[maxn],b[maxn],sum[maxn];
void update(ll l,ll r,ll c) {
  for(int i=l; i<=min(b[l]*blk,r); i++) a[i] += c,sum[b[l]] += c;
  if(b[l] != b[r]) {
    for(int i=(b[r] - 1) * blk+1; i<=r; i++) a[i] += c,sum[b[r]] += c;
  }
  for(int i=b[l]+1; i<=b[r] - 1; i++) {
    lazy[i] += c;
  }
}
ll query(ll l,ll r,ll val) {
  ll ret = 0;
  for(int i=l; i<=min(b[l]*blk,r); i++) {
    ret += a[i] + lazy[b[l]];
    ret %= (val + 1);
  }
  if(b[l] != b[r]) {
    for(int i=(b[r]-1)*blk+1; i<=r; i++) {
      ret += a[i] + lazy[b[r]];
      ret %= (val + 1);
    }
  }
  for(int i=b[l]+1; i<=b[r]-1; i++) {
    ll add = lazy[i] * blk % (val + 1);
    ret += (sum[i] + add) % (val + 1);
    ret %= (val + 1);
  }
  return ret;
}
int main() {
  n = read;
  for(int i=1; i<=n; i++) a[i] = read;
  blk = sqrt(n);
  for(int i=1; i<=n; i++) {
    b[i] = (i - 1) / blk + 1;
    sum[b[i]] += a[i];
  }
  for(int i=1; i<=n; i++) {
    int op = read,l = read,r = read,c = read;
    if(op == 0) update(l,r,c);
    else printf("%lld\n",query(l,r,c));
  }
  return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
1
4
**/


入门 5-区间开方-区间查询


41aa87339eab4d2382670622f191bd65.png


ll n,a[maxn];
ll blk,lazy[maxn],b[maxn],sum[maxn];
bool vis[maxn];
bool check(int id) {
  if(vis[id]) return true;
  for(int i=(id-1)*blk+1; i<=min(n,blk*id); i++) {
    if(a[i] > 1) return false;
  }
  return vis[id] = 1;
}
void update(ll l,ll r) {
  if(!check(b[l])) {
    for(int i=l; i<=min(b[l]*blk,r); i++) {
      sum[b[l]] -= a[i];
      a[i] = sqrt(a[i]);
      sum[b[l]] += a[i];
    }
  }
  if(b[l] != b[r] && !check(b[r])) {
    for(int i=(b[r]-1)*blk+1; i<=r; i++) {
      sum[b[r]] -= a[i];
      a[i] = sqrt(a[i]);
      sum[b[r]] += a[i];
    }
  }
  for(int i=b[l]+1; i<=b[r]-1; i++) {
    if(!check(i)) {
      sum[i] = 0;
      for(int j=(i-1)*blk+1; j<=i*blk; j++) {
        a[j] = sqrt(a[j]);
        sum[i] += a[j];
      }
    }
  }
}
ll query(ll l,ll r) {
  ll ret = 0;
  for(int i=l; i<=min(b[l]*blk,r); i++) {
    ret += a[i];
  }
  if(b[l] != b[r]) {
    for(int i=(b[r]-1)*blk+1; i<=r; i++) {
      ret += a[i];
    }
  }
  for(int i=b[l]+1; i<=b[r]-1; i++) {
    ret += sum[i];
  }
  return ret;
}
int main() {
  n = read;
  for(int i=1; i<=n; i++) a[i] = read;
  blk = sqrt(n);
  for(int i=1; i<=n; i++) {
    b[i] = (i - 1) / blk + 1;
    sum[b[i]] += a[i];
  }
  for(int i=1; i<=n; i++) {
    int op = read,l = read,r = read,c = read;
    if(op == 0) update(l,r);
    else printf("%lld\n",query(l,r));
  }
  return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
6
2
**/


目录
相关文章
|
算法 容器
算法:双指针解决数组划分和数组分块问题
算法:双指针解决数组划分和数组分块问题
|
9月前
|
搜索推荐 C++
掌握归并排序:理解原理并用C++实现
掌握归并排序:理解原理并用C++实现
51 1
|
9月前
|
存储 人工智能 Java
每日一题《剑指offer》数组篇之构建乘积数组
每日一题《剑指offer》数组篇之构建乘积数组
51 0
每日一题《剑指offer》数组篇之构建乘积数组
|
9月前
|
存储 BI
【剑指offer】-构建乘积数组-42/67
【剑指offer】-构建乘积数组-42/67
|
机器学习/深度学习 存储
【每日易题】求二进制中1的个数——三种非常巧妙的解题思路
【每日易题】求二进制中1的个数——三种非常巧妙的解题思路
97 0
|
算法
7-2 整除分块
7-2 整除分块
97 0
|
人工智能 vr&ar
数列分块入门 1 (单点查值,区间加法)
数列分块入门 1 (单点查值,区间加法)
92 0
|
存储 人工智能 算法
剑指offer 74. 构建乘积数组
剑指offer 74. 构建乘积数组
68 0
|
算法 JavaScript 前端开发
日拱算法:双指针解“压缩字符串”
给你一个字符数组 chars ,请使用下述算法压缩: 从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 : 如果这一组长度为 1 ,则将字符追加到 s 中。 否则,需要向 s 追加字符,后跟这一组的长度。 压缩后得到的字符串 s 不应该直接返回 ,需要转储到字符数组 chars 中。需要注意的是,如果组长度为 10 或 10 以上,则在 chars 数组中会被拆分为多个字符。 请在 修改完输入数组后 ,返回该数组的新长度。
|
人工智能
LOJ—— 数列分块入门 2
LOJ—— 数列分块入门 2
96 0