标签归档:逆序对

洛谷P1908 逆序对

洛谷 P1908

以前用树状数组求逆序对,现在用归并排序写一下,顺便复习一下归并排序.

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#define maxn 0x3f3f3f3f
#define ll long long 
using namespace std;

int a[500005];
int b[500005];
ll cnt;
void merge(int l,int mid,int r){
  int i=l,j=mid+1;
  for(int k=l;k<=r;++k){
    if(j>r||i<=mid&&a[i]<=a[j]) b[k]=a[i++];
    else b[k]=a[j++],cnt+=mid-i+1;
  }
   for(int k=l;k<=r;++k) a[k]=b[k];
}

void mergeSort(int l, int r){
  if(l<r){
       int mid=(l+r)>>1;
       mergeSort(l,mid);
       mergeSort(mid+1,r);
       merge(l,mid,r);
  }  
}

int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    scanf("%d",&a[i]);
  }
  mergeSort(1,n);
  cout<<cnt<<endl;
  return 0;
}

CH4201 楼兰图腾(树状数组(顺)逆序对)

题目链接:CH4201

对某个点,求前面和后面分别有多少个点的纵坐标是比它大的,两数相乘就是以该点为中间点,能构成的"v"的数量.

"^"同理.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

#define maxn 200005

typedef long long ll;
typedef unsigned long long ull;

int c[maxn];
int a[maxn];
int Right1[maxn];
int Left1[maxn];
int Right2[maxn];
int Left2[maxn];
int n;

int ask(int x){
  int ans=0;
  for(;x;x-=x&-x) ans+=c[x];
  return ans;
}

void add(int x,int y){
  for(;x<=n;x+=x&-x) c[x]+=y;
}

int main() {
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
  }
  for(int i=n;i>0;--i){
      Right1[i]=n-i-ask(a[i]);
      Right2[i]=ask(a[i]-1);
      add(a[i],1);
  }
  memset(c,0,sizeof(c));
  for(int i=1;i<=n;++i){
    Left1[i]=i-1-ask(a[i]);
    Left2[i]=ask(a[i]-1);
    add(a[i],1);
  }
  ll ans1=0,ans2=0;

  for(int i=1;i<=n;++i){
    ans1+=(ll)Left1[i]*Right1[i];
    ans2+=(ll)Left2[i]*Right2[i];
  } 
  cout<<ans1<<" "<<ans2<<endl;
  return 0;
}