快速排序

public static void quickSort(int[] q, int l, int r) {
	if(l >= r) return;
	int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
	while(i < j) {
		do i++; while(q[i] < x);
		do j--; while(q[j] > x);
		if(i < j) {
			swap(q, i, j);
		}
	}
	quickSort(q, l, j);
	quickSort(q, j + 1, r);
}

// 如果是i，用例1，1。会超时的。
// quickSort(q, 0, 1)
// 0 1
// 1 0
// quickSort(q, 0, 1)

注意最后是j，不是i

如果是i，用例1，1。会超时的。

归并排序

int[] mergeSort(int[] q, int l, int r) {
		if(l >= r) return new int[]{q[l]};
		int mid = (l + r) / 2;
		int[] q1 = mergeSort(q, l, mid);
		int[] q2 = mergeSort(q, mid + 1, r);
		int[] tmp = new int[q1.length + q2.length];
		int i = 0, j = 0, idx = 0;
		while(i < q1.length || j < q2.length) {
			int v1 = i < q1.length ? q1[i] : Integer.MAX_VALUE;
			int v2 = j < q2.length ? q2[j] : Integer.MAX_VALUE;
			if(v1 < v2) {
				tmp[idx] = v1;
				i++;
			}else {
				tmp[idx] = v2;
				j++;
			}
			idx++;
		}
		return tmp;
	}

二分

	private static int searchRight(int[] q, int k) {
		int n = q.length;
		int l = 0, r = n - 1;
		while(l < r) {
			int mid = l + r + 1>> 1;
			if(q[mid] <= k) {
				l = mid;
			}else {
				r = mid - 1;
			}
		}
		return l;
	}
	private static int searchLeft(int[] q, int k) {
		int n = q.length;
		int l = 0, r = n - 1;
		while(l < r) {
			int mid = l + r >> 1;
			if(q[mid] >= k) {
				r = mid;
			}else {
				l = mid + 1;
			}
		}
		return l;
	}

浮点二分

		double l = -10000, r = 10000;
		double eps = 1e-7;
		while(r - l > eps) {
			double mid = (l + r) / 2;
			if(mid * mid * mid < n) {
				l = mid;
			}else {
				r = mid;
			}
		}

LowBit

HashMap

• 拉链法

class Shot {
    int key, val;
    Shot next;
    Shot(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class ListMap {
    int N = 10003;
    Shot[] map = new Shot[N];
    Shot get(int key) {
        int x = (key % N + N) % N;
        Shot cur = map[x];
        while(cur != null && cur.key != key) {
            cur = cur.next;
        }
        return cur;
    }
    void put(int key, int val) {
        int x = (key % N + N) % N;
        if(map[x] == null) {
            map[x] = new Shot(key, val);
        }else {
            Shot cur = map[x];
            while(cur.next != null && cur.key != key) {
                cur = cur.next;
            }
            if(cur.next == null) {
                cur.next = new Shot(key, val);
            } else {
                cur.val = val;
            }
        }
    }
}

• 线性探测法

import java.util.*;

class Shot {
    int key, val;
    Shot(int key, int val) {
        this.key = key;
        this.val = val;
    }
}
class Map {
    int N = 300030;
    Shot[] q = new Shot[N];
    int getIdx(int x) {
        int key = x;
        x = (x % N + N) % N;
        while(q[x] != null && q[x].key != key) {
            x = (x + 1) % N;
        }
        return x;
    }
    Shot get(int x) {
        x = getIdx(x);
        return q[x];
    }
    void put(int key, int val) {
        int x = getIdx(key);
        if(q[x] == null) q[x] = new Shot(key, val);
        else q[x].val = val;
    }
}

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Map map = new Map();
        for(int i = 0; i < n; i++) {
            char op = in.next().charAt(0);
            int x = in.nextInt();
            if(op == 'I') {
                map.put(x, x);
            }else {
                if(map.get(x) == null) {
                    System.out.println("No");
                } else {
                    System.out.println("Yes");
                }
            }
        }
    }
}