当前位置: 首页 > news >正文

根号

一. 根号分治

精髓就是拼接两个暴力

1. 余数根号分治:Remainder Problem

首先直接单点更新O(1),查询暴力跳O(n)。这个暴力的有点在于当查询的x比较大的时候,那么跳的次数就比较少。
另一种暴力思路就是维护c[i][j]为%i = j的下标的数的和,那么更新就是O(n)的,查询则变成O(1)的了。
我们考虑分治 设阈值为B。
当x<=B时用暴力2 O(B) O(1)
x > B时用暴力1 O(1) O(n/B)
B = sqrt(n)时 B = n / B

if(op == 1)
{rep(i, 1, B) c[i][x % i] += y;a[x] += y;
}
else
{if(x <= B) cout << c[x][y] << '\n';else{int res = 0;for(int i = y; i <= 500000; i += x) res += a[i];cout << res << '\n';}
}

小变化

给定一个长度为 ( n ) 的序列 ( x )(元素编号从 ( 1 ) 开始),所有元素初始值为 ( 0 )。接下来进行 ( q ) 次操作,每次操作分为以下两种类型(操作含参数 ( a, b )):

设有长度为 n 的序列 \(x = (x_1, x_2, \dots, x_n)\),初始时满足全0

接下来进行 q 次操作,每次操作分为以下两类之一:

  1. 更新操作:给定 a, b,对所有满足 \(a \cdot i \le n\) 的正整数 \(i\),执行
    \(x_{a \cdot i} \leftarrow x_{a \cdot i} + b\).

  2. 查询操作:给定 \(a, b \; (a \le b)\),输出
    \(\sum_{i=a}^{b} x_i\).
    暴力1,直接跳着修改然后BIT查询,复杂度\(O(log(n) \times \sqrt{n})\)
    暴力2,对于每个修改直接记录tag[a]加了多少,查询时在区间内查看a的倍数有几个在区间内即为贡献 \(O(B)\)
    然后就可以对于a<=B用2,a>B用

http://www.hskmm.com/?act=detail&tid=18280

相关文章:

  • 【A】杂题选将
  • 有一个[1,5]的等概率随机函数fx(),在不改变fx()函数的情况下,利用fx()函数做出一个[1,7]的等概率随机函数。
  • WSL2 磁盘清理
  • 质因数分解
  • 关于OneBot的QQ机器人探索2
  • putty
  • 深入解析:PHP 8.0+ 高级特性深度探索:架构设计与性能优化
  • 客服系统源码二次开发
  • 喜讯!狮桥集团成为天津市行政执法监督企业联系点,共筑法治营商新环境!
  • redis实现分布式锁2
  • 题解:P7334 [JRKSJ R1] 吊打
  • 当不小心误触了一个事件该如何删除呢
  • 烧录工具使用方法大公开:实用说明文档奉上
  • 警惕新型XCSSET macOS恶意软件变种,专攻Xcode开发者
  • 前端面经-高级开发(华为od) - 实践
  • 2025权威排行榜:公众号编辑器Top 6深度测评,哪款最适合你
  • 个人简介
  • 【图床】存几张图
  • 完整教程:Sass:CSS 预处理器
  • DDL表操作
  • 第二周第五天2.5
  • yolo
  • 什么是 glTF:完整指南
  • 垃圾收集器与核心算法详解(上)
  • 在Debian系统上修改开源软件源代码制作patch - 教程
  • WSL2搭建wordpress遇到的一点问题
  • 需求的系统规划 3
  • 430亿美元押注英国,Salesforce 加码 AI 投资
  • C# 中 ref 和 out 的学习笔记
  • C# 序列化三种方式