P1966 火柴排队

这题贪心显然，即将两序列中第k大的数的位置保持一致，证明略；

树状数组求逆序对啦

浅谈树状数组求逆序对及离散化的几种方式及应用

方法：从前向后每次将数插入到bit（树状数组）中，求其前缀和（在它之前插入且比它小的数），那么用i（当前插入的数的总数）- 前缀和就是其（以c[i]为结尾）逆序对对数

这个题需要将一个序列按照另一个序列排序，因为只需要移动一个序列，sort排序就有了第k小的数的下标

$c[a[i].id]=b[i].id$

第i小的数在a中的位置就是b中第i小的数应放的位置，相当于以第一个数列为关键字排序第二个数列

#include<bits/stdc++.h>

#define N 1010100

using namespace std;

const int mod=;

int n,c[N],bit[N],ans;

struct node{

    int x,id;

}a[N],b[N];

bool cmp(node A,node B){

    return A.x<B.x;

}

int lowbit(int k){

    return k&(-k);

}

void add(int x,int w){

    while(x<=n){

        bit[x]+=w;

        bit[x]%=mod;

        x+=lowbit(x);

    }

}

int sum(int x){

    int res=;

    while(x){

        res+=bit[x];

        x-=lowbit(x);

        res%=mod;

    }

    return res%mod;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i;

    for(int i=;i<=n;i++) scanf("%d",&b[i].x),b[i].id=i;

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

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

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

        c[a[i].id]=b[i].id;

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

        add(c[i],);

        ans=(ans+(i-sum(c[i])))%mod;

    }

    printf("%d\n",ans);

    return ;

}

P1774 最接近神的人_NOI导刊2010提高（02）

同样的离散化，只不过是从后向前插入，那么其前缀和就是逆序数。

#include<bits/stdc++.h>

#define N 500005

#define ll long long

using namespace std;

int n,h[N],c[N];

ll ans;

struct node{

    int y;ll x;

    bool operator<(const node A)const {

        return x==A.x ? y<A.y :x<A.x;

    }

}e[N];

void update(int k,int x){

    for(;k<=n;k+=k&-k) c[k]+=x;

}

ll query(int k){

    ll an=;

    for(;k;k-=k&-k) an+=c[k];

    return an;

}

int main()

{

    cin>>n;

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

        scanf("%lld",&e[e[i].y=i].x);

    sort(e+,e++n);

    for(int i=n;i;i--){

        ans+=query(e[i].y-);

        update(e[i].y,);

    }cout<<ans;

//    printf("%lld",ans);

    return ;

}

巴特西

洛谷——P1966 火柴排队&&P1774 最接近神的人_NOI导刊2010提高（02）

P1966 火柴排队

浅谈树状数组求逆序对及离散化的几种方式及应用

P1774 最接近神的人_NOI导刊2010提高（02）

最新文章

热门文章