codebook.tex

\documentclass[11pt,twocolumn,a4paper]{article}
\usepackage[top=1.4cm,bottom=1cm,left=1cm,right=1cm]{geometry}
												%設定留白
\usepackage{fontspec}							%設定字體
\usepackage{color}
\usepackage{xeCJK}								%xeCJK
\usepackage{listings}							%顯示code用的
\usepackage[Sonny]{fncychap}					%排版，頁面模板
\usepackage{fancyhdr}							%設定頁首頁尾
\usepackage[compact]{titlesec}  				%tielespacing
\usepackage{enumerate}							%ordered item
\usepackage[bookmarks,hidelinks]{hyperref}		%make bookmarks

%\topmargin=0pt
\headsep=5pt
%\textheight=750pt
\footskip=20pt
\columnsep=5pt									%兩欄間隔
%\voffset=-40pt
%\textwidth=520pt
%\marginparsep=0pt
%\marginparwidth=0pt
%\marginparpush=0pt
%\oddsidemargin=0pt
%\evensidemargin=0pt
%\hoffset=-30pt

\title{Codebook v2.1}
\author{kevinptt}
\date{April 26, 2017}
\setmainfont{Perpetua}							%主要字型
\setmonofont{Consolas}							%等寬字型
\setCJKmainfont{文泉驛微米黑}					%中文字型
\XeTeXlinebreaklocale "zh"						%中文自動換行
\titleformat{\section}{\normalfont\LARGE\bfseries}{\thesection}{1em}{}
\titlespacing{\section}{0pt}{0pt}{0pt}
\titlespacing{\subsection}{0pt}{0pt}{0pt}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\lstset{										% Code顯示
language=C++,									% the language of the code
basicstyle=\footnotesize\ttfamily, 				% the size of the fonts that are used for the code
numbers=none,									% where to put the line-numbers
numberstyle=\ttfamily,							% the size of the fonts that are used for the line-numbers
stepnumber=1,									% the step between two line-numbers. If it's 1, each line will be numbered
numbersep=8pt,									% how far the line-numbers are from the code
backgroundcolor=\color{white},					% choose the background color. You must add \usepackage{color}
showspaces=false,								% show spaces adding particular underscores
showstringspaces=false,							% underline spaces within strings
showtabs=false,									% show tabs within strings adding particular underscores
frame=no,										% adds a frame around the code
tabsize=2,										% sets default tabsize to 2 spaces
captionpos=b,									% sets the caption-position to bottom
breaklines=true,								% sets automatic line breaking
breakatwhitespace=false,						% sets if automatic breaks should only happen at whitespace
escapeinside={\%*}{*)},							% if you want to add a comment within your code
morekeywords={*}								% if you want to add more keywords to the set
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\setlength{\headheight}{30pt}
\pagestyle{fancy}
\fancyhead[L]{NCTU\_Railgun - National Chiao Tung University}
\fancyhead[R]{\thepage}
\fancyfoot{}
%\fancyhead{}
%\fancyhead[R]{\thepage}
%\renewcommand{\headrulewidth}{0.4pt}
%\renewcommand{\footrulewidth}{0pt}
\renewcommand{\contentsname}{Index}
\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{Enviroment Settings}
\subsection{.vimrc}
\begin{lstlisting}[label=.vimrc,language=bash]
syntax on
set enc=utf-8 fencs=utf-8,big5
set bs=2
set smd nu bg=dark hls ls=2 wmnu so=5 ru cul
set ts=4 sw=4 ai sta si
set list lcs=tab:>\  "# a space after '\'
map<F9> :!g++ "%" -o "%:r.out" -Wall -Wshadow -O2 -Im -std=c++11 && echo "===== done =====" && "./%:r.out"
\end{lstlisting}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{Computational Geometry}

\subsection{Geometry on Plane}
\lstinputlisting{code/Geometry_on_Plane.cpp}

\subsection{Minimum Covering Circle}
\lstinputlisting{code/MinimumCoveringCircle.cpp}

\subsection{KDTree}
\lstinputlisting{code/KDTree.cpp}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{Data Structure}

\subsection{PB DS}
\lstinputlisting{code/pb_ds.cpp}

\subsection{BigInteger}
\lstinputlisting{code/BigInteger.cpp}

\subsection{Fenwick Tree Range Modify [1, size]}
\lstinputlisting{code/BIT_range_modify.cpp}

\subsection{Fenwick Tree 2D - [1, size][1, size]}
\lstinputlisting{code/BIT_2D.cpp}

\subsection{Skew Heap}
\lstinputlisting{code/Skew_Heap.cpp}

\subsection{Splay Tree}
\lstinputlisting{code/Splay.cpp}

\subsection{Treap}
\lstinputlisting{code/Treap.cpp}

\subsection{劃分樹}
\begin{lstlisting}[label=劃分樹]
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100005
int a[N], as[N];//原數組，排序後數組 
int n, m;
int sum[20][N];//紀錄第i層的1~j劃分到左子樹的元素個數(包括j)
int tree[20][N];//紀錄第i層元素序列
void build(int c, int l, int r) {
	int i, mid=(l+r)>>1, lm=mid-l+1, lp=l, rp=mid+1;
	for (i=l; i<=mid; i++)
		if (as[i] < as[mid]) lm--;
			//先假設左邊的(mid-l+1)個數都等于as[mid],然后把實際上小于as[mid]的減去
	for (i = l; i <= r; i++){
		if (i == l) sum[c][i] = 0;
			//sum[i]表示[l, i]內有多少個數分到左邊，用DP來維護 
		else sum[c][i] = sum[c][i-1];
		if (tree[c][i] == as[mid]){
			if (lm){
				lm--;
				sum[c][i]++;
				tree[c+1][lp++] = tree[c][i];
			}else
				tree[c+1][rp++] = tree[c][i];
		} else if (tree[c][i] < as[mid]){
			sum[c][i]++;
			tree[c+1][lp++] = tree[c][i];
		} else
			tree[c+1][rp++] = tree[c][i];
	}
	if (l == r)return;
	build(c+1, l, mid);
	build(c+1, mid+1, r);
}
int query(int c, int l, int r, int ql, int qr, int k){
	int s;//[l, ql)內將被劃分到左子樹的元素數目
	int ss;//[ql, qr]內將被劃分到左子數的元素數目
	int mid=(l+r)>>1;
	if (l == r)
		return tree[c][l];
	if (l == ql){//這裡要特殊處理！
		s = 0;
		ss = sum[c][qr];
	}else{
		s = sum[c][ql 1];
		ss = sum[c][qr]- ;
	} //假設要在區間[l,r]中查找第k大元素，t為當前節點，lch，rch為左右孩子，left，mid為節點t左邊界界和中間點。
	if (k <= ss)//sum[r]-sum[l-1]>=k，查找lch[t],區間對應為[ left+sum[l-1], left+sum[r]-1 ]
		return query(c+1, l, mid, l+s, l+s+ss-1, k);
	else
		//sum[r]-sum[l-1]<k,查找rch[t]，區間對應為
		[mid+1+l-left-sum[l-1], mid+1+r-left-sum[r]]
		return query(c+1, mid+1, r, mid-l+1+ql-s, mid-l+1+qr-s-ss, k-ss);
}
int main(){
	int i, j, k;
	while(~scanf("%d%d", &n, &m)){
		for(i=1; i<=n; i++) {
			scanf("%d", &a[i]);
			tree[0][i] = as[i] = a[i];
		}
		sort(as+1, as+1+n);
		build(0, 1, n);
		while(m--){
			scanf("%d%d%d", &i, &j, &k);
				// i,j分別為區間起始點，k為該區間第k大的數。
			printf("%d\n", query(0, 1, n, i, j, k));
		}
	}
	return 0;
}
\end{lstlisting}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{Graph}
\subsection{Bron-Kerbosch}
\lstinputlisting{code/Bron-Kerbosch.cpp}

\subsection{Dinic}
\lstinputlisting{code/Dinic.cpp}

\subsection{General Graph Matching (bcw)}
\lstinputlisting{code/GeneralGraphMatching.cpp}

\subsection{General Graph Matching with minimum weight (bcw)}
\lstinputlisting{code/MinimumGeneralGraphMatching.cpp}

\subsection{Heavy-Light Decomposition}
\lstinputlisting{code/HeavyLightDecomposition.cpp}

\subsection{Kuhn Munkres (bcw)}
\lstinputlisting{code/KuhnMunkres.cpp}

\subsection{Manhattan MST (bcw)}
\lstinputlisting{code/ManhattanMST.cpp}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{Math}
\subsection{China remainder theorem}
$ ans \equiv  a_i\; (mod\; m_i) $
\lstinputlisting{code/CRT.cpp}

\subsection{Euler's phi function O(n)}
\begin{enumerate}[1.]
\item $gcd(x,y)=d \Rightarrow \phi(xy) = \frac{\phi(x) \phi(y)}{\phi(d)}$
\item $p\; is\; prime \Rightarrow \phi(p^k) = p^{k-1} \phi(p)$
\item $p\; is\; prime \Rightarrow \phi(p^k) = \phi(p^{k-1}) \times p$
\item $n = p_{1}^{k_1} p_{2}^{k_2} \cdots p_{m}^{k_m}\\
\Rightarrow \phi(n) = p_{1}^{k_1-1}\phi(p_1)\; p_{2}^{k_2-1}\phi(p_2) \cdots p_{m}^{k_m-1}\phi(p_m)$
\end{enumerate}
\lstinputlisting{code/EularPhi.cpp}

\subsection{Extended Euclid's Algorithm}
$ ax+by=gcd(a,b) $
\lstinputlisting{code/ExtendedEuclid.cpp}

\subsection{FFT}
\lstinputlisting{code/FFT-truckski.cpp}

\subsection{Gaussian Elimination}
\lstinputlisting{code/GaussianElimination.cpp}

\subsection{Miller Rabin}
\lstinputlisting{code/Miller-Rabin.cpp}

\subsection{Möbius function}
\lstinputlisting{code/Mobius.cpp}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{String}
\subsection{AhoCorasick}
\lstinputlisting{code/AC-Automaton.cpp}

\subsection{KMP}
\lstinputlisting{code/KMP.cpp}

\subsection{Longest Palindromic Substring}
\lstinputlisting{code/LPS.cpp}

\subsection{Suffix Array}
\lstinputlisting{code/SuffixArray.cpp}

\subsection{Suffix Tree}
\lstinputlisting{code/SuffixTree.cpp}

\subsection{Suffix Automaton}
\lstinputlisting{code/SuffixAutomaton.cpp}

\subsection{Z Algorithm}
\lstinputlisting{code/Z-Algorithm.cpp}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{Others}
\subsection{recursive to stack}
replace all variable in data into layer[lay].variable
\begin{lstlisting}[label=recursive to stack]
struct data {
	parameter;
	local variabla;
	direction;		//new
} layer[10000];
int lay=0;	//new
type reval;	//new
void go() {
// at the beginning
start:
// call recursive function	
	direction = 1;
	lay++, parameter = value;
	goto start;
point1:
	variable = reval;
// return
	reval = value;
	lay--;
	goto trans;
// at the end
trans:
	switch (direction) {
		case 1:
			goto point1;
	}
}
\end{lstlisting}

\section*{The End}
\end{document}