lca (logN + NlogN предподсчетом)

Ссылка

Система непересекающихся множеств

class dsu {
  int p[]; // parents
  int r[]; // rangs
  int N; // number of elements

  dsu(int N) {
    this.N = N;
    p = new int[N];
    r = new int[N];
    for (int i = 0; i < N; i++) {
      p[i] = i;
      r[i] = 1;
    }
  }

  int get(int x) {
    return (x == p[x] ? x : p[x] = get(p[x]));
  }

  void union(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) return;
    if (r[x] == r[y]) r[x]++;
    if (r[x] < r[y]) 
      p[x] = p[y]; else
      p[y] = p[x];
  }
}

Бинарное возведение в степень

long pow(long a, long n) {
  if (n == 0) return 1;
  if (n % 2 == 0) {
    long ans = pow(a, n / 2);
    return ans * ans;
  } else {
    return a * pow(a, n - 1);
  }
}

Splay-дерево

class Splay {
  Node root;

  private Node rotateRight(Node h) {
   Node x = h.lNode;
   h.lNode = x.rNode;
   x.rNode = h;
   return x;
  }

  private Node rotateLeft(Node h) {
   Node x = h.rNode;
   h.rNode = x.lNode;
   x.lNode = h;
   return x;
  }

  private Node splay(Node h, int key) {
   if (h == null)
    return null;

   if (key < h.key) {
    if (h.lNode == null) {
     return h;
    }
    if (key < h.lNode.key) {
     h.lNode.lNode = splay(h.lNode.lNode, key);
     h = rotateRight(h);
    } else if (key > h.lNode.key) {
     h.lNode.rNode = splay(h.lNode.rNode, key);
     if (h.lNode.rNode != null)
      h.lNode = rotateLeft(h.lNode);
    }
    if (h.lNode == null)
     return h;
    else
     return rotateRight(h);
   }
   if (key > h.key) {
    if (h.rNode == null) {
     return h;
    }
    if (key < h.rNode.key) {
     h.rNode.lNode = splay(h.rNode.lNode, key);
     if (h.rNode.lNode != null)
      h.rNode = rotateRight(h.rNode);
    } else if (key > h.rNode.key) {
     h.rNode.rNode = splay(h.rNode.rNode, key);
     h = rotateLeft(h);
    }

    if (h.rNode == null)
     return h;
    else
     return rotateLeft(h);
   }

   return h;
  }

  public void insert(int key) {
   if (root == null) {
    root = new Node(key);
    return;
   }

   root = splay(root, key);

   if (key < root.key) {
    Node n = new Node(key);
    n.lNode = root.lNode;
    n.rNode = root;
    root.lNode = null;
    root = n;
   } else if (key > root.key) {
    Node n = new Node(key);
    n.rNode = root.rNode;
    n.lNode = root;
    root.rNode = null;
    root = n;
   }

  }

  public void remove(int key) {
   if (root == null)
    return;

   root = splay(root, key);

   if (root.key == key) {
    if (root.lNode == null) {
     root = root.rNode;
    } else {
     Node x = root.rNode;
     root = root.lNode;
     root = splay(root, key);
     root.rNode = x;
    }
   }
  }

  Node next(int key) {
   if (root == null) {
    return null;
   }
   root = splay(root, key);
   return next(key, root);
  }
  
  Node next(int key, Node root) {
   if (root == null) return null;
   Node best = null;
   if (root.key > key) best = root;
   if (root.key <= key) {
    Node tryNode = next(key, root.rNode);
    if (tryNode != null) {
     if (best == null || tryNode.key < best.key) best = tryNode;
    }
   } else {
    Node tryNode = next(key, root.lNode);
    if (tryNode != null) {
     if (best == null || tryNode.key < best.key) best = tryNode;
    }
   }
   return best;
  }

  Node prev(int key) {
   if (root == null) {
    return null;
   }
   root = splay(root, key);
   return prev(key, root);
  }
  
  Node prev(int key, Node root) {
   if (root == null) return null;
   Node best = null;
   if (root.key < key) best = root;
   if (root.key < key) {
    Node tryNode = prev(key, root.rNode);
    if (tryNode != null) {
     if (best == null || tryNode.key > best.key) best = tryNode;
    }
   } else {
    Node tryNode = prev(key, root.lNode);
    if (tryNode != null) {
     if (best == null || tryNode.key > best.key) best = tryNode;
    }
   }
   return best;
  }


  boolean contains(int key) {
   if (root == null) {
    return false;
   } else {
    root = splay(root, key);
    if (root.key == key) return true;
    return false;      
   }
  }
}

class Node {
  int key;
  Node lNode, rNode;

  Node(int key) {
   this.key = key;
  }
}

Тернарный поиск с золотым сечением

Тернарный поиск с использованием золотого сечения для поиска минимума выпуклой вниз функции

 
double gts(double l, double r, double eps) {
    final double phi = (1 + Math.sqrt(5.0)) / 2;
    final double resphi = 2 - phi;
    double x1 = l + resphi * (r - l);
    double x2 = r - resphi * (r - l);
    double f1 = f(x1);
    double f2 = f(x2);
    
    do {
        if (f1 < f2) {
            r = x2;
            x2 = x1;
            f2 = f1;
            x1 = l + resphi * (r - l);
            f1 = f(x1);
        } else {
            l = x1;
            x1 = x2;
            f1 = f2;
            x2 = r - resphi * (r - l);
            f2 = f(x2);
       }
    } while (Math.abs(r - l) > eps);
    return (x1 + x2) / 2
}

Формула Стирлинга

$$n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$$

Java template

Java Template для быстрого чтения-записи

import java.util.*;
import java.io.*;

public class Solution {
 FastScanner in;
 PrintWriter out;

 int N;

 public void solve() throws IOException {
  // solution is here
  N = in.nextInt();
  out.print(N);
 }

 public void run() {
  try {
   // works with files
   in = new FastScanner(new File("input.txt"));
   out = new PrintWriter(new File("output.txt"));

   // works with standart input-output
   //in = new FastScanner(System.in);
   //out = new PrintWriter(System.out);

   solve();

   out.close();
  } catch (IOException e) {
   e.printStackTrace();
  }
 }

 class FastScanner {
  BufferedReader br;
  StringTokenizer st;

  FastScanner(File f) {
   try {
    br = new BufferedReader(new FileReader(f));
   } catch (FileNotFoundException e) {
    e.printStackTrace();
   }
  }

  FastScanner(InputStream f) {
   br = new BufferedReader(new InputStreamReader(f));
  }

  String next() {
   while (st == null || !st.hasMoreTokens()) {
    try {
     st = new StringTokenizer(br.readLine());
    } catch (IOException e) {
     e.printStackTrace();
    }
   }
   return st.nextToken();
  }

  int nextInt() {
   return Integer.parseInt(next());
  }

  long nextLong() {
   return Long.parseLong(next());
  }

  String nextLine() {
   try {
    return br.readLine();
   } catch (IOException e) {
    e.printStackTrace();
   }
   return null;
  }
 }

 public static void main(String[] arg) {
  new Solution().run();
 }
}