Author

[email protected]

https://liuup.top/

Golang Fast IO

https://github.com/EndlessCheng/codeforces-go/

感谢灵神！

快速排序

AcWing 785. 快速排序

package main

import (
	"bufio" // io
	"fmt"   // Fprintln(out)
	"os"    //io
	"strconv" //io
)

var (
	in  *bufio.Scanner
	out *bufio.Writer
)

func ri() int { // fast read int
	in.Scan()
	x, _ := strconv.Atoi(string(in.Bytes()))
	return x
}

func rf() float64 { // fast read float64
	in.Scan()
	f, _ := strconv.ParseFloat(string(in.Bytes()), 64)
	return f
}

func main() {
	// ===== fast io =====
	in = bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords) // 分割
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== fast io =====

	n := ri()

	nums := make([]int, n)
	for i := 0; i < n; i++ {
		nums[i] = ri()
	}
	quicksort(nums, 0, len(nums)-1)

	for _, x := range nums {
		fmt.Fprint(out, x, " ")
	}
}

func quicksort(nums []int, l, r int) {
	if l >= r {
		return
	}
	i, j := l-1, r+1
	x := nums[(l+r)>>1]
	for i < j {
		i++
		for ; nums[i] < x; i++ { // 可以理解让左边都小于x
		}
		j--
		for ; nums[j] > x; j-- {
		}

		if i < j {
			nums[j], nums[i] = nums[i], nums[j]
		}
	}
	quicksort(nums, l, j)
	quicksort(nums, j+1, r)
}

AcWing 786. 第k个数

package main

import (
	"bufio"   // io
	"fmt"     // io
	"os"      // io
	"strconv" // io
)

var (
	in  *bufio.Scanner
	out *bufio.Writer
)

func ri() int { // fast read int
	in.Scan()
	x, _ := strconv.Atoi(string(in.Bytes()))
	return x
}

func rf() float64 { // fast read float64
	in.Scan()
	f, _ := strconv.ParseFloat(string(in.Bytes()), 64)
	return f
}

func main() {
	// ===== fast io =====
	in = bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords) // 分割
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== fast io =====
	n, k := ri(), ri()
	nums := make([]int, n)

	for i := 0; i < n; i++ {
		nums[i] = ri()
	}
	quicksort(nums, 0, n-1)
	fmt.Fprintln(out, nums[k-1])
}

func quicksort(nums []int, l, r int) {
	if l >= r {
		return
	}
	i, j := l-1, r+1
	x := nums[(l+r)>>1]
	for i < j {
		i++
		for ; nums[i] < x; i++ {
		}
		j--
		for ; nums[j] > x; j-- {
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	quicksort(nums, l, j)
	quicksort(nums, j+1, r)
}

归并排序

AcWing 787. 归并排序

package main

import (
	"bufio"   // io
	"fmt"     // io
	"os"      // io
	"strconv" // io
)

var (
	in  *bufio.Scanner
	out *bufio.Writer
)

func ri() int { // fast read int
	in.Scan()
	x, _ := strconv.Atoi(string(in.Bytes()))
	return x
}

func rf() float64 { // fast read float64
	in.Scan()
	f, _ := strconv.ParseFloat(string(in.Bytes()), 64)
	return f
}

func main() {
	// ===== fast io =====
	in = bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords) // 分割
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== fast io =====

	n := ri()
	mergetmp = make([]int, n)
	nums := make([]int, n)

	for i := 0; i < n; i++ {
		nums[i] = ri()
	}
	mergesort(nums, 0, n-1)

	for _, x := range nums {
		fmt.Fprint(out, x, " ")
	}
}

var mergetmp []int

// nums, 0, len(nums)-1
func mergesort(nums []int, l, r int) {
	if l >= r {
		return
	}
	mid := (l + r) >> 1
	mergesort(nums, l, mid)
	mergesort(nums, mid+1, r)

	k := 0
	i, j := l, mid+1
	for ; i <= mid && j <= r; k++ {
		if nums[i] <= nums[j] {
			mergetmp[k] = nums[i]
			i++
		} else {
			mergetmp[k] = nums[j]
			j++
		}
	}
	for ; i <= mid; i, k = i+1, k+1 {
		mergetmp[k] = nums[i]
	}
	for ; j <= r; j, k = j+1, k+1 {
		mergetmp[k] = nums[j]
	}
	for i, j := l, 0; i <= r; i, j = i+1, j+1 { // 全部数组
		nums[i] = mergetmp[j]
	}
}

AcWing 788. 逆序对的数量

package main

import (
	"bufio"   // io
	"fmt"     // io
	"os"      // io
	"strconv" // io
)

var (
	in  *bufio.Scanner
	out *bufio.Writer
)

func ri() int { // fast read int
	in.Scan()
	x, _ := strconv.Atoi(string(in.Bytes()))
	return x
}

func rf() float64 { // fast read float64
	in.Scan()
	f, _ := strconv.ParseFloat(string(in.Bytes()), 64)
	return f
}

func main() {
	// ===== fast io =====
	in = bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords) // 分割
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== fast io =====

	n := ri()
	mergetmp = make([]int, n)
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		nums[i] = ri()
	}

	mergesort(nums, 0, n-1)

	fmt.Fprintln(out, result)
}

var mergetmp []int

var result int = 0

// nums, 0, len(nums)-1
func mergesort(nums []int, l, r int) {
	if l >= r {
		return
	}
	mid := (l + r) >> 1
	mergesort(nums, l, mid)
	mergesort(nums, mid+1, r)

	k := 0
	i, j := l, mid+1
	for ; i <= mid && j <= r; k++ {
		if nums[i] <= nums[j] {
			mergetmp[k] = nums[i]
			i++
		} else {
			mergetmp[k] = nums[j]
			j++
			result += (mid - i + 1) // 求逆序对
		}
	}
	for ; i <= mid; i, k = i+1, k+1 {
		mergetmp[k] = nums[i]
	}
	for ; j <= r; j, k = j+1, k+1 {
		mergetmp[k] = nums[j]
	}
	for i, j := l, 0; i <= r; i, j = i+1, j+1 { // 全部数组
		nums[i] = mergetmp[j]
	}
}

二分

AcWing 789. 数的范围

package main

import (
	"bufio"   // io
	"fmt"     // io
	"os"      // io
	"strconv" // io
)

var (
	in  *bufio.Scanner
	out *bufio.Writer
)

func ri() int { // fast read int
	in.Scan()
	x, _ := strconv.Atoi(string(in.Bytes()))
	return x
}

func rf() float64 { // fast read float64
	in.Scan()
	f, _ := strconv.ParseFloat(string(in.Bytes()), 64)
	return f
}

func main() {
	// ===== fast io =====
	in = bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords) // 分割
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== fast io =====

	n, q := ri(), ri()
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		nums[i] = ri()
	}

	for i := 0; i < q; i++ {
		query := ri()
		left := bsearch1_(nums, query)
		if left >= len(nums) || nums[left] != query {
			fmt.Fprint(out, -1)
		} else {
			fmt.Fprint(out, left)
		}

		fmt.Fprint(out, " ")

		right := bsearch2_(nums, query)
		if right < 0 || nums[right] != query {
			fmt.Fprintln(out, -1)
		} else {
			fmt.Fprintln(out, right)
		}
	}
}

// find 5 left border; 1 2 3 {5 5 5 7 8}
// if left >= len(nums) || nums[left] != query
func bsearch1_(n []int, t int) int {
	l, r := -1, len(n)
	for l+1 < r {
		mid := (l + r) >> 1
		if n[mid] >= t {
			r = mid
		} else {
			l = mid
		}
	}
	return r // 函数外判断是否越右边界
}

// find 5 right border; {1 2 3 5 5 5} 7 8
// right < 0 || nums[right] != query
func bsearch2_(n []int, t int) int {
	l, r := -1, len(n)
	for l+1 < r {
		mid := (l + r) >> 1
		if n[mid] <= t {
			l = mid
		} else {
			r = mid
		}
	}
	return l // 函数外判断是否越左边界
}