CF1588F Jumping Through the Array


题目描述你有个长度为 nnn 的数组 aaa 和一个长度为 nnn 的排列 ppp,对于每一个 iii 有一有向边 (i,pi)(i,p_i)(i,pi​)。有如下三种操作:1 l r 询问 ∑i=lrai\sum_{i=l}^r a_i∑i=lr​ai​。2 v x 将所有 vvv 能到达的节点所

[国家集训队]排队


题目描述题目传送门思路对于交换 $i , j$ 的数字,我们考虑交换这两个数字(记这两个数字分别为 $a,b$)对答案的贡献。显然,对于区间 $[i+1,j-1]$ 中每一个大于 $a$ 的数字会产生 $+1$ 的贡献,每一个小于 $a$ 的数字会产生 $-1$ 的贡献,每一个小于 $b$ 的数字会

分块


简介其实,分块是一种思想,而不是一种数据结构。从 NOIP 到 NOI 到 IOI,各种难度的分块思想都有出现。分块的基本思想是,通过对原数据的适当划分,并在划分后的每一个块上预处理部分信息,从而较一般的暴力算法取得更优的时间复杂度。分块的时间复杂度主要取决于分块的块长,一般可以通过均值不等式求出某

[COCI2009-2010#3] PATULJCI


题目描述题目传送门思路由于我特别喜欢暴力数据结构,于是我就用分块 AC 了这道题。显然我们可以按照 $\sqrt n$ 为一块,将颜色分块,对每一块统计出每种颜色的数量,对于每一次询问,我们对完整块 $O(c)$ 累加,块外元素暴力累加。最后扫一遍结果得出答案。时间复杂度 $O(cm\sqrt n)