分块

与值域有关的问题（非权值线段树）——运用分块：1004T1

区间小于等于某值区间加显然同时涉及区间和值域，不能用log级ds来做，常见套路就是上分块这题是个复合题，后面就是个组合数 #include<bits/stdc.h> using namespace std; #define int long long inline int read(){int x0,f1;char c…

[CF1083F]The Fair Nut and Amusing Xor

Description 给出两个长度为n的序列A和B，定义一次操作为，选择A中一个长度为k的区间，将这个区间内的元素异或上x，x为你选择的数。我们认为A和B的相似度为将A和B变为相等的最小的操作次数。现在有Q次操作，每次操作会修…

【WinterCamp 2013】模积和

Description 求∑i1n∑j1,j≠im(nmodi)∗(mmodj)n,m<10^9，答案模19940417Solution 首先，看到有%，心里很不爽，把它变成n−⌊ni⌋∗i，对于i≠j的情况，后面减去就可以了。我们设n<m于是原式就变成了 …

[51nod1244]莫比乌斯函数之和

Description 求∑ilrμ(i)l,r<10^10Solution 设M(n)∑i1nμ(i)我们知道，∑d|nμ(d)[n1]那么1∑i1n∑d|iμ(d)∑T1n∑d|Tμ(d)∑i1n∑d1⌊ni⌋μ(d)∑i1nM(⌊ni⌋)于是，M(n)1−∑i2nM(⌊ni⌋)后面的东西可以用分块来加速。然后打上记忆化标记。或者…

【GDOI2018模拟8.12】区间第k小

Description 给出一个长度为n的序列a，q次询问某个区间[l,r]中的区间第k小，注意如果一个数的出现次数大于w就把它当成n 询问强制在线 n,q,ai<10^5 Solution Orz 数据结构根号算法讲师首先如果询问可以离线怎么做？ 一个显然的思路就…

【2011集训队出题】Crash的数字表格

Description 求∑i1n∑j1mlcm(i,j)n,m<10^7Solution （注意，以下内容默认n<m） 看着lcm不爽，把它变一变： ∑i1n∑j1mijgcd(i,j)莫比乌斯反演常用，枚举gcd ∑d1n1d∑i1n∑j1,gcd(i,j)dmij设f(d)∑i1…

BZOJ2453: 维护队列（分块）

传送门题意： 给一个序列，每个位置对应一个值，支持下面两种操作： 1.修改某个位置的值。 2.询问(l,r)区间内不同值的个数。题解： 1.考虑分块：统计ans[i][j]表示第i块到第j块的个数，容易发…

【NOIP2013模拟联考7】数列

Description 给出一个序列，每个数由一个二元组(a,b)表示，有4中操作 1：把a值在l~r范围内的数乘上x再加上y 2：把b值在l~r范围内的数乘上x再加上y 3：询问a值在l~r范围内的数的和。 4：询问b值在l~r范围内的…

[bzoj1257][CQOI2007]余数之和sum

Description 给出n,k，求∑i1nkmodin,k<10^9Solution 又是一道水题。（最近比较颓） 所以说嘛，做人呢，还是需要一定的姿势水平，像我这种蒟蒻呀，就只能不断地用手划水。看着%不爽&#xff0…

【WC模拟】J

Description 由于题面过于丧心病狂就直接贴图了 Solution 可以把每个操作变成2进制的异或操作。那么就是修改加询问前缀异或和为st的数的个数。线段树\分块都可以做啊。一个优化：有用的状态只有16种，可以提前处理出来。 Code #include <…

BZOJ2724: [Violet 6]蒲公英（分块）

传送门题意给一个数列，求区间众数（若有多个则输出较小值）。题解考虑分块，对于块i维护cnt[i][val]表示从第一块到i块中val出现了几次，维护ans[i][j]表示从第i块到第j块的众数（之后会用）。…

算法竞赛进阶指南---0x44 蒲公英（分块）

题面题解(分块) 本题是经典的在线求众数问题。因为众数不具有"区间可加性"(已知序列a中区间[x,y]的众数和区间[y1,z]的众数，不能直接得到[x,z]的众数，所以用树状数组或线段是维护就十分困难)，这里我们用分块的方法来做&#xff0c…

A Simple Problem with Integers

原题传送门题目 Description You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given i…

[Ynoi2017]舌尖上的由乃

Description 维护区间加和区间第k小。 n<100000 Solution 分块，设块大小为k相信大家都会O(n/k log^2 n)的查询和O(k)的修改。什么你不会O(k)的修改？归并啊归并啊。那么平衡规划一下kn√logn总复杂度O(nn√logn)Code #include <cstdio>…

bzoj 4241: 历史研究

Description IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。日记中记录了连续N天发生的时间，大约每天发生一件。事件有…

算法竞赛进阶指南---一个简单的整数问题2 （分块）

题面题解分块的基本思想：通过适当的划分，预处理一部分信息并保存下来，用空间换取时间，以达到时空平衡。通过表我们也有看出，分块的效率比不上树状数组和线段树，但是它更通用，容易实现。回忆&…

Codeforces Educational Codeforces Round 56 (Rated for Div. 2) 1093E. Intersection of Permutations

求区间a[l,r]a[l,r]a[l,r]中b[x,y]b[x,y]b[x,y]的数字出现了多少个。因为a,ba,ba,b均是排列，所以区间数字分布具有可加性。所以分块树状数组，时间复杂度约为O(n3/2lg⁡n)≈2e55e2202e9\mathrm{O}(n^{3/2}\lg n)\approx 2e5\times 5e2\times 202e9O(n3/…

长链贪心+虚树+类直径合并性+分块建树维护ST表：1008T4

http://47.92.197.167:5283/contest/408/problem/4 两个可以推的经典套路： 我们可以对所有点建序树，然后取前 k k k 大。而取前 k k k 大可以通过以直径端点为根长剖来贪心直径具有合并性（不仅是连通块，而且是点集&#xff09…

BZOJ3343: 教主的魔法（分块）

传送门题意给你一个序列，每个序列有一个值。支持两种操作: 1.区间加减。 2.区间查询比C小的数的个数。题解有想法的人可以看出树套树可做。时间复杂度O(m⋅log2n)。当然没想法的人可以直接写暴力，分块大法好。。时间复杂度O(m⋅n√⋅logn√)…

BZOJ2821: 作诗(Poetize)（分块）

传送门题意给你一个区间，每次查询(l,r)，问(l,r)中数字出现偶数次的种类数。题解分块大法好。。。分析： 1.查询(l,r)中的数字出现偶数次的种类数，可以等价于完整块中数字种类数及不完整块中数字种类数（前半部…

【每日一题】区域和检索 - 数组可修改

文章目录 Tag题目来源解题思路方法一：分块方法二：线段树方法三：树状数组写在最后 Tag 【树状数组】【线段树】【分块】【前缀和】【设计类】【2023-11-13】题目来源 307. 区域和检索 - 数组可修改解题思路使用前缀和解决不行吗&#x…

bzoj 4320: ShangHai2006 Homework

Description 1：在人物集合 S 中加入一个新的程序员，其代号为 X,保证 X 在当前集合中不存在。 2：在当前的人物集合中询问程序员的mod Y 最小的值。 （为什么统计这个？因为拯救过世界的人太多了，只能取模&…

bzoj 2741: 【FOTILE模拟赛】L

Description FOTILE得到了一个长为N的序列A，为了拯救地球，他希望知道某些区间内的最大的连续XOR和。即对于一个询问，你需要求出max(Ai xor Ai1 xor Ai2 ... xor Aj)，其中l<i<j<r。为了体现在线操作，对于一个询…

【HNOI2016模拟4.10】 K小数查询

Description 维护一个长度为n的序列，使得其支持m次操作，包括区间插入和区间求k小数。 n,m<80000,在任何时候|ai|<5000000 Solution 一看到区间第k大/小，就想到了主席树。但这个是区间修改！ 怎么做呢？ &a…

[51nod1239]欧拉函数之和

Description 求∑i1nφ(i)n<10^10Solution 这道题和莫比乌斯函数一行，都可以通过神奇的推导的出结论。我们设ϕ(n)∑i1nφ(i)众所周知，∑d|nφ(d)n那么，φ(n)n−∑d|n,d<nφ(d)于是ϕ(n)∑i1n(i−∑d|i,d<iφ(d))ϕ(n)n∗(n1)2−…

莫队算法模板题

莫队算法可解决的类型题： 给定n个数，有q次询问，每次询问一个区间的某个属性（因题而异）。关于莫队算法的详解见以下博客： https://blog.csdn.net/ThinFatty/article/details/72581276 https://blog.csdn.n…

[51nod1223]分数等式的数量

Description 给出一个数L，求所有的x < y <l且满足1/x1/y1/n（n为整数）的(x,y)二元组的数量。 L<10^11 Solution 复杂度近似暴力的算法碾过去了w 安利一份更劲的题解首先我们就相当于求xy|xy的二元组的数量提取一个dgcd(x,y)…

[BZOJ2122]工作评估

Description 给出一个长度为n的序列，第i天有状态值Di和评估上限Li 若当前的评估值为x0，第i天后会变成min(x0Di,Li) 需要回答q次询问，第i次询问给出L,R,x0，求[L,R]的一个子区间[l,r]使得经过这些天之后最后的评估值最大。 n,q<…

bzoj 2821: 作诗(Poetize)

Description 神犇SJY虐完HEOI之后给傻LYD出了一题： SHY是T国的公主，平时的一大爱好是作诗。由于时间紧迫，SHY作完诗之后还要虐OI，于是SHY找来一篇长度为N的文章，阅读M次，每次只阅读其中连续的一段[l,r]&am…

数论与线性代数——整除分块【数论分块】的【运用】【思考】【讲解】【证明(作者自己证的QWQ)】

文章目录整除分块的思考与运用整除分块的时间复杂度证明 & 分块数量整除分块的公式 & 公式证明公式证明代码code↓ 整除分块的思考与运用整除分块是为了解决一个整数求和问题题目的问题为： ∑ i 1 n ⌊ n i ⌋ \sum_{i1}^{n} \left \lfloor \frac{n}{…

【清华集训2017模拟11.29】K小数查询

Description 维护一个数据结构，资瓷区间取min和区间求k小值。 n<8*1e4 Solution 和由乃OI那题很像，直接分块，块内归并重构，二分答案块内二分查询。只不过比较良心的是JZOJ上不卡常，但是我块大小开n√lognT了&…

BJ模拟等差数列（分块+FFT）

Description 给定N个整数 A1,A2,⋯AN，求有多少个三元组 (i,j,k)满足 1≤i<j<k≤N且 Aj−AiAk−Aj。Input 第一行一个正整数 N(3≤N≤105)第二行 N个整数 A1,A2,⋯,AN， 1≤Ai≤3104Output 输出一个整数表示答案。Sample Input 10 3 5 3 6 3 4 10 4 …

[51nod1192]gcd表中的质数

Description 求∑i1n∑j1me(gcd(i,j)是质数)T<1000,n,m<5*10^6Solution 经典反演套路题，貌似没有其他做法（其他做法的大爷不要鄙视蒟蒻w） 复习一下莫比乌斯反演，所以就来打了这道题首先约定n<m设Fd表示∑ni1∑mj1e(…

$2019南昌网络赛 H. The Nth Item（广义斐波那契数列求通项公式模板）（二次剩余+分块）$