LuoguLOJUOJ分析Subtask1首先调用 MinMax(0,1e18,&a[1],&a[n]) 来求出 $a_1$ 和 $a_n$。然后不断调用 MinMax(a[i-1]+1,a[j+1]-1,&a[i],&a[j]) 即可求出整个序列。Subtask2首先调用 MinMax(0,1e18,&a[1],&a[n]) 来求出 $a_1...
LuoguLOJ分析可以发现这两条规则长得很像更相减损术,推一推可以得到最后那一步可以考虑实际意义,证明就不写了(如果没有修改的话就可以预处理 $i^2\varphi(i)$ 的前缀和然后数论分块计算了。然而现在还有若干次对于 $f(d,d)$ 的修改,可以想到用一个数据结构来维护。思考一下,我们在数论分块时需要进行 $\mathcal{O}(Q)$ 次修改和求 $\mathcal{O}(Q...
CodeforcesLuogu分析考虑一个贪心,即每次取贡献最大的一个,这里的贡献是 $k_i\times a_i+b_i$,其中 $k_i$ 表示前面选了的数量,$b_i$ 表示后面选了的 $a_i$ 的和。那么我们相当于要维护一些直线,支持区间斜率加、截距加和求全局最大值。考虑分块,对每块维护一个上凸壳,散块修改后重构、整块打标记即可。注意要把当前选出来的数删掉。代码// =======...
Luogu分析考虑莫队,在移动过程中用树状数组维护每种值的出现次数。这样子是 $\mathcal{O}(n\sqrt{n}\log n)$ 的,由于这是 Ynoi 所以过不了。由于转移是 $\mathcal{O}(\log n)$ 的,而逆序对数又是个可减的东西,所以可以考虑二次离线莫队。需要注意的是这里左端点的 $f$ 和右端点的 $f$ 是不一样的,一个是区间中比 $x$ 小的数的个数,...
Luogu分析先考虑没有修改怎么用分块做。一个想法是将序列分块,然后维护 $s_{i,j}$ 表示前 $i$ 块中 $j$ 的数量,然而这样子查询是 $\mathcal{O}(n)$ 的。因此我们再对值域分块,并再维护 $s'_{i,j}$ 表示前 $i$ 块中值在第 $j$ 块中的数的数量,询问时先把所求在值域的哪一块中求出来,再在这一块中求,复杂度 $\mathcal{O}(\sqrt{...
CodeforcesLuogu分析我们要让小于 $x$ 的数最少,即让大于等于 $x$ 的数最多。那么我们可以对于每个大于等于 $x$ 的 $a_i$,将能覆盖到它的左端点的区间加上 $1$,这样子查询 $[l,r]$ 中的最大值就可以得到答案了。仍然用上面的思路,但是我们考虑用分块维护这个区间加 $1$ 区间求最大值。这个很好分块维护:对于整块,我们直接打标记即可;对于散块,我们暴力加并更...
Luogu分析考虑分块。对于每一块,维护它的最大值 $mx$。可以发现 $\sum mx$ 是 $\mathcal{O}(n\sqrt{n})$ 级别的,因此每一块如果能够 $\mathcal{O}(x)$ 修改的话复杂度就是 $\mathcal{O}(n\sqrt{n})$。可以想到这样的修改方式如果 $2x\geq mx$,则直接将所有 $>x$ 的数减去 $mx$。这样子是 $\...
CodeforcesLuogu分析一个不要脑子的做法是线段树分治,即以时间为下标将所有物品与询问挂到线段树上,在线段树上递归时维护一个长度为 $4000$ 的 0/1 背包的 DP 数组即可。标解给的是一个奇妙的分块做法,大概是分成 $p$ 块,从每个交界点往左右跑 0/1 背包,然后每个询问一定会包含一个交界点,直接将左右合并即可。代码因为我懒所以只有第一个方法的代码。// =======...
Luogu分析考虑莫队。则我们需要实现一个支持单点修改、区间求和和非 $0$ 数的个数的东西。考虑用值域分块实现,对于每块维护内部的和和非 $0$ 数的个数即可。总时间复杂度 $\mathcal{O}(m\sqrt{n})$。代码// =================================== // author: M_sea // website: http://m-s...
Luogu分析先分块。先预处理出 $s_{i,j}$ 表示前 $i$ 块中 $j$ 的数量,以及 $f_{i,j}$ 表示第 $i$ 块到第 $j$ 块的众数。算答案时,显然答案要么是整块的 $f$,要么是角块中的某个数,枚举角块中数利用 $s$ 判断是否更多即可。具体实现和细节见代码。代码// =================================== // author:...