问题描述

我正在尝试解决这样的问题：

问题

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))中的段树或 fenwick 树简单地计算每个位置的反转次数。我对这个问题的唯一解决方案是O(q*N*log(N)) （我认为）除了O(q*N ² )普通算法之外的分段树。然而，这不适合问题的时间限制。我想提示一个更好的算法来解决O(N*log(N))（如果可能的话）或O(N*log ² (N))中的问题。

两天前我第一次遇到这个问题，并且在这里和那里花了几个小时来尝试解决它。但是，我发现这样做并非易事，并希望获得一些有关相同的帮助/提示。感谢您的时间和耐心。

更新

解决方案

在Tanvir Wahid的建议、回答和帮助下，我已经在 C++ 中实现了该问题的源代码，并希望在这里与任何可能偶然发现此问题但对如何解决它没有直观想法的人分享。谢谢！

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

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

构建段树并处理更新

对于每个叶节点，将反转计数初始化为 0，并将输入数组中表示的元素的频率增加到 1。父节点的频率可以通过将左右子节点的频率相加来计算。父节点的反转计数可以通过将添加的左右子节点的反转计数与合并其权限的两个段时创建的新反转相加来计算，该反转计数可以使用每个子节点中元素的频率来计算。该计算基本上找出了左孩子中较大元素的频率与右孩子中较小元素的频率的乘积。

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;
}

标签： algorithmmathdata-structuressegment-tree

algorithm - 使用更新计算段中的反转

问题描述

更新

解决方案

推荐阅读