[BZOJ 3509] [CodeChef] COUNTARI (FFT+分块)
[BZOJ 3509] [CodeChef] COUNTARI (FFT+分块)题面给出一个长度为n的数组,问有多少三元组\((i,j,k)\)满足\(i<j<k,a_j-a_i=a_k-a_j\)\(n \leq 10^5, a_i \leq 30000\)分析记\(m=\max(a_...
LOJ2803 CCC2018 平衡树 数论分块、记忆化搜索
传送门题意差评，其实就是一个递推式：\(f_1 = 1 , f_i = \sum\limits_{j=2}^i f_{\lfloor \frac{i}{j} \rfloor}\)，然后求\(f_N\)的值首先\(\lfloor \frac{i}{j} \rfloor\)只有\(2\sqrt{i}\)...
BZOJ 2741: 【FOTILE模拟赛】L [分块 可持久化Trie]
题意：区间内最大连续异或和5点调试到现在....人生无望但总算A掉了一开始想错可持久化trie的作用了...可持久化trie可以求一个数与一个数集(区间中的一个数)的最大异或和做法比较明显，前缀和后变成选区间内两个元素异或最大考虑分块，预处理$f[i][j]$第i块到第j块选两个元素异或最大询问时两...
Bzoj 2301: [HAOI2011]Problem b(莫比乌斯反演+除法分块)
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x...
Codeforces Round #307 (Div. 2) E. GukiZ and GukiZiana 分块
E. GukiZ and GukiZianaTime Limit: 20 SecMemory Limit: 256 MB题目连接http://codeforces.com/contest/551/problem/EDescriptionProfessor GukiZ was playing with...
CH 4401/Luogu 4168 - 蒲公英 - [分块]
题目链接：传送门题目链接：https://www.luogu.org/problemnew/show/P4168题解：经典的在线求区间众数的问题，由于区间众数不满足区间可加性，所以考虑分块，假设分块长度为 $S$，则总共分成 $T=N/S$ 块，对于每个询问 $[l,r]$，设点 $l$ 在第 $p...
BZOJ2002 & LCT模板(分块不会搞)
题意:看题.某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿 着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置...
[bzoj] 3343 教主的魔法 || 带修改分块
原题长度为n的序列，有两种操作：1、[l,r]区间每个数+w2、询问[l,r]区间有多少个数>c记录lazy数组即可。#include<cstdio>#include<algorithm>#define N 1000010#define B 1010#define st...
BZOJ 3343 教主的魔法（分块）
题意：有一个1e6的数组，t次操作：将[l,r]内的值增加w，或者查询[l,r]内的值大于等于add的思路：分块，块大小为sqrt(n)，每次只需要暴力头尾两块，中间的整块打标记，对于查询查操作，块内排序然后二分即可复杂度O(T(sqrt(n)+sqrt(n)logn))代码：可以弄两个数组对应着写...
BZOJ 3343: 教主的魔法(分块+二分查找)
BZOJ 3343: 教主的魔法(分块+二分查找)3343: 教主的魔法Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1172 Solved: 526[Submit][Status][Discuss]这个题目为什么不能用线段树做事因为C的值不固定，...
Bzoj 3343: 教主的魔法 分块,二分
3343: 教主的魔法Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 821 Solved: 364[Submit][Status][Discuss]Description教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个...
BZOJ 3343: 教主的魔法 [分块]【学习笔记】
3343: 教主的魔法Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1172 Solved: 526[Submit][Status][Discuss]Description教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每...
洛谷P5110 块速递推 [分块]
传送门思路显然可以特征根方程搞一波（生成函数太累），得到结果：\[a_n=\frac 1 {13\sqrt{337}} [(\frac{233+13\sqrt{337}}{2})^n-(\frac{233+13\sqrt{337}}{2})^n]\]（其实我也不知道是不是，网上抄的，懒得算了）放在模...
CDOJ 1324 卿学姐与公主 分块
题目地址分块模板 #include<cstdio> #include<algorithm> #include<math.h> using namespace std; const int Nmax=; int num,block,l[Nmax],r[Nmax],n...
BZOJ 1798 (线段树||分块)的标记合并
我原来准备做方差的。。结果发现不会维护两个标记。。就是操作变成一个 a*x+b ，每次维护a ， b 即可加的时候a=1 ，b=v乘的时候a=v ，b=0 #include <cstdio> const long long Maxn=; long long a[Maxn],n,P,l,r...
P2261 [CQOI2007]余数求和 【整除分块】
一、题面P2261 [CQOI2007]余数求和二、分析参考文章：click here对于整除分块，最重要的是弄清楚怎样求的分得的每个块的范围。假设$ n = 10 ，k = 5 $$$ i : 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10 \\ \lflo...
P2261 [CQOI2007]余数求和[整除分块]
题目大意给出正整数 n 和 k 计算 \(G(n, k)=k\ \bmod\ 1 + k\ \bmod\ 2 + k\ \bmod\ 3 + \cdots + k\ \bmod\ n\) 的值 其中 \(k\ \bmod\ i\) 表示 k 除以 i 的余数。解析整除分块的一个典型例子。整除分块解决...
洛谷P2261 [CQOI2007] 余数求和 [数论分块]
题目传送门余数求和题目背景数学题，无背景题目描述给出正整数n和k，计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 m...
2020 CCPC Wannafly Winter Camp Day1 - I. K小数查询(分块)
题目链接：K小数查询题意：给你一个长度为$n$序列$A$，有$m$个操作，操作分为两种：输入$x，y，c$，表示对$i\in[x,y] $，令$A_{i}=min(A_{i},c)$输入$x，y，k$，表示询问区间$[x,y]$中的第$k$小数思路：数据范围不是很大，可以分块来做，记录每个块已经更新...
LOJ #6285 分块入门9
题意：区间众数，不带修改，带修改刚看了一眼没看懂cls在讲啥QAQ。题解：按照代码中那个sqrt(n/2/log2(n))大小分块，可以用均值不等式证明的，就是假设查询和n同级，然后一通爆算就可以得出了。然后预处理出(i,j)块之间最多的数。然后不满一块的部分在vector上二分，这题要先离散化。P...