逆序对,树状数组,归并排序-白红宇

逆序对,树状数组,归并排序

阅读量：5793 次

发布时间：2019-06-18

本文共 7226 字，大约阅读时间需要 24 分钟。

求逆序对有三种方法,

线段树求逆序对,

树状数组求逆序对,

分治求逆序对,

先上手树状数组版的,

有没有重复的数都好使,

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 using namespace std; 7 typedef long long ll; 8 typedef unsigned long long ull; 9 10 #define MAXN 50000111 ll c[MAXN];12 //传说中的树状数组 13 ll n;14 struct shu{15     ll val;16     ll pos;17 }num[MAXN];18 bool cmp(shu a,shu b) {19     //这种是有重复数的 20     if (a.val!=b.val) return a.val>b.val;21     else return a.pos>b.pos; 22     /* retuen a.val>b.val;//这种没有重复 */23 }24 ll lowbit(ll x){25     return x&(-x);26 }27 ll qu_sum(ll x){28     ll s=0;29     while (x>0) {30         s+=c[x];31         x-=lowbit(x);32     }33     return s;34 }35 void updata(ll x){36     while (x<=n) {37         c[x]+=1;38         x+=lowbit(x);39     }40 }41 42 ll ans;43 int main () {44     scanf("%lld",&n);45     memset(c,0,sizeof(c));46     for (int i=1;i<=n;i++) {47         scanf("%lld",&num[i].val);48         num[i].pos=i;49     }50     sort(num+1,num+n+1,cmp);51     ans=0;52     for (int i=1;i<=n;i++) {53         updata(num[i].pos);54         ans+=qu_sum(num[i].pos-1);55     }56     printf("%lld\n",ans);57     return 0;58 }

有的时候,

n 太大,

可以用离散化来求,

下面是离散化例子,

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 using namespace std; 7 typedef long long ll; 8 typedef unsigned long long ull; 9 10 #define MAXN 10000511 ll c[MAXN],s[MAXN],a[MAXN],b[MAXN];12 ll n;13 int lowbit(int x) {
   return x&(-x);}14 void updata(ll i,int x) {15     while (i<=n) {16         c[i]+=x;17         i+=lowbit(i); 18     }19 }20 ll qu_sum(ll x) {21     ll sum=0;22     while(x>0) {23         sum+=c[x];24         x-=lowbit(x);25     }26     return sum;27 }28 int main () {29     //还是求逆序对 30     scanf("%lld",&n);31     ll ans=0;32     for (int i=1;i<=n;i++) {33         scanf("%lld",&a[i]);34         a[i]+=1000000000;35         b[i]=a[i];36     }37     sort(b+1,b+n+1);38     int len=unique(b+1,b+n+1)-b-1; 39     //STL库去重40     for (int i=1;i<=n;i++) {41         a[i]=lower_bound(b+1,b+len+1,a[i])-b;42         updata(a[i],1);43         ans+=(ll)i-qu_sum(a[i]);44     }45     printf("%lld\n",ans);46     return 0;47 }

树状数组还有好多扩展应用,

比如下面这个,

就是区间加,区间查询和,

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 using namespace std; 7 typedef long long ll; 8 typedef unsigned long long ull; 9 #define MAXN 10001010 int a[MAXN],n,m;11 ll c[2][MAXN],sum[MAXN];12 ll lowbit(int x) {
   return x&(-x);}13 ll asksum(int k,int x) {14     ll ans=0;15     for (;x;x-=lowbit(x)) {16         ans+=c[k][x];17     }18     return ans;19 }20 void add(int k,int x,int y) {21     for (;x<=n;x+=lowbit(x)){22         c[k][x]+=y;23     }24 }25 int main () {26     scanf("%d%d",&n,&m);27     for (int i=1;i<=n;i++) {28         scanf("%d",&a[i]);29         sum[i]=sum[i-1]+a[i];30     }31     for (int i=1,l,r,d;i<=m;i++){32         char op[2];33         cin>>op;34         scanf("%d%d",&l,&r);35         if (op[0]=='C') {36             scanf("%d",&d);37             //区间加 38             add(0,l,d);39             add(0,r+1,-d);40             add(1,l,l*d);41             add(1,r+1,-(r+1)*d);42         }43         else {44             //区间求和45             ll ans=0;46             ans=sum[r]+(r+1)*asksum(0,r)-asksum(1,r);47             ans-=sum[l-1]+l*asksum(0,l-1)-asksum(1,l-1);48             printf("%lld\n",ans);49         }50     } 51 52     return 0;53 }

这回就很全了,

最后还有归并排序求逆序对,

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 using namespace std; 7 typedef long long ll; 8 typedef unsigned long long ull; 9 #define MAXN 10000110 ll ans,n;11 int s[MAXN],v[MAXN];12 //s[i]存数据,v[i]更改添加 13 14 void fenzhi(int x,int y) {15     if(x==y) {16         return;17     }18     int mid=(x+y)/2;19     fenzhi(x,mid);20     fenzhi(mid+1,y);21     int p=x,j=x,k=mid+1;22     while(j<=mid&&k<=y) {23         if(s[j]>s[k]) {24             ans+=mid-j+1;25             v[p++]=s[k++];26         } else v[p++]=s[j++];27     }28     while(j<=mid) {29         v[p++]=s[j++];30     }31     while(k<=y) {32         v[p++]=s[k++];33     }34     for(int i=x; i<=y; i++) {35         s[i]=v[i];36     }37 }38 int main() {39     cin>>n;40     for(int i=1; i<=n; i++) {41         cin>>s[i];42     }43     fenzhi(1,n);44     printf("%lld\n",ans);45     return 0;46 }

终于清了,

逆序对还要常看看

再来几个吧：

单点修改,区间查询

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int n,m;int c[500005];int lowbit(int x) {    return (-x)&x;}void add(int pos,int x) {    while(pos<=n) {        c[pos]+=x;        pos+=lowbit(pos);    }}void input() {    int x;    for(int i=1; i<=n; i++) {        scanf("%d",&x);        add(i,x);    }}int query(int pos) {    int res=0;    while(pos>0) {        res+=c[pos];        pos-=lowbit(pos);    }    return res;}int main() {    scanf("%d%d",&n,&m);    input();    int f,x,y;    for(int i=1; i<=m; i++) {        scanf("%d%d%d",&f,&x,&y);        if(f==1) add(x,y);        else if(f==2) cout<
         
          <

区间修改,单点查询：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int c[500005];int n,m;int lowbit(int x) {    return x&(-x);}void add(int pos,int x) {    while(pos<=n) {        c[pos]+=x;        pos+=lowbit(pos);    }}int query(int pos) {    int res=0;    while(pos>0) {        res+=c[pos];        pos-=lowbit(pos);    }    return res;}int main() {    scanf("%d%d",&n,&m);    int x=0,y;    for(int i=1; i<=n; i++) {        scanf("%d",&y);        add(i,y-x);        x=y;    }    int opt,k;    for(int i=1; i<=m; i++) {        scanf("%d",&opt);        if(opt==1) {            scanf("%d%d%d",&x,&y,&k);            add(x,k);            add(y+1,-k);        } else if(opt==2) {            scanf("%d",&x);            printf("%d\n",query(x));        }    }    return 0;}

以及

区间修改,区间查询：

#include
     
      #include
      
       #include
       
        using namespace std;long long c[200005][2];int n,q;int lowbit(int x) {    return x&(-x);}void add(int pos,int x,int f) {    while(pos<=n) {        c[pos][f]+=x;        pos+=lowbit(pos);    }}long long query(int pos,int f) {    long long res=0;    while(pos>0) {        res+=c[pos][f];        pos-=lowbit(pos);    }    return res;}long long ask(int pos) {    long long res=(pos+1)*query(pos,0)-query(pos,1);    return res;}int main() {    scanf("%d",&n);    int a=0,b,opt,x;    for(int i=1; i<=n; i++) {        scanf("%d",&b);        add(i,b-a,0);        add(i,(b-a)*i,1);        a=b;    }    scanf("%d",&q);    for(int i=1; i<=q; i++) {        scanf("%d",&opt);        if(opt==1) {            scanf("%d%d%d",&a,&b,&x);            add(a,x,0);            add(b+1,-x,0);            add(a,x*a,1);            add(b+1,-x*(b+1),1);        } else if(opt==2) {            scanf("%d%d",&a,&b);            printf("%lld\n",ask(b)-ask(a-1));        }    }    return 0;}