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月前
|
消息中间件 资源调度 Java
实时计算 Flink版产品使用合集之部署yarn模式,怎么实现峰谷动态并行度扩容缩容
实时计算Flink版作为一种强大的流处理和批处理统一的计算框架,广泛应用于各种需要实时数据处理和分析的场景。实时计算Flink版通常结合SQL接口、DataStreamAPI、以及与上下游数据源和存储系统的丰富连接器,提供了一套全面的解决方案,以应对各种实时计算需求。其低延迟、高吞吐、容错性强的特点,使其成为众多企业和组织实时数据处理首选的技术平台。以下是实时计算Flink版的一些典型使用合集。
|
8月前
|
NoSQL Redis C语言
[hiredis 的Redis执行语句返回结果类型全说明
[hiredis 的Redis执行语句返回结果类型全说明
86 1
|
8月前
|
Kotlin
Kotlin注释
Kotlin注释
203 0
|
9月前
|
前端开发 数据库
返回参数不用实体类,用map返。resultType=“Map“,以及使用map不返回空的值解决办法,
返回参数不用实体类,用map返。resultType=“Map“,以及使用map不返回空的值解决办法,
295 1
|
7月前
|
Linux 测试技术 网络安全
【好玩的开源项目】Linux系统之部署adarkroom文字风格冒险小游戏
【7月更文挑战第15天】Linux系统之部署adarkroom文字风格冒险小游戏
145 4
|
7月前
|
前端开发 JavaScript 开发者
学习CSS动画的高级技巧
【7月更文挑战第1天】学习CSS动画的高级技巧
72 2
|
8月前
|
Linux Shell 数据安全/隐私保护
【Linux】Linux的权限_1
【Linux】Linux的权限_1
41 0
|
机器学习/深度学习 PyTorch 算法框架/工具
计算机视觉PyTorch实现图像分类(二) - AlexNet
计算机视觉PyTorch实现图像分类(二) - AlexNet
186 0
|
设计模式 存储 JSON
设计模式再探-备忘录模式
最近在做一学期的语文课,每一节课结束的时候,需要将这节课上到哪儿了给记录下来;以便于下次再上课的时候接着上,这样一个需求。
|
数据可视化
关于Revit与Navisworks的互操作性(interoperability)
关于Revit与Navisworks的互操作性(interoperability)
关于Revit与Navisworks的互操作性(interoperability)

热门文章

最新文章