gyro永不抽风！ - BIT
type: channel
link: https://gyrojeff.top/index.php/tag/BIT/
items: Archived | 310-01-ACOJ-0864-奶牛赛跑
items: Archived | 306-14-CDQ分治-陌上花开
items: Archived | 306-03-逆序对的应用

Archived | 310-01-ACOJ-0864-奶牛赛跑
type: item
date: 2020-03-01T14:48:00+00:00
description: 310-01-ACOJ-0864 : 奶牛赛跑 题目大意： 有$n$头奶牛，在一个圆形的赛跑场地里赛跑。所有奶牛同时从起点出发，奶牛的速度都是匀速的，其中第$i$头牛的速度为$v_i$，跑道的长度为单位$1$。当跑得最快那头奶牛跑完$k$圈之后，比赛就结束了。 有时候，跑得快的奶牛可以比跑得慢的奶牛多绕赛场几圈，从而在一些时刻超过慢的奶牛。这就是最令观众激动的套圈事件了。请问在整个比赛过程中，套圈事件一共会发生多少次呢？ 题解： 对于这道题，很显然可以直接求解（小学问题），然后要考虑的是如何降低计算的时间复杂度（原来是$O(n^2)$。 由于每一个奶牛的追击追击次数可以显然得到：$\lfloor \frac {(v_i - v_j)}{v}k\rfloor$，所以要求的就是$\sum_{1≤j<i≤n}\lfloor\frac {v_i - v_j}{v}k\rfloor$。 那么采用整数与小数分离的思想计算：（对于负数向下取整是更小，所以对于$-0. ~…$向下取整为$-1$） $$ \begin {align*} &\frac {(v_i-v_j)} {v} k = A + \alpha \\ \Rightarrow~&\frac {v_ik}v - \frac {v_jk}v = A_i + \alpha_i - (A_j + \alpha_j) \\ \Rightarrow~&\sum_{1≤j<i≤n}\lfloor\frac {v_i - v_j}{v}k\rfloor = \sum_{1≤j<i≤n}(A_i - A_j)+\sum_{1≤j<i≤n}\lfloor\alpha_i - \alpha_j\rfloor \\ &\sum_{1≤j<i≤n}(A_i - A_j) \\ =~&\sum_{1≤i≤n}[(i - 1)A_i - (n - i)A_i] = \sum_{1≤i≤n}(i - 1 - n + i) A_i = \sum_{1≤i≤n}(2i - 1 - n)A_i \end {align*} $$ 而可以发现$\sum_{1≤j<i≤n} \lfloor \alpha_i - \alpha_j\rfloor$就是求$\alpha$序列的逆序对个数。 而对于求逆序对同样可以进行优化（因为小数求逆序对需要进行离散化，很烦），令$\alpha_i’ = v_i \times k \mod v_n$，这非常好证明。 正解： #include <iostream> #include <algorithm> #define int long long using namespace std; int n, k; const int maxn = 1000005; int v[maxn]; int A[maxn], a[maxn]; struct node { int id, val; } B[maxn]; int T[maxn]; int lb(int i) { return i & (-i); } bool cmp(node a, node b) { if (a.val == b.val) return a.id < b.id; return a.val < b.val; } void add(int i, int d) { while (i <= n + 100) { T[i] += d; i += lb(i); } } int sum(int i) { int ans = 0; while (i > 0) { ans += T[i]; i -= lb(i); } return ans; } signed main() { cin >> n >> k; for (int i = 1; i <= n; i ++) cin >> v[i]; sort(v + 1, v + 1 + n); int ans = 0; for (int i = 1; i <= n; i ++) { A[i] = v[i] * k / v[n]; a[i] = v[i] * k % v[n]; ans += (2 * i - 1 - n) * A[i]; B[i] = (node) {i, a[i]}; } sort(B + 1, B + 1 + n, cmp); // for (int i = 1; i <= n; i ++) cout << B[i].id << " " << B[i].val << endl; for (int i = 1; i <= n; i ++) { int p = sum(B[i].id - 1); ans -= (i - 1 - p); add(B[i].id, 1); } cout << a…

Archived | 306-14-CDQ分治-陌上花开
type: item
date: 2020-02-28T15:39:00+00:00
description: 题目大意 对于给遗传给定的序列： $$ (x,y,z)_1, (x,y,z)_2, (x,y,z)_3, \cdots, (x,y,z)_n $$ 求： $$ \sum_{x_i < x_j,~y_i < y_j,~z_i<z_j,~i ≠j}1 $$ 题解： CDQ分治，顾名思义就是要进行分治，但是它可以解决比普通分治更多的问题。CDQ分治的整体思想，是： 对于一个需要解决问题的区间$[l,r)$，将其一分为二，变为$[l,mid),[mid,r)$。 对于这两个被分开的区间，分别进行递归解决。 完成递归解决之后，计算左边对右边的贡献（有的时候可能要计算右边对左边的计算或者互相都要算） 完成，统计答案。 在这道题当中，需要解决的是三维偏序的问题，而首先想到的是使用二维树状数组进行求逆序对，将这三维当中的两维当作下标，对最后一维求逆序对。但是这种做法显而易见，空间会爆掉，是开不下的。所以我们需要采取某种算法或者数据结构来代替树状数组的这意味空间。 在这里，就是用了CDQ分治。 首先解决第一维的问题：以第一维作为第一关键字，第二维作为第二关键字，第三维作为第三关键字，进行排序。比较函数如下： bool cmp1(Point a, Point b) { if (a.x == b.x && a.y == b.y) return a.z < b.z; if (a.x == b.x) return a.y < b.y; return a.x < b.x; } 在进行排序之后，就保证了整个序列单调不下降。 随后进行CDQ分治：solve(0,n) solve(0,mid)，solve(mid, n) 计算左边对右边的影响（原因：整个序列对于第一维变量单调不下降，所以右边的大数无法对小数产生答案上的贡献） 对$[l,mid),[mid,r)$分别进行以第二维作为第一关键字，第三维作为第二关键字的排序： bool cmp2(Point a, Point b) { if (a.y == b.y) return a.z < b.z; return a.y < b.y; } 注意，这里是直接对原数组进行排序，而且实际上不会产生任何问题，因为被排序的两个子序列的这两个子问题，共同属于同一个问题，所以在进行其父亲问题的解决时还会进行重拍，届时并不会产生元素跨界问题。 进行双指针扫描，双指针扫描的目的就是直接使用树状数组对每个元素进行答案统计。 整个问题解决完毕。 但是其存在一定的问题：由于CDQ分治这里我们讨论过了，应该只需要计算左边对右边的影响，但是忽略了一种情况，就是两个元素完全相同，那么左右应该共享影响，但是这里是非常难做到的，所以对于输入的时候，直接进行去重操作，并且赋予每个元素重复次数的权值，方便计算。 注意：在统计答案的时候，会看到下式： ans[A[i].ans + A[i].cnt - 1] += A[i].cnt 这里还要加上A[i].cnt-1的原因其实也不难想到，就是去重的逆运算。 历届悲惨代码如下： 第一次（WA，0分，没有去重）： #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef pair<ll, pair<ll, ll> > Point; const ll maxn = 200005; Point A[maxn]; ll n, K, ord[maxn], f[maxn], T[maxn], ans[maxn]; bool cmp(ll x, ll y) { return A[x].second < A[y].second; } ll lb(ll i) { return i & (-i); } void add(ll i, ll delta) { while (i <= K) { T[i] += delta; i += lb(i); } } ll sum(ll i) { ll ans = 0; while (i > 0) { ans += T[i]; i -= lb(i); } return ans; } // 左闭右开 void solve(ll left, ll right) { if (right - left == 1) return; ll mid = (right + left) / 2; solve(left, mid); solve(mid, right); for (ll i = left; i < right; i ++) ord[i] = i; sort(ord + left, ord + right, cmp); // 左边对右边的理想 for (ll i = left;…

Archived | 306-03-逆序对的应用
type: item
date: 2020-02-28T15:28:00+00:00
description: P1966 火柴排队 题目描述 涵涵有两盒火柴，每盒装有n根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：$∑(a_i−b_i)^2$ 其中$a_i$表示第一列火柴中第i个火柴的高度，$b_i$表示第二列火柴中第i个火柴的高度。 每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 $99,999,997$取模的结果。 输入样例#1： 复制 4 2 3 1 4 3 2 1 4 输出样例#1： 复制 1 输入样例#2： 复制 4 1 3 4 2 1 7 2 4 输出样例#2： 复制 2 题解 可以证明当两个数列都是经过排序之后的数列可以使得$\sum(a_i-b_i)^2$取到最小， 根据上面的结论，就是说如果对于数列$\{a_n\}, \{b_n\}$： $$ \begin{aligned} a_1,~a_2,~a_3,~\cdots,~a_{n-1},~a_n \\ b_1,~b_2,~b_3,~\cdots,~b_{n-1},~b_n \end{aligned} $$ 对它们的$id$排序之后，原数组排序的过程中相当于消除逆序对，但是本来的$id$是正序的，对于这个过程是对$id$增加逆序对的数量。可以说就因该是当$a$数组对于$b$数组想要移动到一模一样所需要花的时间。但是如何求出这个步骤是一个值得讨论的问题： 首先定于$q[a[i]] = b[i]$，最终的目标是$a[i]=b[i] = t$，即$q[t] = t$。可以发现终极目标就是将$q$数组进行排序所需要的次数是多少，即求$q$的逆序对的个数。 代码： #include <iostream> #include <algorithm> using namespace std; const int maxn = 100005; const int P = 99999997; int n; struct node { int id, val; } a[maxn], b[maxn]; int T[maxn], m[maxn]; int lb(int i) { return i & (-i); } bool cmp(node x, node y) { return x.val < y.val; } void add(int i, int delta) { while (i <= n) { T[i] += delta; i += lb(i); } } int sum(int i) { int rtn = 0; while (i > 0) { rtn += T[i]; i -= lb(i); } return rtn; } int main() { cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i].val; for (int i = 1; i <= n; i ++) { cin >> b[i].val; a[i].id = b[i].id = i; } sort(a + 1, a + 1 + n, cmp); sort(b + 1, b + 1 + n, cmp); for (int i = 1; i <= n; i ++) { m[a[i].id] = b[i].id; } int ans = 0; for (int i = 1; i <= n; i ++) { add(m[i], 1); ans = (ans + i - sum(m[i])) % P; } cout << ans << endl; return 0; } P2344 奶牛抗议 题目描述 约翰家的N 头奶牛正在排队游行抗议。一些奶牛情绪激动，约翰测算下来，排在第i 位的奶牛的理智度为Ai，数字可正可负。 约翰希望奶牛在抗议时保持理性，为此，他打算将这条队伍分割成几个小组，每个抗议小组的理智度之和必须大于或等于零。奶牛的队伍已经固定了前后顺序，所以不能交换它们的位置，所以分在一个小组里的奶牛必须是连续位置的。除此之外，分组多少组，每组分多少奶牛，都没有限制。 约翰想知道有多少种分组的方案，由于答案可能很大，只要输出答案除以1000000009 的余数即可。 ### 题解： 方程： $$ f(i) = \sum_{0≤j<i,~\sum_{t = j + 1}^i a[t] ≥0}f(j), ~f(0)=1 $$ 时间复杂度：$O(n^3)$，使用前缀和优化： $$ f(i) = \sum_{0≤j<i,~s[i]-s[j] ≥0}f(j), ~f(0)=1 $$ 时间复杂…