为什么在洛谷上AC,但是其他OI全RE？

NirvanaCeleste @ 2024-07-11 07:03:15

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500100;
long long tree[MAXN],ranks[MAXN];
long long ans,n;
struct point {
    long long num,val;
} a[MAXN];
bool cmp(point q,point w) {
    if(q.val == w.val) return q.num < w.num;
    return q.val < w.val;
}
void add(int p,long d) {
    for(; p<=n; p += p & (-p)) tree[p] += d;
}
long long sum(int p) {
    long long pll = 0;
    for(; p; p -= p & (-p)) pll += tree[p];
    return pll;
}
int main() {
    scanf("%lld\n",&n);
    for(int i=1; i<=n; i++){
        scanf("%lld\n",&a[i].val);
        a[i].num = i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1; i<=n; i++) ranks[a[i].num] = i;
    for(int i=n; i>=1; i--) {
        ans += sum(ranks[i] - 1);
        add(ranks[i],1);
    }
    printf("%lld\n",ans);
    return 0;
}

by qiuribomu @ 2024-07-11 07:08:10

可能编译语言选的不对

by NirvanaCeleste @ 2024-07-11 07:14:05

@qiuribomu 它选的是C++14(O2) 请问这个会有什么影响吗？

by qiuribomu @ 2024-07-11 07:19:31

没，都一样

by NirvanaCeleste @ 2024-07-11 07:22:02

求逆序对的数目

输入格式 第一行为n,表示序列长度；

接下来的n行，第i+1行表示序列中的第i个数。

输出格式 所有逆序对总数.

样例数据 input

4

3

2

3

2

output

3

数据规模与约定 保证

1≤n,ai≤10^5

时间限制： 1s

空间限制： 256 MB @qiuribomu 这个数据规模反而更小了，但是为什么会RE？

by FiraCode @ 2024-07-11 07:25:44

@NirvanaCeleste 我猜add参数错了。

by FiraCode @ 2024-07-11 07:26:22

我指类型。

by NirvanaCeleste @ 2024-07-11 07:30:23

@FiraCode 确实少打了一个long。 改了之后哈是RE http://172.20.0.170/d/summer/record/668f18d41572626289faed97

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500050;
long long tre[MAXN],ranks[MAXN];
long long ans;
int n;
struct point {
    long long num,val;
} a[MAXN];
bool cmp(point q,point w) {
    if(q.val == w.val) return q.num < w.num;
    return q.val < w.val;
}
void add(int p,long long d) {
    for(; p<=n; p += p & (-p)) tre[p] += d;
    return;
}
long long count(int p) {
    long long t = 0;
    for(; p; p -= p & (-p)) t += tre[p];
    return t;
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%lld",&a[i].val);
        a[i].num = i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1; i<=n; i++) ranks[a[i].num] = i;
    for(int i=n; i>=1; i--) {
        ans += count(ranks[i] - 1);
        add(ranks[i],1);
    }
    printf("%lld",ans);
    return 0;
}

by Fish_Love_Water @ 2024-07-11 07:37:28

@NirvanaCeleste 数组开大开小了？

by NirvanaCeleste @ 2024-07-11 07:47:58

@Fish_Love_Water 那个OI上n和ai都在[1,10^5] ，我开了MAXN = 500500的大小

by Lyw_and_Segment_Tree @ 2024-07-11 07:50:10

@NirvanaCeleste 建议使用离散化，不然假设 a_i \le 10 ^ 9 那你这程序的 rank 数组指定存不下啊。
建议学习离散化相关知识。