关于离散化
  • 板块P1908 逆序对
  • 楼主senak
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/29 09:25
  • 上次更新2024/4/29 09:30:01
查看原帖
关于离散化
1201076
senak楼主2024/4/29 09:25

我看好多题解的离散化都是

struct point{
    int num,val;
}a[500010];
bool cmp(point q,point w){
    if(q.val==w.val)
        return q.num<w.num;
    return q.val<w.val;
}
 scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&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;

但是本人的离散化是这样的也可以通过 研究了一下不知道为什么 还请各位大佬帮帮忙

signed main() {
    cin >> n; int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    }
    //前
   /* for (int i = 1; i <= n; i++) {
        add(a[i], 1);
        ans += i - sum(a[i]);
    }*/
    //后
    for (int i = n; i >= 1; i--) {
        add(a[i], 1);
        ans += sum(a[i]-1);
    }
    cout << ans << endl;
}
2024/4/29 09:25
加载中...