Introduction

Welcome to this sample article. Here, we’ll explore various Markdown elements rendered in an Apple News-inspired design.

Chapter 5

Exercise 1

Given the pseudo code below:

1
2
3
4
5
6

find(n,a,b):
	if(n==1) return min(A[a],B[b])
	if(A[a + ceil(n/2)] < B[b + ceil(n/2)]) return find(k,a + floor(n/2),b)
	else return find(k,a,b + floor(n/2))
	
The answer is find(n,0,0).

The time complexity is $T(n) = T(\lceil \frac n 2 \rceil) + 2 \Rightarrow T(n)=2\lceil\log n\rceil = O(\log n)$.

Exercise 2

We can use Binary Indexed Tree (also called Fenwick Tree) to count inversions.

You can refer to this page to learn it: 树状数组 - OI Wiki

1
2
3
4
5
6
7

int lowbit(int x){return x&-x;}
void add(int x,int val){while(x<=n)c[x]+=val,x+=lowbit(x);}
int query(int x){
	int res=0;
	while(x)res+=c[x],x-=lowbit(x);
	return res;
}

After discretization, each time we can add $a_i$ and query for how many $a_j > a_i$ with $j<i$.

1
2
3
4
5
6
7
8
9
10
11
12

int main(){
    ...
	sort(b+1,b+n+1);
	rep(i,1,n)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
    //discretization
	for(int i=1;i<=n;++i){
		int x=a[i];
		add(x,1);
		ans+=query(n)-query(x);
	}
	printf("%lld\n",ans);
}

For this problem, we can still use Fenwick Tree to count significant inversions.

After discretization, each time we can add $a_i$ and query for how many $a_j > 2a_i$ with $j<i$.

1
2
3
4
5
6
7
8
9
10

int main(){
    ...
    //discretization
	for(int i=1;i<=n;++i){
		int x=discretization(a[i]);
		add(x,1);
		ans+=query(2*n)-query(discretization(2*a[i]));
	}
	printf("%lld\n",ans);
}

Time complexity is $O(n\log n)$.