逆序对 树状数组 归并排序
程序员文章站
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;
}
推荐阅读
-
C#实现对二维数组排序的方法
-
PHP使用array_multisort对多个数组或多维数组进行排序
-
php中array_multisort对多维数组排序的方法
-
php 归并排序 数组交集
-
数据结构算法(数组中的逆序对)
-
海创软件组--20200712--axios上传文件获取进度--js对多个四边形的点对象数组分别按顺时针排序--定义上传视频并可预览
-
编写程序对该数组排序,并输出所有包含“王”字的字符串。
-
给出数组array(1,9,5,8,3,7,2,4,6),写一个方法对其进行排序,使排序后的结果为(1,2,3,4,5,6,7,8,9)
-
【剑指offer刷题】--数组中的逆序对
-
POJ 2352 Stars & UESTC 1584 Washi与Sonochi的约定 排序+树状数组