关于大部分题解

P1908 逆序对

HYdroKomide @ 2021-11-26 19:25:51

大部分树状数组写法的题解貌似都没有判重,导致错误,希望管理撤下。

@StudyingFather


by HYdroKomide @ 2021-11-26 19:26:16

@StudyingFather 望撤下


by StillEmpty @ 2021-11-26 19:44:17

你搞错了啊


by StillEmpty @ 2021-11-26 19:50:18

我来口述一遍:

  1. 离散化,获得每一个数的升序排名
  2. bucket_i表示排名为i的数出现的次数。
  3. 对于循环到第i个数:
    • 每次询问sum\{bucket_{(rk_i, n]}\},其中rk_i表示i的排名
    • bucket_i加1

by StillEmpty @ 2021-11-26 19:51:16

观察bucket的询问和修改特性,发现可以用线段树/树状数组维护


by StillEmpty @ 2021-11-26 19:52:34

@Kevin_FOS


by HYdroKomide @ 2021-11-26 19:54:18

@Kobayashi 但也确实许多题解都有错误


by StillEmpty @ 2021-11-26 19:59:05

@Kevin_FOS 我给你看一眼我的代码(省去了线段树部分,就是给你看一眼逻辑,你说有什么问题)

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

int n, tar;
unsigned long long sum = 0;
int ranking[MAXN+1];
pair<int, int> a[MAXN+1];
int cnt[MAXN*4+1], l[MAXN*4+1], r[MAXN*4+1];

void init(int k, int lp, int rp) {
    ...
}

int query(int k) { // return the cnt of bucket(tar, maxa]
    ...
}

void update(int k) {
    ...
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a+1, a+n+1);
    for(int i = 1, j = 0; i <= n; i++) {
        if(a[i].first != a[i-1].first) {
            j++;
        }
        ranking[a[i].second] = j;
    }
    init(1, 1, n);
    for(int i = 1; i <= n; i++) {
        tar = ranking[i];
        sum += query(1);
        update(1);
    }
    cout << sum << endl;
    return 0;
}

by StillEmpty @ 2021-11-26 20:00:45

@Kobayashi 注:2.3.的i是两个东西


by HYdroKomide @ 2021-11-26 20:04:30

@Kobayashi 我的意思是看见了题解区里不少的题解都没有加上去重,就错了。


by StillEmpty @ 2021-11-26 20:06:18

@Kevin_FOS 你是说离散化?


| 下一页