洛谷p1966火柴排队题解

ps：鉴于你们的蒟蒻yxj实在太蒻辽，所以，看不懂也是正常的........

树状数组

xxy学姐给我们讲的树状数组，她讲的真的是太好啦！qwq！吹爆xxy

然后，为了巩固自己，硬着头皮写题解

题目链接

读完题之后来分析是要求逆序对

可以先离散化

因为我们要顺序存， f1数组的第i小和f2数组的第i小在同一个位置一定就是最优的

然后再求在离散化的那个数组里的逆序对的个数

你们将就着看代码吧，水平不够啊qwq..

#include <iostream>

#include <cstdio>

#include <algorithm>

#define mod 99999997

using namespace std;

const int N = ;

struct node {

    long long h, id;

}f1[N], f2[N];

int n;

int id[N], c[N];

int cmp (node x, node y) {

    return x.h < y.h;

}

int lowbit (int k) {

    return k & (-k);

}

void change (int k) {

    while (k <= n) {

        c[k]++;

        c[k] %= mod;

        k += lowbit (k);

    }

}

int query (int k) {

    long long sum = ;

    while (k) {

        sum += c[k];

        sum %= mod;

        k -= lowbit (k);

    }

    return sum;

}

int main () {

    scanf ("%d", &n);

    for (int i = ; i <= n; i++)

        scanf ("%lld", &f1[i].h),f1[i].id = i;

    for (int i = ; i <= n; i++)

        scanf ("%lld", &f2[i].h), f2[i].id = i;

    sort (f1 + , f1 +  + n, cmp);

    sort (f2 + , f2 +  + n, cmp);

    for (int i = ; i <= n; i++)

        id[f1[i].id] = f2[i].id;

    long long ans = ;

    for (int i = ; i <= n; i++) {

        change (id[i]);

        ans += i - query(id[i]);

        ans %= mod;

    }

    printf ("%lld", ans);;

    return ;

}

巴特西

洛谷p1966火柴排队题解

最新文章

热门文章