Home » Archives for 2011-10-23

Lowest Common Ancestor

   2:57 AM      

//<O(N logN, O(logN)> #define mx 10010 #define logmx ceil(log(mx)) #define pii pair < int, int > //#define i64 __int64 #define inf 2147483647 int L[mx], T[mx], P[mx][logmx]; const int root = 1; bool color[mx]; long long d[mx]; vector < pii > G[mx]; void preprocess(int n){ int...

  

RMQ with Segment Tree

   2:43 AM      

#define mx 1000010 #define tmx 2000020 int a[mx]; int t[tmx]; void init(int node, int i, int j){ if(i==j){ t[node] = a[i]; return; } int mid = (i+j)>> 1; init(2*node, i, mid); init((2*node)+1, mid+1, j); t[node] = max(t[2*node], t[(2*node)+1]); } int query(int...

  

Binary Indexed Tree

   2:33 AM      

#define i64 long long i64 BIT[mx]; int n; //1-D BIT i64 read(int idx){ i64 sum = 0; while (idx > 0){ sum += BIT[idx]; idx -= (idx & -idx); } return sum; } void update(int idx, i64 val){ while (idx <= m){ BIT[idx] += val; idx += (idx &...

  

Bipartite Matching (Hopcroft-Karp)

   2:11 AM      

//Complexity: O(e√v) //n: number of nodes in left side n=[1,n] //m: number of nodes in right side m=[n+1,n+m] //G: NIL U G1[G[1,n]] U G2[G[n+1,n+m]] #define mx 100010 #define inf (1<<28) vector < int > G[mx]; int match[mx], dist[mx]; const int NIL = 0; bool bfs(int n){ int i,u,v,sz; ...