欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

逆序对 树状数组 归并排序

程序员文章站 2022-05-10 19:58:02
...

牛客 兔子的逆序对
https://ac.nowcoder.com/acm/problem/20861
需要反转区间 反转区间后不会改变区间外的逆序对个数
只考虑区间内的逆序对个数即可
区间内的总对数 = 顺序对 + 逆序对
反转之后 逆序对个数变为顺序对个数 顺序对个数变为逆序对个数

求出逆序对个数 ans

设区间内逆序对个数为x 反转之后 则总逆序对个数为 ans-x+(r-l+1)(r-l)/2-x
整理: ans+(r-l+1)
(r-l)/2-2x 2x对整个式子的奇偶性无影响
只要考虑 ans+(r-l+1)*(r-l)/2

只要考虑 ans和(r-l+1)*(r-l)/2的奇偶就可以

求逆序对的两种方法:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
//树状数组
/*
C[] 树状数组
A[] 普通数组
c[1] = A[1]
C[2] = A[1] + A[2];
C[3] = A[3];
C[4] = A[1] + A[2] + A[3] + A[4];
C[5] = A[5]
C[6] = A[5] + A[6]
C[7] = A[7]
C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8]

C[i] = A[i-2^k+1] + A[i-2^k+2] + ... +A[i]   k为二进制后面零的个数   2^k == i&(-1);

A[1] -- A[n] 之间的和为
sum = C[n] + C[n-2^k] + C[(n - 2^k)-2^k1]
*/

struct node{
    ll val;
    ll num;
};
node a[100005];
ll C[100005];
ll l,r,m,n,ans;

bool cmp(node a,node b){
    return a.val>b.val;
}
ll lowbit(ll x){
    return x&(-x);
}
ll getsum(ll x){
    ll sum = 0;
    for(;x>0;x-=lowbit(x)){
        sum+=C[x];
    }
    return sum;
}
void update(ll x){
    for(;x<=n;x+=lowbit(x)){
        C[x]+=1;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i = 1; i <=n ; i++){
        cin>>a[i].val;
        a[i].num = i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i = 1; i<=n ; i++){
        ans+=getsum(a[i].num);
        update(a[i].num);
    }
   // cout<<ans<<endl;
    cin>>m;
    /*
      已知区间内总对数:(r-l+1)*(r-l)/2  设区间内逆序对个数为x  则顺序对个数为  (r-l+1)*(r-l)/2-x 则反转后逆序变顺序 顺序便逆序 则逆序对个数为 ans-x+(r-l+1)*(r-l)/2-x
      化简: ans-(r-l+1)*(r-l)/2-2x  2x对奇偶性无影响

    */
    ans%=2;
    while(m--){
        cin>>l>>r;
        ll sum = (r-l+1)*(r-l)/2; //区间内总对个数
        if(sum%2) ans^=1;
        if(ans)puts("dislike");
        else puts("like");
    }


    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
ll a[100005];
ll help[100005];
ll ans;

void mergeSort(ll l,ll mid,ll r){
    ll p=l,q=mid+1,o=1;
    while(p<=mid&&q<=r){
        if(a[p]<=a[q]){
            help[o++] = a[p];
            p++;
        }else{
            ans+=mid-p+1;
            help[o++] = a[q];
            q++;

        }
    }
    while(p<=mid){
        help[o++] = a[p++];
    }
    while(q<=r){
        help[o++] = a[q++];
    }
    for(int i = l; i <= r;i++){
        a[i] = help[i-l+1];
    }

}


void merge_sort(ll l,ll r){
    if(l>=r)return ;
    ll mid = (l+r) / 2;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    mergeSort(l,mid,r);
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    merge_sort(1,n);
    ll m,l,r;
    cin>>m;
    ans%=2;
    while(m--){
        cin>>l>>r;
        ll sum = (r-l+1)*(r-l)/2; //区间内总对个数
        if(sum%2) ans^=1;
        if(ans)puts("dislike");
        else puts("like");
    }
    return 0;
}

相关标签: 逆序对