Catshao

用户名：Catshao

访问量：28830

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7133
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

[ω] 最大子段乘积
浏览：108

蓝桥杯2020年第十一届省赛真题-整数小拼接
浏览：1472

蓝桥杯2020年第十一届省赛真题-BST插入节点问题
浏览：547

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （Java代码）

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

区间逆序对（弱化版）

　　作者: Catshao　　　　发表时间：2022-02-17 10:35:40 浏览：158　|　评论：0　

原题链接：区间逆序对（弱化版）

~~各位不要被之前的提交记录吓到，之前这道题时人人本着正义之名的随机数据。~~

------------

数据有变化：$$1 \le n, m \le 2 \times 10^5$$ 。

不卡常。

做法显然，用对于两种操作分别处理，对于第一种操作，从左至右用树状数组扫一遍，得到所有操作为 1 的答案。对于第二种操作从右往左扫即可。

下面代码中的`naive`是 $$O(n^2)$$ 的暴力做法，`test`是树状数组的 $$O(n \log n)$$ 的解法。

```cpp
//
// Created by Cat-shao on 2022/2/15.
//

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 500010;

inline int lowbit(int x) {
    return x & -x;
}

class BIT {
public:
    int node[MAX_N], n;

BIT(int _n) {
        memset(node, 0, sizeof(node));
        n = _n;
    }

int sum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += node[index];
            index -= lowbit(index);
        }
        return sum;
    }

void add(int index, int value) {
        while (index <= n) {
            node[index] += value;
            index += lowbit(index);
        }
    }
};

class block {
public:
    static const int MAX_LEN = 320;
    int b[MAX_N], pre[MAX_LEN], pre2[MAX_N], n, len;

block(int _n) {
        n = _n;
        len = sqrt(n);
        for (int i = 1; i <= n; ++i) {
            b[i] = (i - 1) / len + 1;
        }
        memset(pre, 0, sizeof(pre));
        memset(pre2, 0, sizeof(pre2));
    }

void add(int x, int v) {
        for (int i = x; i <= min(n, b[x] * len); ++i) {
            pre2[i] += v;
        }
        for (int i = b[x]; i <= b[n]; ++i) {
            pre[i] += v;
        }
    }

int sum(int l, int r) {
        return pre[b[r] - 1] + pre2[r] - pre[b[l - 1] - 1] - pre2[l - 1];
    }
};

namespace test {
    int n, m, k, a[MAX_N], h[MAX_N], q1[MAX_N], q2[MAX_N];
    long long res[MAX_N], ans;

void main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        memcpy(h + 1, a + 1, n * sizeof(int));
        sort(h + 1, h + n + 1);
        k = unique(h + 1, h + n + 1) - (h + 1);
        for (int i = 1; i <= n; ++i) {
            a[i] = lower_bound(h + 1, h + k + 1, a[i]) - h;
        }
        int op, x;
        for (int i = 1; i <= m; ++i) {
            cin >> op >> x;
            if (op == 1) {
                q1[x] = i;
            } else {
                q2[x] = i;
            }
        }
        BIT tree(n);
        ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans += (i - 1) - tree.sum(a[i]);
            if (q1[i]) {
                res[q1[i]] = ans;
            }
            tree.add(a[i], 1);
        }
        memset(tree.node, 0, sizeof(tree.node));
        ans = 0;
        for (int i = n; i >= 1; --i) {
            ans += tree.sum(a[i] - 1);
            if (q2[i]) {
                res[q2[i]] = ans;
            }
            tree.add(a[i], 1);
        }
        for (int i = 1; i <= m; ++i) {
            cout << res[i] << '\n';
        }
    }
}

namespace naive {
    int n, m, a[MAX_N], q1[MAX_N], q2[MAX_N];
    long long res[MAX_N], ans;

void main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        int op, x;
        for (int i = 1; i <= m; ++i) {
            cin >> op >> x;
            if (op == 1) {
                q1[x] = i;
            } else {
                q2[x] = i;
            }
        }
        ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                if (a[j] > a[i]) {
                    ans ++;
                }
            }
            if (q1[i]) {
                res[q1[i]] = ans;
            }
        }
        ans = 0;
        for (int i = n; i >= 1; --i) {
            for (int j = i + 1; j <= n; ++j) {
                if (a[i] > a[j]) {
                    ans ++;
                }
            }
            if (q2[i]) {
                res[q2[i]] = ans;
            }
        }
        for (int i = 1; i <= m; ++i) {
            cout << res[i] << endl;
        }
    }
}

int main()
{
    test::main();
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （Java代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

1268:P1001

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

【蟠桃记】（C语言代码）

区间逆序对（弱化版）

评论区

精彩推荐

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

C语言训练-最大数问题（C语言代码）

A+B for Input-Output Practice (VII) （C++代码）

这可能是一个假的冒泡法

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

WU-输出正反三角形（C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （Java代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

1268:P1001

数字整除 （C++代码）——(22行代码)真的只需要两个变量就够了

【蟠桃记】 （C语言代码）

区间逆序对（弱化版）

评论区

精彩推荐

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

C语言训练-最大数问题 （C语言代码）

A+B for Input-Output Practice (VII) （C++代码）

这可能是一个假的冒泡法

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

WU-输出正反三角形 （C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

【蟠桃记】（C语言代码）

　　评论区

C语言训练-最大数问题（C语言代码）

WU-输出正反三角形（C++代码）