映射乱搞然后傻了QAQ WA

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100000+5;
const int M=99999997;
int a[maxn],b[maxn],ra[maxn],rb[maxn],r[maxn],t[maxn],n,cnt;
bool cmpa(const int i,const int j){
    return a[i]<a[j];
}
bool cmpb(const int i,const int j){
    return b[i]<b[j];
}
void build(){
    for(int i=1;i<=n;i++){
        ra[i]=i;
        rb[i]=i;
    }
    sort(ra,ra+n,cmpa);
    sort(rb,rb+n,cmpb);
    for(int i=0;i<n;i++) t[ra[i]-1]=i;
    for(int i=0;i<n;i++) r[i]=t[rb[i]-1];
    memset(t,0,sizeof(t));
}
void merge_sort(int x,int y){
    if(y-x<=1) return;
    int m=x+(y-x)/2;
    int p=x,q=m,i=x;
    merge_sort(x,m);
    merge_sort(m,y);
    while(p<m||q<y){
        if(q>=y||(p<m&&r[p]<=r[q])) t[i++]=r[p++];
        else{
            t[i++]=r[q++];
            cnt=(cnt+m-p)%M;
        }
    }
    for(i=x;i<y;i++) r[i]=t[i];
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    build();
    merge_sort(0,n-1);
    cout<<cnt<<endl;
    return 0;
}

0 条评论

目前还没有评论...

信息

ID
1842
难度
7
分类
(无)
标签
递交数
5085
已通过
1102
通过率
22%
被复制
10
上传者