Some Templates

Directory


Data Structure

Trie Tree

#include<cstdio>
#include<cstring>
typedef long long llint;
const bool DEBUG_ENABLE = 0;
const int MAXN = 1e6 + 5;
const int MOD = 19260827;
struct TRIE {
    int nxt[MAXN][30], cnt;
    bool end[MAXN];
    void insert(char str[]) {
        int now = 0, len = strlen(str);
        for(int i = 0; i < len; ++i) {
            int c = str[i] - 'a';
            if(!nxt[now][c]) nxt[now][c] = ++cnt;
            now = nxt[now][c];
        }
        end[now] = 1;
    }
    int find(char str[]) {
        int now = 0, len = strlen(str);
        for(int i = 0; i < len; ++i) {
            int c = str[i] - 'a';
            if(!nxt[now][c]) return 0;
            now = nxt[now][c];
        }
        return end[now];
    }
} a;

int n, m;
int main() {
/*==================================*/
#ifdef LOCAL_JUDGE
    freopen("\\Codes\\in.in", "r", stdin);
    freopen("\\Codes\\out.out", "w", stdout);
#endif
/*==================================*/
    char name[MAXN];
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%s", name);
        a.insert(name);
    }
    scanf("%d", &m);
    for(int i = 0; i < m; ++i) {
        scanf("%s", name);
        if(a.find(name)) printf("MATCHED\n");
        else printf("NEW\n");
    }
    return 0;
}

Segment Tree

#include<cstdio>
typedef long long llint;
const bool DEBUG_ENABLE = 0;
const int MAXN = 2e6 + 5;
const int MOD = 19260827;

struct TREE {
    llint ar[MAXN], a[MAXN], laz[MAXN];
    inline void build(int l, int r, int pos) {
        if(l == r) {
            ar[pos] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, pos * 2);
        build(mid + 1, r, pos * 2 + 1);
        ar[pos] = ar[pos * 2] + ar[pos * 2 + 1];
    }
    inline void pushdown(int l, int r, int s, int t, int pos) {
        laz[pos * 2] += laz[pos];
        laz[pos * 2 + 1] += laz[pos];
        int mid = (s + t) >> 1;
        ar[pos * 2] += (mid - s + 1) * laz[pos];
        ar[pos * 2 + 1] += (t - mid) * laz[pos];
        laz[pos] = 0;
    }
    inline void update(int l, int r, int s, int t, llint val, int pos) {
        if(l <= s && t <= r) {
            ar[pos] += (t - s + 1) * val;
            laz[pos] += val;
            return;
        }
        int mid = (s + t) >> 1;
        pushdown(l, r, s, t, pos);
        if(l <= mid) update(l, r, s, mid, val, pos * 2);
        if(r > mid) update(l, r, mid + 1, t, val, pos * 2 + 1);
        ar[pos] = ar[pos * 2] + ar[pos * 2 + 1];
    }
    inline llint query(int l, int r, int s, int t, int pos) {
        if(l <= s && t <= r)  return ar[pos];
        int mid = (s + t) >> 1;
        llint ans = 0;
        pushdown(l, r, s, t, pos);
        if(l <= mid) ans += query(l, r, s, mid, pos * 2);
        if(r > mid) ans += query(l, r, mid + 1, t, pos * 2 + 1);
        return ans;
    }
} a;

int n, m;
int main() {
/*==================================*/
#ifdef LOCAL_JUDGE
    freopen("\\Codes\\in.in", "r", stdin);
    freopen("\\Codes\\out.out", "w", stdout);
#endif
/*==================================*/
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a.a[i]);
    }
    a.build(1, n, 1);
    int opt, a1, a2;
    llint a3;
    for(int i = 1; i <= m; ++i) {
        scanf("%d", &opt);
        if(opt == 1) {
            scanf("%d%d%lld", &a1, &a2, &a3);
            a.update(a1, a2, 1, n, a3, 1);
        } else {
            scanf("%d%d", &a1, &a2);
            printf("%lld\n", a.query(a1, a2, 1, n, 1));
        }
    }
    return 0;
}

About Segment Tree (Chinese)

On Graph

Tarjan

Tarjan Strongly Connected Compnnects

#include<stack>
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
const int MAXN = 5e3 + 5;

vector<int> grp[MAXN];
stack<int> sta;
int n, m, _time = 1;
int vst[MAXN], low[MAXN];
bool insta[MAXN];
void dfs(int pos) {
    vst[pos] = low[pos] = _time++;
    sta.push(pos);
    insta[pos] = true;
    for(int i = 0;i < grp[pos].size(); ++i) {
        if(!vst[grp[pos][i]]) {
            dfs(grp[pos][i]);
            low[pos] = min(low[pos], low[grp[pos][i]]);
        }
        else if(insta[pos]) low[pos] = min(low[pos], low[grp[pos][i]]);
    }
    if(vst[pos] == low[pos]) {
        int las;
        do {
            printf("%d ", sta.top());
            las = sta.top();
            sta.pop();
        } while(las != pos);
        printf("\n");
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        arg1–;
        arg2–;
        grp[arg1].push_back(arg2);
    }
    for(int i = 0; i < n; ++i) if(!vst[i]) dfs(i);
    return 0;
}

Tarjan Shrink Point

Tarjan Cut Point and Bridge

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN = 5e3 + 5;

vector<int> grp[MAXN];
int n, m, _time = 1, ans, ans2;
int vst[MAXN], low[MAXN], fth[MAXN];
bool insta[MAXN], pts[MAXN];
bool brdg[MAXN][MAXN];
void dfs(int pos) {
    vst[pos] = low[pos] = _time++;
    int child = 0;
    for(int i = 0;i < grp[pos].size(); ++i) {
        if(!vst[grp[pos][i]]) {
            child++;
            fth[grp[pos][i]] = pos;
            dfs(grp[pos][i]);
            if(fth[pos] == -1 && child >= 2) pts[pos] = true;
            if(fth[pos] != -1 && low[grp[pos][i]] >= vst[pos]) pts[pos] = true;
            if(low[grp[pos][i]] > vst[pos]) brdg[pos][grp[pos][i]] = true;
            low[pos] = min(low[pos], low[grp[pos][i]]);
        }
        else if(grp[pos][i] != fth[pos]) low[pos] = min(low[pos], low[grp[pos][i]]);
    }
}
int main() {
    memset(fth, -1, sizeof(fth));
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        arg1–;
        arg2–;
        grp[arg2].push_back(arg1);
        grp[arg1].push_back(arg2);
    }
    for(int i = 0; i < n; ++i) if(!vst[i]) dfs(i);
    for(int i = 0; i < n; ++i) if(pts[i]) ans++;
    for(int i = 0; i < n; ++i)
        for(int j = 0;j < n; ++j)
            if(brdg[i][j]) ans2++;
    printf("%d\n%d", ans, ans2);
    return 0;
}

Shortest Path

Floyd

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 1e9
double dp[1005][1005];
double map[1005][1005];
int main() {
    int n,m,kkk,u,v;
    double lenth;
    scanf("%d %d %d",&n,&m,&kkk);
    for(int i=1; i<=m; i++) {
        scanf("%d %d %lf",&u,&v,&lenth);
        map[v][u]=map[u][v]=max(map[u][v],lenth);
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(!map[i][j]) map[i][j]=INF;
            dp[i][j]=map[i][j];
        }
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
    for(int i=1; i<=kkk; i++) {
        scanf("%d %d",&u,&v);
        if(ceil(dp[u][v])==dp[u][v]) printf("%.0lf\n",dp[u][v]);
        else printf("%.1lf\n",dp[u][v]);
    }
    return 0;
}

Dijkstra (With stack)

#include<cstdio>
#include<vector>
#include<queue> 
#include<cstring>
using namespace std;
const int MAXN = 1e5 + 5;

struct edges {
    int to, we;
    bool operator < (const edges &other) const {
        return we > other.we;
    }
};

int n, m, dis[MAXN];
bool vis[MAXN];
vector<edges> grp[MAXN];

void dij() {
    priority_queue<edges> que;
    que.push((edges) {1, 0});
    while(!que.empty()) {
        edges k = que.top();
        que.pop();
        if(vis[k.to]) continue;
        vis[k.to] = 1;
        dis[k.to] = k.we;
        for(int i = 0; i < grp[k.to].size(); ++i){
            que.push((edges) {grp[k.to][i].to, grp[k.to][i].we + k.we});
        }
    }
}

int main() {
    memset(dis, 0x3f, sizeof(dis));
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i) {
        int arg1, arg2, arg3;
        scanf("%d%d%d", &arg1, &arg2, &arg3);
        grp[arg1].push_back((edges) {arg2, arg3});
        grp[arg2].push_back((edges) {arg1, arg2});
    }
    dij();
    for(int i = 1; i <= n; ++i) {
        printf("The shortest path length from 1 to %d is %d. \n", i, dis[i]);
    }
    return 0;
}

Numbers

RMQ Problem Using Sparese Table

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 1e5 + 5;

int n, m;
int lg[MAXN], rmq[MAXN][21], a[MAXN];
void init() {
    lg[0] = -1;
    for(int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; ++i) rmq[i][0] = a[i];
    for(int j = 1; (1 << j) <= n; ++j)
        for(int i = 1; i + (1 << j) - 1 <= n; ++i)
            rmq[i][j] = max(rmq[i][j-1], rmq[i + (1 << j - 1)][j - 1]);
}

int getres(int l, int r) {
    int k = lg[r - l + 1];
    return max(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    init();
    for(int i = 1; i <= m; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        printf("%d\n", getres(arg1, arg2));
    }
    return 0;
}

二叉搜索树

Splay

#include<cstdio>
using namespace std;
const bool CONST_DEBUG = false;
const int MAXN = 1e5 + 5;

struct N {
    int fa, ch[2], val, cnt, size;
} spl[MAXN];
int n, root, cnt;

inline void update(int idx) {
    if(CONST_DEBUG) printf("update()\n");
    spl[idx].size = spl[spl[idx].ch[0]].size + spl[spl[idx].ch[1]].size + spl[idx].cnt;

}

inline bool ide(int idx, int fa) {
    if(CONST_DEBUG) printf("ide()\n");
    return spl[fa].ch[1] == idx;
}

inline void connect(int idx, int fa, int so) {
    if(CONST_DEBUG) printf("connect()\n");
    spl[fa].ch[so] = idx;
    spl[idx].fa = fa;
}

inline void rotate(int idx) {
    if(CONST_DEBUG) printf("rotate()\n");
    int fa = spl[idx].fa, gfa = spl[fa].fa, so = ide(idx, fa);
    connect(spl[idx].ch[so ^ 1], fa, so);
    connect(idx, gfa, ide(fa, gfa));
    connect(fa, idx, so ^ 1);
    update(fa), update(idx);
}

inline void splaying(int idx, int top) {
    if(CONST_DEBUG) printf("splaying()\n");
    if(!top) root = idx;
    while(spl[idx].fa != top) {
        int fa = spl[idx].fa, gfa = spl[fa].fa;
        if(gfa != top) ide(fa, gfa) ^ ide(idx, fa) ? rotate(idx) : rotate(fa);
        rotate(idx);
    }
}

inline void newnode(int &idx, int fa, int val) {
    if(CONST_DEBUG) printf("newnode()\n");
    spl[idx = ++cnt].val = val;
    spl[idx].fa = fa;
    spl[idx].size = spl[idx].cnt = 1;
}

inline void delnode(int idx) {
    if(CONST_DEBUG) printf("delnode()\n");
    splaying(idx, 0);
    if(spl[idx].cnt > 1) spl[idx].cnt--;
    else if(spl[idx].ch[1]) {
        int so = spl[idx].ch[1];
        while(spl[so].ch[0]) so = spl[so].ch[0];
        splaying(so, 0);
        connect(spl[idx].ch[0], so, 0);
        root = so;
        spl[so].fa = 0;
        update(root);
    } else root = spl[idx].ch[0], spl[root].fa = 0;
}

inline void ins(int &idx, int fa, int val) {
    if(CONST_DEBUG) printf("ins()\n");
    if(!idx) newnode(idx, fa, val), splaying(idx, 0);
    else if(val < spl[idx].val) ins(spl[idx].ch[0], idx, val);
    else if(val > spl[idx].val) ins(spl[idx].ch[1], idx, val);
    else spl[idx].cnt++, splaying(idx, 0);
}

inline void del(int idx, int val) {
    if(CONST_DEBUG) printf("del()\n");
    if(val == spl[idx].val) delnode(idx);
    else if(val < spl[idx].val) del(spl[idx].ch[0], val);
    else del(spl[idx].ch[1], val);
}

inline int getrank(int val) {
    if(CONST_DEBUG) printf("getrank()\n");
    int pos = root, rank = 1;
    while(pos) {
        if(spl[pos].val == val) {
            rank += spl[spl[pos].ch[0]].size;
            splaying(pos, 0);
            break;
        }
        if(val <= spl[pos].val) pos = spl[pos].ch[0];
        else {
            rank += spl[spl[pos].ch[0]].size + spl[pos].cnt;
            pos = spl[pos].ch[1];
        }
    }
    return rank;
}

inline int getnum(int rank) {
    if(CONST_DEBUG) printf("getnum()\n");
    int pos = root;
    while(pos) {
        int lsize = spl[spl[pos].ch[0]].size;
        if(lsize + 1 <= rank && rank <= lsize + spl[pos].cnt) {
            splaying(pos, 0);
            break;
        } else if(lsize >= rank) pos = spl[pos].ch[0];
        else {
            rank -= lsize + spl[pos].cnt;
            pos = spl[pos].ch[1];
        }
    }
    return spl[pos].val;
}

int main() {
    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
    scanf("%d", &n);
    int opt, x;
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d", &opt, &x);
        switch(opt) {
            case 1:
                ins(root, 0, x);
                break;
            case 2:
                del(root, x);
                break;
            case 3:
                printf("%d\n", getrank(x));
                break;
            case 4:
                printf("%d\n", getnum(x));
                break;
            case 5:
                printf("%d\n", getnum(getrank(x) - 1));
                break;
            case 6:
                printf("%d\n", getnum(getrank(x + 1)));
                break;
        }
    }
    return 0;
}

Diameter of A Tree

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100005;

struct EDGE {
    int to, le;
};
vector<EDGE> grp[MAXN];
int n, m, t, ans;
int f1[MAXN], f2[MAXN];

void add(int x, int y, int z) {
    grp[x].push_back((EDGE) {y, z});
}

void dp(int pos, int fa) {
    for(int i = 0;i < grp[pos].size(); ++i) {
        if(grp[pos][i].to == fa) continue;
        dp(grp[pos][i].to, pos);
        if(f1[pos] < f1[grp[pos][i].to] + grp[pos][i].le) {
            f2[pos] = f1[pos];
            f1[pos] = f1[grp[pos][i].to] + grp[pos][i].le;
        }
        else if(f2[pos] < f1[grp[pos][i].to] + grp[pos][i].le) f2[pos] = f1[grp[pos][i].to] + grp[pos][i].le;
        ans = max(ans, f1[pos] + f2[pos]);
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i < n; ++i) {
        int arg1, arg2;
        scanf("%d%d", &arg1, &arg2);
        add(arg1, arg2, 1);
        add(arg2, arg1, 1);
    }
    dp(1, 0);
    printf("%d", ans);
    return 0;
}

Tree Chain Patition

#include<cstdio>
#include<vector>
typedef long long llint;
const bool DEBUG_ENABLE = 1;
const llint MAXN = 1e6 + 5;
const llint MOD = 19260827;

llint ti, n, m;
struct TREE {
    llint we[MAXN], siz[MAXN], dep[MAXN], tim[MAXN], son[MAXN], fa[MAXN], top[MAXN], wei[MAXN];
    std::vector<llint> grp[MAXN];
    inline void findSize(llint pos, llint fat) {
        fa[pos] = fat;
        dep[pos] = dep[fat] + 1;
        siz[pos] = 1;
        llint maxsize = -1;
        for(llint i = 0; i < grp[pos].size(); ++i) {
            llint v = grp[pos][i];
            if(v == fat) continue;
            findSize(v, pos);
            siz[pos] += siz[v];
            if(siz[v] > maxsize) maxsize = siz[v], son[pos] = v;
        }
    }
    inline void partition(llint pos, llint tp) {
        tim[pos] = ++ti;
        top[pos] = tp;
        wei[ti] = we[pos];
        if(!son[pos]) return;
        partition(son[pos], tp);
        for(llint i = 0; i < grp[pos].size(); ++i) {
            llint v = grp[pos][i];
            if(v == son[pos] || v == fa[pos]) continue;
            partition(v, v);
        }
    }
    inline void addEdge(llint u, llint v) {
        grp[u].push_back(v);
    }
    llint ar[MAXN], laz[MAXN];
    inline void build(llint rt, llint l, llint r) {
        if(l == r) {
            ar[rt] = wei[l];
            return;
        }
        llint mid = (l + r) >> 1;
        build(rt * 2, l, mid);
        build(rt * 2 + 1, mid + 1, r);
        ar[rt] = ar[rt * 2] + ar[rt * 2 + 1];
    }
    inline void pushdown(llint l, llint r, llint s, llint t, llint pos) {
        laz[pos * 2] += laz[pos];
        laz[pos * 2 + 1] += laz[pos];
        llint mid = (s + t) >> 1;
        ar[pos * 2] += (mid - s + 1) * laz[pos];
        ar[pos * 2 + 1] += (t - mid) * laz[pos];
        laz[pos] = 0;
    }
    inline llint getSum(llint l, llint r, llint s, llint t, llint pos) {
        if(l <= s && t <= r) return ar[pos];
        llint mid = (s + t) >> 1;
        llint ans = 0;
        pushdown(l, r, s, t, pos);
        if(l <= mid) ans += getSum(l, r, s, mid, pos * 2);
        if(r > mid) ans += getSum(l, r, mid + 1, t, pos * 2 + 1);
        return ans;
    }
    inline void update(llint l, llint r, llint val, llint s, llint t, llint pos) {
        if(l <= s && t <= r) {
            ar[pos] += (t - s + 1) * val;
            laz[pos] += val;
            return;
        }
        llint mid = (s + t) >> 1;
        pushdown(l, r, s, t, pos);
        if(l <= mid) update(l, r, val, s, mid, pos * 2);
        if(r > mid) update(l, r, val, mid + 1, t, pos * 2 + 1);
        ar[pos] = ar[pos * 2] + ar[pos * 2 + 1];
    }
    inline void multiUpdate(llint pos, llint val) {
        update(tim[pos], tim[pos] + siz[pos] - 1, val, 1, ti, 1);
    }
    inline llint query(llint pos) {
        llint ans = 0;
        llint x = pos, y = 1;
        while(top[x] != top[y]) {
            if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
            ans += getSum(tim[top[x]], tim[x], 1, ti, 1);
            x = fa[top[x]];
        }
        if(dep[x] > dep[y]) std::swap(x, y);
        ans += getSum(tim[x], tim[y], 1, ti, 1);
        return ans;
    }
} a;

int main() {
/*==================================*/
#ifdef LOCAL_JUDGE
    freopen("\\Codes\\in.in", "r", stdin);
    freopen("\\Codes\\out.out", "w", stdout);
#endif
/*==================================*/
    scanf("%lld%lld", &n, &m);
    for(llint i = 1; i <= n; ++i) {
        scanf("%lld", &a.we[i]);
    }
    llint u, v;
    for(llint i = 1; i < n; ++i) {
        scanf("%lld%lld", &u, &v);
        a.addEdge(u, v);
        a.addEdge(v, u);
    }
    a.findSize(1, 0);
    a.partition(1, 1);
    a.build(1, 1, ti);
    llint opt;
    for(llint i = 1; i <= m; ++i) {
        scanf("%lld%lld", &opt, &u);
        if(opt == 1) {
            scanf("%lld", &v);
            a.update(a.tim[u], a.tim[u], v, 1, ti, 1);
        } else if(opt == 2) {
            scanf("%lld", &v);
            a.multiUpdate(u, v);
        } else {
            printf("%lld\n", a.query(u));
        }
    }
    return 0;
}

Solution (Chinese)

Like

Leave a Reply

Your Email address will not be published. The required items are marked with *