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 i,j;
    for(i = 1; i <= n; i++)for(j = 0; (1<<j) < n; j++)P[i][j] = -1;
    for(i = 1; i <= n; i++)P[i][0] = T[i];
    for (j = 1; (1<<j) < n; j++)for (i = 1; i <= n; i++)
        if (P[i][j - 1] != -1)
            P[i][j] = P[P[i][j - 1]][j - 1];
}

int getLCA(int p, int q){
    int lg, i;
    if (L[p] < L[q])swap(p,q);
    for (lg = 1; (1<<lg) <= L[p]; lg++);
    lg--;
    for (i = lg; i >= 0; i--)
        if (L[p] - (1 << i) >= L[q])
            p = P[p][i];
    if (p == q)return p;
    for (i = lg; i >= 0; i--)
        if (P[p][i] != -1 && P[p][i] != P[q][i])
            p = P[p][i], q = P[q][i];
    return T[p];
}
Tutorial of Topcoder

  

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 node, int i, int j, int si, int sj){
    if(i == si && j == sj)return t[node];
    int mid = (i+j)>> 1;
    if(sj <= mid)return query(2*node, i, mid, si, sj);
    else if(si > mid)return query((2*node)+1, mid+1, j, si, sj);
    else{
        int r1 = query(2*node, i, mid, si, mid);
        int r2 = query((2*node)+1, mid+1, j, mid+1, sj);
        return max(r1,r2);
    }
}
void update(int node, int i, int j, int idx, int val){
    if(i == j){
        a[i] = val;
        t[node] = val;
        return;
    }
    int mid = (i+j)>> 1;
    if(idx <= mid) update(2*node, i, mid, idx, val);
    else update ((2*node)+1, mid+1, j, idx, val);
    t[node] = max(t[2*node], t[(2*node)+1]);
}

  

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 & -idx);
    }
}

//2-D BIT
void update(int x , int y , i64 val){
    int y1;
    while (x <= n){
        y1 = y;
        while (y1 <= n){
            BIT[x][y1] += val;
            y1 += (y1 & -y1); 
        }
        x += (x & -x); 
    }
}

i64 read(int x, int y){
    int y1;
    i64 sum = 0;
    while (x > 0){
        y1 = y;
        while (y1 > 0){
            sum += BIT[x][y1];
            y1 -= (y1 & -y1); 
        }
        x -= (x & -x);
    }
    return sum;
}
Tutorial in Topcoder

  

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;
    queue < int > q;
    for(i = 1;i<=n;i++){
        if(match[i]==NIL){
            dist[i] = 0;
            q.push(i);
        }
        else dist[i] = inf;
    }
    dist[NIL] = inf;
    while(!q.empty()){
        u = q.front(); q.pop();
        sz = G[u].size();
        for(i=0;i < sz;i++){
            v = G[u][i];
            if(dist[match[v]]==inf){
                dist[match[v]] = dist[u] + 1;
                q.push(match[v]);
            }
        }
    }
    return (dist[NIL]!=inf);
}

bool dfs(int u){
    int sz,v,i;
    if(u!=NIL){
        sz = G[u].size();
        for(i=0;i < sz;i++){
            v = G[u][i];
            if((dist[match[v]] == dist[u]+1) && dfs(match[v])){
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
        dist[u] = inf;
        return false;
    }
    return true;
}

int Hopcroft_Karp(int n, int m){
    int i,matching;
    for(i=0;i <= (n+m+1);i++)match[i] = NIL;
    matching = 0;
    while(bfs(n)){
        for(i=1;i <= n;i++){
            if(match[i] == NIL && dfs(i))
                matching++;
        }
    }
    return matching;
}