18duangduang

题解

未归档(23) 计算几何(1)

/ 注册

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

题解 | #数组中的逆序对#

const int maxn=1e5+5; const int mod=1e9+7; class Solution { public: #define lowbit(x) x&(-x) int sum[100005]; vector<int> p; ...

树状数组

2021-09-03

0 517

骚区间

%参考fyj大佬题解：https://blog.nowcoder.net/n/9eb663297d054e8898236cf06bed7f17分析：骚区间定义：区间左端点为区间的第二小值,区间右端点为区间的第二大值.给定序列是一个1-n的排列,所以无重复元素.求所有骚区间个数.容易想到枚举一个端点，...

树状数组次小值问题

2020-07-07

0 591

位数差

大致题意：给定一个序列，求 . 表示和十进制下的位数差.分析：方法一:离散+树状数组我们可以逆序遍历序列，计算当前作为的左参数的贡献，那么我们与相加能产生数位差 .举个例子：能至少产生一位数位差，设比大的最小十进制数位，那么的大小一定要大于等于 .依次枚举至少产生两位数位差.......

树状数组分治

2020-07-03

0 1090

逆序数

树状数组简单应用，逆序数转换为：求前i个数小于x的和。 #include<bits/stdc++.h> #define lowbit(x) x&(-x) using namespace std; typedef long long ll; const int maxn=2e5+...

树状数组

2020-05-29

5 692

牛客小白月赛9 E.换个角度思考

分析:一个新的方法求任意区间小于等于k的个数.-------离散+树状数组.将询问按照大小从小到大排序,并且将也从小到大排序，然后根据询问从小到大插入到树状数组对应编号中,当大于时候更新询问答案.复杂度可以做到O(nlogn).十分优美的方法 #include<bits/stdc++.h&...

树状数组

2020-05-04

1 772

OI周赛13-提高组

B题题目大意:求一个由二元组组成最长序列，二元组的相对位置不变，并且满足对于数列a中任意一个数字都是极大值或者极小值首先离散将所有数字离散化.分两种情况，奇数位较大和偶数为较大.1.奇数位较大的情况，我们需要将所有满足 x>y 的二元组选出来。用表示前 i 个二元组选出的最后一个二元...

树状数组 dp优化

2019-12-11

1 820