公司建设网站记什么费用,网站刷链接怎么做,织梦网站栏目字体怎么调,嘉兴seo网站排名优化文章目录 1. 根号分治哈希冲突 2. 线性分块引入教主的魔法[CQOI2011] 动态逆序对[国家集训队] 排队[HNOI2010] 弹飞绵羊蒲公英 1. 根号分治
哈希冲突
题目1 n n n 个数#xff0c; m m m 次操作。操作 1 为修改某一个数的值#xff0c;操作 2 为查询所有满足下标模 x x x … 文章目录 1. 根号分治哈希冲突 2. 线性分块引入教主的魔法[CQOI2011] 动态逆序对[国家集训队] 排队[HNOI2010] 弹飞绵羊蒲公英 1. 根号分治
哈希冲突
题目1 n n n 个数 m m m 次操作。操作 1 为修改某一个数的值操作 2 为查询所有满足下标模 x x x 等于 y y y 的数之和。 先来看两个暴力算法 算法 1 修改直接修改。时间复杂度 O ( 1 ) O(1) O(1) 。 查询枚举下标模 x x x 等于 y y y 的数的和。时间复杂度 O ( n ) O(n) O(n) 。 算法 2 先预处理出 f ( i , j ) f(i,j) f(i,j) 表示下标模 i i i 等于 j j j 的数之和。时间复杂度 O ( n 2 ) O(n^2) O(n2) 。 修改修改所有 i i i 下的 f ( i , x m o d i ) f(i,x\bmod i) f(i,xmodi)。时间复杂度 O ( n ) O(n) O(n) 查询直接查询。时间复杂度 O ( 1 ) O(1) O(1)。
容易想到划定一个界限 B B B 选择使用的算法。
当 x x x 较大时即 x B xB xB 时算法 1 的查询次数会较小复杂度 O ( N B ) O(\frac N B) O(BN) 。
当我们仅用算法 2 处理模数 i i i 较小的情况时即 i ≤ B i\le B i≤B 时算法 2 复杂度会较低预处理复杂度 O ( B 2 ) O(B^2) O(B2)修改复杂度 O ( B ) O(B) O(B)。
总时间复杂度 O ( B 2 m ( N B B ) ) O(B^2m(\frac N B B)) O(B2m(BNB))。在 B N B\sqrt N BN 时复杂度最低。
代码 2. 线性分块
引入
题目 给定 n n n 个数 a [ 1.. n ] a[1..n] a[1..n] m m m 次操作区间修改区间查询。 我们将数列分段设块长为 B B B。
对于区间 [ L , R ] [L,R] [L,R] 的询问 若 L , R L,R L,R 在同一个块内直接暴力枚举 [ L , R ] [L,R] [L,R] 统计。 若 L , R L,R L,R 不在同一个块内则将 [ L , R ] [L,R] [L,R] 分成左右两个散块以及中间若干整块。对于每个整块我们事先预处理出每个整块的 b i ∑ a i b_i\sum a_i bi∑ai。对于散块暴力统计。 时间复杂度至多 O ( B N B ) O(B\frac N B) O(BBN) 。
对于区间 [ L , R ] [L,R] [L,R] 的修改 若 L , R L,R L,R 在同一个块内直接暴力枚举 [ L , R ] [L,R] [L,R] 修改。 若 L , R L,R L,R 不在同一个块内则将 [ L , R ] [L,R] [L,R] 分成左右两个散块以及中间若干整块。对于每个整块我们修改整块的 b i b_i bi。对于散块暴力修改。 时间复杂度至多 O ( B N B ) O(B\frac N B) O(BBN) 。 B N B\sqrt N BN 时最优。
代码 教主的魔法
题目 给定 n n n 个数 m m m 次操作。区间修改区间查询有多少个数 ≥ k \ge k ≥k。 设块长为 B B B。 对于区间 [ L , R ] [L,R] [L,R] 的询问 与上题基本一样但是我们需要快速统计出整块中有多少个 ≥ k \ge k ≥k 的数。考虑将所有整块内元素排序后二分查找。 时间复杂度至多 O ( B N B log B ) O(B\frac N B \log B) O(BBNlogB) 。 对于区间 [ L , R ] [L,R] [L,R] 的修改 修改整块并不会改变排序后的相对位置记录标记表示增加的量即可。 而对于散块的修改可能会改变所在块的相对位置我们暴力修改后重新排序。 时间复杂度至多 O ( B log B N B ) O(B \log B \frac N B) O(BlogBBN) 。
复杂度最低时 B B B 的大小应该为 N \sqrt N N 左右略大于 N \sqrt N N 取 N \sqrt N N 也能过。
代码
同类题 Array Transformer (附代码) [CQOI2011] 动态逆序对
题目 给定 n n n 个数的一个排列 m m m 此操作。每次删一个数问删前逆序对个数。 删除一个数后逆序对数量会减少这个数的贡献。第 i i i 个数的贡献为 [ 1 , i ) [1,i) [1,i) 中比 i i i 大的个数加上 ( i , n ] (i,n] (i,n] 中比 i i i 小的个数。和上一题类似可以用二分或者树状数组解决。
代码 [国家集训队] 排队
题目 给定 n n n 个数 h 1 . . . h n h_1...h_n h1...hn m m m 次操作。每次操作交换两个数问操作前的逆序对个数。 和上一题一样考虑两个数交换前和交换后的贡献。
代码
双倍经验 Anton and Permutation (附代码) [HNOI2010] 弹飞绵羊
题目
题意见题面。
考虑预处理出 s t e p [ x ] step[x] step[x] 表示从 x x x 处开始弹几步能弹到下一块 p o s [ x ] pos[x] pos[x] 表示从 x x x 开始第一次弹到下一块的位置在哪里。
查询每次跳到下一块复杂度为 O ( N B ) O(\frac N B) O(BN) 。 修改记修改点为 x x x 所在块为 B B B 块对应区间为 [ L B , R B ] [L_B,R_B] [LB,RB] 那么可能会对 [ L B , x ] [L_B,x] [LB,x] 上的点的 p o s pos pos 和 s t e p step step 造成影响。复杂度 O ( B ) O(B) O(B)。 B N B\sqrt N BN 。
代码
双倍经验 Holes (附代码) 蒲公英
题目 静态求区间众数强制在线。 分析 n ≤ 4 × 1 0 4 , a ≤ 1 0 9 n\le 4 \times 10 ^ 4, a\le 10^9 n≤4×104,a≤109 考虑离散化。 由于众数不满足一些性质如可加性等无法方便的用一些数据结构维护出来考虑分块。
Solution
我们将序列分成 K K K 段每段长度 N K \frac {N}{K} KN 左右。
对于一次询问 [ l , r ] [l,r] [l,r] 将其划分为若干整块和两块散块
那么答案一定为蓝色区间的众数或者红色区间出现过的数字。
考虑预处理出任意 i i i 到 j j j 块间的众数来快速求出蓝色区间的众数预处理时间复杂度 O ( K 2 N ) O(K^2N) O(K2N)。
// cnt[i][j][x] : x 在 i 到 j 块间出现的次数
// num[i][j] : i 到 j 块间的众数for(int i1; in; i){int B ceil((1.0 * i) / (1.0 * len));belong[i] B;cnt[B][B][a[i]] ;}for(int i1; in; i){int B ceil((1.0 * i) / (1.0 * len));if(cnt[B][B][a[i]] cnt[B][B][num[B][B]] a[i] num[B][B]) num[B][B] a[i];if(cnt[B][B][a[i]] cnt[B][B][num[B][B]]) num[B][B] a[i];}for(int i1; ik; i)for(int ji1; jk; j)for(int x1; xtot; x){cnt[i][j][x] cnt[i][j-1][x] cnt[j][j][x];if(cnt[i][j][x] cnt[i][j][num[i][j]] x num[i][j]) num[i][j] x;if(cnt[i][j][x] cnt[i][j][num[i][j]]) num[i][j] x;}
对于每次询问我们 O ( 1 ) O(1) O(1) 求蓝色区间的众数 O ( N K ) O(\frac N K) O(KN) 枚举红色区间的数计算 [ l , r ] [l,r] [l,r] 的众数询问时间复杂度 O ( M N K ) O(M \frac N K) O(MKN)。
总时间复杂度 O ( N K 2 M N K ) O(NK^2M \frac N K) O(NK2MKN)如果我们认为 N , M N,M N,M 同构那么 K N 1 3 KN^{\frac 1 3} KN31 时复杂度最低。
代码
