离散化+树状数组求逆序对全RE求问（玄关）

题目总版

Hor1zDPX @ 2024-11-27 21:35:57

首先为您的热心与支持表示感谢。

rt 使用离散化+树状数组，全部RE,0pts.抓破脑袋都想不到在哪错了 题目为P1908.

code:https://www.luogu.com.cn/paste/wxnh61rw

关于code：

  • 关于离散化：参考皎月半洒花的题解https://www.luogu.com.cn/article/qdrjv3h3
  • 关于判断重复：看了下大家RE的问题多半是没判重导致下标超出树状数组范围，然而我已经写了判重（第53行），调试显示没有问题。（大概）

关于问题：

  • 关于测试点1：在本地跑完全没问题。然而RE。
  • 一些其他的问题：数组开到5e5之后运行未响应。（好像五分钟以前还能正常跑来着？）数组改1e5之后能跑了，然而提交后依然全RE。（至少测试点1应该ac吧..）

再次感谢您的帮助！

by sdjjdjdjdjd @ 2024-11-27 21:46:34

用奇怪方法调到样例能过了且不会段错误(gcc 11.3.0)，但至于代码的正确性我帮不了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=5e5+5;
ll n,c[MAXN],ans=0;
struct Nub
{
    ll ar;//下标，即在原数组中的位置 
    ll val;//值 
}nub[MAXN];

bool cmp(Nub x,Nub y)
{
    if(x.val!=y.val) return x.val<y.val;
    else return x.ar<y.ar;
}

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

void add(ll x,ll k)
{
    while(x<=n)
    {
        c[x]+=k;
        x=x+lowbit(x);
    }
}
ll query(ll x)
{
    ll res=0;
    while(x>0)
    {
        res+=c[x];
        x=x-lowbit(x);
    }
    return res;
}
void init()
{
    Nub tmp[MAXN];
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        cin>>nub[i].val;
        nub[i].ar=i;
        tmp[i]=nub[i];
    }
    sort(tmp+1,tmp+1+n,cmp);
    ll k=1;
    for(ll i=1;i<=n;i++)
    {
        if(tmp[i].val>tmp[i-1].val && i>1) k++;//判重 
        nub[tmp[i].ar].val=k;//离散化 
    }
    return;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    init();
    for(ll i=n;i>=1;i--)
    {
        add(nub[i].val,1);
        ans+=query(nub[i].val-1);
    }
    cout<<ans;
    return 0;
}

by Hor1zDPX @ 2024-11-27 22:01:57

@sdjjdjdjdjd 感谢热心解答（另外数组开到5e5的情况下本地跑未响应是为什么）

by Hor1zDPX @ 2024-11-27 22:03:10

楼主是个纱布

对着看了半个小时没看出写得ll add（黑线）

by sdjjdjdjdjd @ 2024-11-27 22:06:16

@Hor1zDPX 这个我不太清楚

我也不知道为什么把add的返回值改成void就可以了

|