Loading...

洛谷P1966 火柴排队

check评论:0 条 remove_red_eye浏览量:409 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-10

这道题还是挺裸的

拍完序之后直接求逆序对救星qwq

#include <bits/stdc++.h>
using namespace std;
#define pushup(o) sum[o]=sum[o<<1]+sum[o<<1|1]
#define int long long
int sum[400040];
int rka[100010],rkb[100010];
struct node
{
    int num,id;
    bool operator<(const node&a)const
    {
        return num>a.num;
    }
}a[100010],b[100010];
void modify(int o,int lf,int rg,int x)
{
    if(lf==rg)
    {
        sum[o]++;
        return ;
    }
    int mid=(lf+rg)>>1;
    if(x<=mid)
    {
        modify(o<<1,lf,mid,x);
    }
    if(mid<x)
    {
        modify(o<<1|1,mid+1,rg,x);
    }
    pushup(o);
}
int query(int o,int lf,int rg,int l,int r)
{
    if(l<=lf&&rg<=r)
    {
        return sum[o];
    }
    int ans=0;
    int mid=(lf+rg)>>1;
    if(l<=mid)
    {
        ans+=query(o<<1,lf,mid,l,r);
    }
    if(mid<r)
    {
        ans+=query(o<<1|1,mid+1,rg,l,r);
    }
    return ans;
}
main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].num);
        a[i].id=i;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&b[i].num);
        b[i].id=i;
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        rka[a[i].id]=b[i].id;
    }
    for(int i=1;i<=n;i++)
    {
        if(n==rka[i])
        {
            modify(1,1,n,n-rka[i]+1);
            continue;
        }
        ans+=query(1,1,n,1,n-rka[i]);
        ans%=99999997;
        modify(1,1,n,n-rka[i]+1);
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名