逆序对（inversion）

2022年11月23日
0 收藏 341 点赞 4,963 浏览 2011 个字

样例输入

`5 41 5 3 4 25142`

`5221`

提示

tj,idi>idj,xi

``#include<cstdio>#include<iostream>#include<cstdlib>#include<cstring>#include<algorithm>#include<cmath>#define maxn 1000005#define ll long longusing namespace std;int n,m,c;ll sum[maxn],tree[maxn],ans[maxn];int p[maxn];struct node{    int id,x,t;}s[maxn],a[maxn];bool cmp(node a,node b){    return a.t>b.t;}bool X(node a,node b){    return a.x>b.x;}bool ID(node a,node b){    return a.id>b.id;}void jia(int k,int val){    for(int i=k;i<=n;i+=i&-i)tree[i]+=val;}ll ask(int k){    ll su=0;    for(int i=k;i;i-=i&-i)su+=tree[i];    return su;}void cdq(int l,int r){    if(l==r)return;    int mid=(l+r)>>1;    cdq(l,mid);cdq(mid+1,r);    sort(s+l,s+mid+1,X);sort(s+mid+1,s+r+1,X);    //cout<<l<<' '<<r<<endl;    int i=l;    for(int j=mid+1;j<=r;j++){        while(s[i].x>s[j].x&&i<=mid){            jia(s[i].id,1);i++;            //cout<<s[i].id<<' ';        }        ans[s[j].t]+=ask(s[j].id);    }    for(int j=l;j<i;j++)jia(s[j].id,-1);    //merge(s+l,s+mid+1,s+mid+1,s+r+1,a,X);    //for(int i=0;i<=l+r-1;i++)s[i+l]=a[i];}void cd(int l,int r){    if(l==r)return;    int mid=(l+r)>>1;    cd(l,mid);cd(mid+1,r);    sort(s+l,s+mid+1,ID);sort(s+mid+1,s+r+1,ID);    int i=l;    for(int j=mid+1;j<=r;j++){        while(s[i].id>s[j].id&&i<=mid){            jia(s[i].x,1);i++;        }        ans[s[j].t]+=ask(s[j].x);    }    for(int j=l;j<i;j++)jia(s[j].x,-1);    //merge(s+l,s+mid+1,s+mid+1,s+r+1,a,ID);    //for(int i=0;i<=l+r-1;i++)s[i+l]=a[i];}int main(){    cin>>n>>m;    for(int i=1;i<=n;i++){        scanf("%d",&s[i].x);p[s[i].x]=i;        s[i].id=i;    }    for(int i=1;i<=m;i++){        scanf("%d",&c);        s[p[c]].t=i;    }    int top=m;    for(int i=1;i<=n;i++)if(!s[i].t)s[i].t=++top;    sort(s+1,s+n+1,cmp);    cdq(1,n);    sort(s+1,s+n+1,cmp);    cd(1,n);    for(int i=n;i>=1;i--)sum[i]=sum[i+1]+ans[i];//    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";cout<<endl;    for(int i=1;i<=m;i++){        printf("%lld\n",sum[i]);    }    return 0;}``

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用

400-888-8888

ceotheme@ceo.com