10分找不到原因
查看原帖
10分找不到原因
1454736
xuanzeiliza楼主2024/11/11 17:40
#include<iostream>
#define M 100005
#include<algorithm>
#include<utility>
#define ll long long
#define mod 99999997

using namespace std;

int n;

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

bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first < b.first;
}

pair<int, int> a[M];//用于离散化
pair<int, int> b[M];//用于排序
int f[M];//离散化和排序完成后求逆序数的数组
int tree[M];//树状数组

void addx(int p, int x)
{
    while (p <= n)
    {
        tree[p] += x;
        p += lowbit(p);
    }
}//树状数组的单点修改

ll getsum(int p)
{
    ll sum = 0;
    while (p) {
        sum += tree[p];
        p -= lowbit(p);
    }
    return sum;
}//树状数组区间查询

//树状数组用于求逆序数

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> b[i].first;
    }

    for (int i = 1; i <= n; i++)
    {
        cin >> b[i].second;
    }

    sort(b + 1, b + 1 + n , cmp);

    for (int i = 1; i <= n; i++)
    {
        a[i].first = b[i].second;
        a[i].second = i;
    }

    sort(a + 1, a + 1 + n , cmp);

    for (int i = 1; i <= n; i++)
    {
        f[a[i].second] = i;
    }
    cout << endl;
    for (int i = 1; i <= n; i++)
    {
        cout << f[i] << "\t";
        if (!(i % 5))cout << endl;
    }
    
    ll ans = 0;
    for (int i = n; i > 0; i--)
    {
        addx(f[i], 1);
        ans += getsum(f[i] - 1);
        ans %= mod;
    }

    cout << ans;

    return 0;
}

10分真找不到原因了有dalao帮忙看看吗(哭)

2024/11/11 17:40
加载中...