19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

全部文章 / 题解（共5篇）

E. Optimal Insertion 来自专栏

考虑是把b{b}b序列中的元素插入到a{a}a序列中，b{b}b序列插入的相对位置一定是值小的在前面。对bi<bj,i<j{b_i<b_j,i<j}bi<bj,i<j，当前得到ans{ans}ans对逆序数，bi、bj{b_i、b_j}bi、bj之间值在...

线段树树状数组逆序数离散化

2021-11-10

1 552

Array 来自专栏

原题链接:P4062 [Code+#1]Yazid 的新生舞会解法一分块对于所有的，暴力扫描所有长度不大于的区间，即枚举左端点，然后往右扫描，长度不大于，然后维护众数出现的次数，当众数出现的次数大于区间的一半时，该区间对答案的贡献加一。这里注意不要把的维护进众数里，后面会单独计算每个的为众数...

整数分块树状数组 STL

2021-08-06

1 791

I love counting 来自专栏

思路：如果不考虑去重，一般都会想到可持久化字典树。求的个数满足，很明显用字典树可以轻松的做到。求区间的内的个数的话加个可持久化，前个数组成第个版本的字典树，然后第个版本算出的值减去第个版本算出的值就是答案。字典树求的个数满足的原理：构建字典树时，每个节点存这个节点包含了多少个数。搜索字典树...

树状数组线段树

2021-07-29

2 654

Different Integers

题意：给出个数，求 ,这两个区间不同数的个数思路：其实只要把区间扩大一倍，就是求这个区间了定义数组中第一次出现的数的后缀为，第次出现的数的后缀为该数第次出先时的下标。比如：原数组为，扩大一倍后为，每个数对应的后缀为。如果某个数出现多次，而我们只算最右边的那个，我们会发现最右边的那个数的后缀...

线段树树状数组

2021-07-29

1 593

Harbour.Space Scholarship Contest 2021-2022 来自专栏

E. Permutation Shift 思路：原问题等价于把往左挪位，然后最多交换次得到原排列，求有多少种。假设排列表示原排列，表示原排列往右挪位得到的排列，那么当时，对应位置上数字相同的个数为。一个通常能想到的套路就是枚举，然后把排列往左挪位得到排列，然后判断排列能不能通过最多次交换得到原排...

排序树状数组

2021-07-23

1 682