Splendor White's blog

标签 · 分块

首页

关于

归档

算法数据结构题解数据结构分块排序

SPOJ Give Away 解题笔记

简直和 UVA-12003 Array Transformer 解题笔记 一模一样。 把这题写一遍单纯是为了巩固分块实现能力。 实际写起来还真的 WA 了一发,确实有很多易错的地方,绝知此事要躬行。 尤其是循环的对象问题。是循环原序列还是块序列?想清楚再写。 #include<bits/stdc++.h> #define N 500100 #define Q 100100 using namespace std; int n,x[N],q; int op,a,b,c; int id[N],len,num; vector<int> block[N]; inline void change(int a, int b){ int aid = id[a]; x[a] = ..

更多
算法数据结构题解数据结构分块排序树状数组

UVA-11990 Dynamic Inversion 解题笔记

题目来源 UVA - 11990 Dynamic Inversion Vjudge 页面 题意简述 将一个 n≤2×105n\le 2\times10^5n≤2×105 的排列逐个删去 m≤1×105m\le1\times10^5m≤1×105 个元素,问每次删除元素之前,排列中有多少个逆序对。 解题思路 本题和 UVA-12003 Array Transformer 解题笔记 几乎一模一样,都是分块并在每次修改后保持块内有序,由此可使用二分查找实现高效的查询。 在求逆序对数量初值的时候使用树状数组即可,此后每一次删掉一个数字就查询其左侧比它大的数的数量,在总逆序对数量中减掉即可。 保持块内有序的方式依然可以使用冒泡排序,减少一个 log⁡\loglog 。 与 UVA-12003 实在太像了,代码略..

更多
算法数据结构题解数据结构分块排序

UVA-12003 Array Transformer 解题笔记

题目来源 UVA - 12003 - Array Transformer Vjudge 页面 题意简述 长度为 n≤3×105n\le 3\times10^5n≤3×105 的序列做 m≤5×104m\le 5\times10^4m≤5×104 次操作,每次操作询问 [L,R][L,R][L,R] 之间小于 vvv 的数的个数 kkk ,然后将 apa_pap​ 修改为 ⌊u∗kR−L+1⌋\displaystyle \left\lfloor \frac{u*k}{R-L+1} \right\rfloor⌊R−L+1u∗k​⌋ 。 解题思路 显然这题用线段树是很容易解的,不过我把这个题当做分块的练习题来做,不使用任何树形数据结构。 假设块长为 sss 每次修改完后将 ppp 所在块内的数据排序,复杂度..

更多
算法数据结构题解数据结构分块

LOJ6280 分块入门 区间和 解题笔记

题目来源 LibreOJ 6280 数列分块入门 4 题意简述 序列区间加与查询区间和, n≤5×104n\le5\times 10^4n≤5×104 。 解题思路 分块,操作区间中不是整块的部分暴力求解,是整块的部分打标记。 重点在时间复杂度的计算上。 最坏复杂度为操作区间几乎覆盖整个序列时,此时中间的整块数量近似于 ns\displaystyle\frac{n}{s}sn​ ,两端的非整块长度为 2s2s2s 。忽略常数,单次操作最坏时间复杂度为 O(ns+s)\displaystyle O(\frac{n}{s}+s)O(sn​+s) 。 运用基本不等式 ns+s≥2ns⋅s=2n\displaystyle\frac{n}{s}+s\ge2\sqrt{\frac{n}{s}\cdot s}=2\..

更多