louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共160篇）

「分块系列」公主的朋友解题报告

公主的朋友 Description Problem 由于\(Wulala\)在上个问题中的精彩表现，公主认为\(Wulala\)是一个很棒的人，就把\(Wulala\)留在了\(X\)国。这时正好公主的一位传教士朋友来拜访公主，于是想找\(wulala\)帮忙。 \(X\)国如同一条直线，...

2018-12-01

0 398

「分块系列」「洛谷P4168 [Violet]」蒲公英解题报告

蒲公英 Description 我们把所有的蒲公英看成一个长度为\(n\)的序列(\(a_1,a_2,...a_n\))，其中\(a_i\)为一个正整数，表示第i棵蒲公英的种类的编号。每次询问一个区间\([l,r]\)，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同...

2018-12-01

0 476

「分块系列」数列分块入门9 解题报告

数列分块入门9 题意概括静态，区间求众数。写在前面还记得分块1就提到的关于块的大小有时要通过计算么？？在这里就得到了体现！正题为了方便起见，我们设把数列分成K块~ 这道题很值得思考。先离散化~ 然后记录位置~ 我们可以考虑，对于L ~ R之间的众数只有可能是以下三种情况...

2018-12-01

0 474

「分块系列」数列分块入门8 解题报告

数列分块入门8 题意概括区间修改，区间计数。写在前面感叹~ 分块真是玄之又玄|(￣0￣) 正题跟分块7类似的是，这题也运用还原。 v数组用来记录一个分块是否都为一个数，f数组来记录如果都为一个数，那么这个数是什么(实际上可以用只一个数组来记录QAQ) 查询时，对于都为一个数的...

2018-12-01

0 502

「分块系列」数列分块入门7 解题报告

数列分块入门7 题意概括区间乘法，区间加法，单点询问。写在前面写过线段树模板2的童鞋应该很清楚了吧QAQ 由于*与Markdown冲突，所以用×代替o(*￣︶￣*)o 正题我们把一个数表示为 a[i] × tg2[b[i]] + tg1[b[i]]。tg2表示乘法标记，tg1表...

2018-12-01

0 526

「分块系列」数列分块入门4 解题报告

数列分块入门4 题意概括区间加法，区间求和。写在前面这题。。。也与分块1如出一辙。。。正题当有修改时，对于完整的块，直接维护一个数组v记录整个块加过的数(每块共同的加数)与s记录每个块的和(不算共同加数)，不完整的就直接暴力在原数组a上直接加，并且别忘了给s也加上。询问时，对于...

2018-12-01

0 507

「分块系列」数列分块入门5 解题报告

数列分块入门5 题意概括区间开方，区间求和。写在前面这题需要更好地利用暴力QAQ 不暴力这题简直没法做~ 还有注意下，由于不是同一时段的代码，所属分块之后都写成b而不是p了QAQ 希望谅解。正题因为每个数都不超过2 ^ 31 - 1,所以一个数开方5次，肯定会为1。我们可...

2018-12-01

0 400

「分块系列」数列分块入门6 解题报告

数列分块入门6 题意概括单点插入，单点询问。写在前面分块的小技巧可多啦 O(∩_∩)O哈哈~ 正题用一个vector来记录每个块的元素。vector提供了强大的insert函数，插入某个元素只要写一点点就可以啦O(∩_∩)O，就是一个一个枚举块，直到找到插入位置属于哪个块，然后i...

2018-12-01

0 710

「分块系列」数列分块入门3 解题报告

数列分块入门3 题意概括区间加法，区间求前驱。写在前面这题的方法与分块2方法极其类似，建议自行解决。正题和上一题类似，但是二分不是用来计数的，而是用来求小于c的最大值的。然后对于不完整快，将小于c的值求最大值，再与所有块中二分结果求最大值即可。(其他思路上一篇题解已经讲了，这里...

2018-12-01

0 652

「分块系列」数列分块入门2 解题报告

数列分块入门2 题意概括区间加法，区间询问小于一个数的个数。正题对于每个块，除原数组之外用一个vector来有序地存储所有数。当区间加时，对于每个完整块维护共同加数，对于不完整的块直接暴力加上再重新排序。当询问时，对于每个完整块在vector中二分，对于不完整的，直接暴力计数。代码...

2018-12-01

0 471