计算具有更新的段中的反转

Question

我正在尝试解决如下问题：

问题

Given an array of integers "arr" of size "n", process two types of queries. There are "q" queries you need to answer.

Query type 1
    input: l r
   result: output number of inversions in [l, r]

Query type 2
    input: x y
   result: update the value at arr [x] to y

反转

For every index j < i, if arr [j] > arr [i], the pair (j, i) is one inversion.

输入

n = 5
q = 3
arr = {1, 4, 3, 5, 2}

queries:
    type = 1, l = 1, r = 5
    type = 2, x = 1, y = 4
    type = 1, l = 1, r = 5

输出

4
6

约束

Time: 4 secs

1 <= n, q <= 100000

1 <= arr [i] <= 40

1 <= l, r, x <= n

1 <= y <= 40

我知道如何在不更新的情况下解决这个问题的更简单版本，即使用 O(N*log(N ))。我对这个问题的唯一解决方案是 O(q*N*log(N)) （我认为）除了 O(q*N ²) 简单的算法。然而，这不符合问题的时间限制。我想得到一个更好的算法来解决 O(N*log(N)) （如果可能的话）或者 O(N* log²(N)).

两天前我第一次遇到这个问题，我花了几个小时来尝试解决它。但是，我发现这样做 non-trivial 并希望有一些关于相同的 help/hints。感谢您的时间和耐心。

更新

解决方案

在 by Tanvir Wahid 中，我已经用 C++ 实现了该问题的源代码，并想在这里与可能偶然发现此问题并且对如何解决没有直观想法的任何人分享它它。谢谢！

让我们构建一个线段树，每个节点都包含有关存在多少反转以及元素在其权限段中出现的频率计数的信息。

node {
    integer    inversion_count : 0
    array [40] frequency       : {0...0}
}

构建线段树并处理更新

对于每个叶节点，将反转计数初始化为0，并将输入数组中表示的元素的频率增加到1。parent节点的频率可以通过将左节点和左节点的频率相加来计算对 childrens。 parent 节点的反转计数可以通过将左右 children 节点的反转计数相加加上合并两个权限段时创建的新反转来计算，可以使用每个 child 中元素的频率。这个计算基本上是找出左边大元素的频率child和右边小元素的频率child.

的乘积

parent.inversion_count = left.inversion_count + right.inversion_count
for i in [39, 0]
    for j in [0, i)
        parent.inversion_count += left.frequency [i] * right.frequency [j]

更新的处理方式类似。

关于反转计数的回答范围查询

为了回答 [l, r] 范围内的倒置次数查询，我们使用下面附带的源代码计算倒置。

时间复杂度：O(q*log(n))

备注

附带的源代码确实打破了一些良好的编程习惯。代码的唯一目的是“解决”给定的问题，而不是完成任何其他事情。

源代码

/**
    Lost Arrow (Aryan V S)
    Saturday 2020-10-10
**/

#include "bits/stdc++.h"

using namespace std;

struct node {
    int64_t inv = 0;
    vector <int> freq = vector <int> (40, 0);

    void combine (const node& l, const node& r) {
        inv = l.inv + r.inv;
        for (int i = 39; i >= 0; --i) {
            for (int j = 0; j < i; ++j) {
                // frequency of bigger numbers in the left * frequency of smaller numbers on the right
                inv += 1LL * l.freq [i] * r.freq [j];
            }
            freq [i] = l.freq [i] + r.freq [i];
        }
    }
};

void build (vector <node>& tree, vector <int>& a, int v, int tl, int tr) {
    if (tl == tr) {
        tree [v].inv = 0;
        tree [v].freq [a [tl]] = 1;
    }
    else {
        int tm = (tl + tr) / 2;
        build(tree, a, 2 * v + 1, tl, tm);
        build(tree, a, 2 * v + 2, tm + 1, tr);
        tree [v].combine(tree [2 * v + 1], tree [2 * v + 2]);
    }
}

void update (vector <node>& tree, int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
        tree [v].inv = 0;
        tree [v].freq = vector <int> (40, 0);
        tree [v].freq [val] = 1;
    }
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(tree, 2 * v + 1, tl, tm, pos, val);
        else
            update(tree, 2 * v + 2, tm + 1, tr, pos, val);
        tree [v].combine(tree [2 * v + 1], tree [2 * v + 2]);
    }
}

node inv_cnt (vector <node>& tree, int v, int tl, int tr, int l, int r) {
    if (l > r)
        return node();
    if (tl == l && tr == r)
        return tree [v];
    int tm = (tl + tr) / 2;
    node result;
    result.combine(inv_cnt(tree, 2 * v + 1, tl, tm, l, min(r, tm)), inv_cnt(tree, 2 * v + 2, tm + 1, tr, max(l, tm + 1), r));
    return result;
}

void solve () {
    int n, q;
    cin >> n >> q;
    vector <int> a (n);
    for (int i = 0; i < n; ++i) {
        cin >> a [i];
        --a [i];
    }

    vector <node> tree (4 * n);
    build(tree, a, 0, 0, n - 1);

    while (q--) {
        int type, x, y;
        cin >> type >> x >> y;
        --x; --y;

        if (type == 1) {
            node result = inv_cnt(tree, 0, 0, n - 1, x, y);
            cout << result.inv << '\n';
        }
        else if (type == 2) {
            update(tree, 0, 0, n - 1, x, y);
        }
        else
            assert(false);
    }
}

int main () {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.precision(10);
    std::cout << std::fixed << std::boolalpha;

    int t = 1;
//  std::cin >> t;
    while (t--)
        solve();

    return 0;
}

Answer 1

arr[i] 最多可以是 40。我们可以利用这个优势。我们需要的是一个线段树。每个节点将包含 41 个值（一个 long long int 表示此范围的反转，一个大小为 40 的数组用于每个数字的计数。一个结构就可以）。我们如何合并一个节点的两个children。我们知道左 child 和右 child 的倒置。也知道他们两个中每个数字的频率。 parent节点的反转将是children的反转加上左右child之间的反转数的总和。我们可以很容易地从数字的频率中找到两个 children 之间的反转。查询可以用类似的方式完成。复杂度 O(40*qlog(n))

计算具有更新的段中的反转

Counting inversions in a segment with updates

algorithm

math

data-structures

segment-tree

更新