POJ3207 Ikki's Story IV - Panda's Trick < 2-SAT >

发表于 2017-10-14

字数统计: 675 | 阅读时长 ≈ 4

Problem

Ikki’s Story IV - Panda’s Trick

Description

liympanda, one of Ikki’s friend, likes playing games with Ikki. Today after minesweeping with Ikki and winning so many times, he is tired of such easy games and wants to play another game with Ikki.
liympanda has a magic circle and he puts it on a plane, there are n points on its boundary in circular border: . Evil panda claims that he is connecting m pairs of points. To connect two points, liympanda either places the link entirely inside the circle or entirely outside the circle. Now liympanda tells Ikki no two links touch inside/outside the circle, except on the boundary. He wants Ikki to figure out whether this is possible…
Despaired at the minesweeping game just played, Ikki is totally at a loss, so he decides to write a program to help him.

Input

The input contains exactly one test case.
In the test case there will be a line consisting of of two integers: and . The following lines each contain two integers and , which denote the endpoints of the wire. Every point will have at most one link.

Output

Output a line, either “panda is telling the truth…” or “the evil panda is lying again”.

阅读全文 »

BZOJ1997 Planer < 2-SAT >

发表于 2017-10-14

字数统计: 444 | 阅读时长 ≈ 2

Problem

Planer

Description

Input

Output

阅读全文 »

201701001-08总结

发表于 2017-10-10

字数统计: 1,695 | 阅读时长 ≈ 6

长沙雅礼中学2017国庆训练滚粗记

阅读全文 »

【福利】洛谷模板汇总

发表于 2017-09-29

字数统计: 12,992 | 阅读时长 ≈ 81

Graph Theory

Disjoint Set

#include <iostream>
#define MAX_N 10000
using namespace std;
int n, m, f, x, y, father[MAX_N+5];
int getfather(int v) {
    if (father[v] == v) {
        return v;
    }
    father[v] = getfather(father[v]);
    return father[v];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
    for (int i = 0; i < m; i++) {
        cin >> f >> x >> y;
        if (f == 1) {
            int f1 = getfather(x);
            int f2 = getfather(y);
            if (f1 != f2) {
                father[f1] = f2;
            }
        } else {
            int f1 = getfather(x);
            int f2 = getfather(y);
            if (f1 != f2) {
                cout << "N" << endl;
            } else {
                cout << "Y" << endl;
            }
        }
    }
    return 0;
}

Minimum Spanning Tree

Kruskal

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 5000
#define MAX_M 200000
using namespace std;
struct node {
    int u, v, l;
} edge[MAX_M+5];
int n, m, tot = 0;
int father[MAX_N+5];
bool comp(const node &a, const node &b) {
    return a.l < b.l;
}
int getfather(int v) {
    if (father[v] == v) {
        return v;
    }
    father[v] = getfather(father[v]);
    return father[v];
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].l;
    }
    sort(edge, edge+m, comp);
    for (int i = 1; i <= n; i++)	father[i] = i;
    int flag = n-1;
    for (int i = 0; i < m; i++) {
        int f1 = getfather(edge[i].u);
        int f2 = getfather(edge[i].v);
        if (f1 != f2) {
            father[f1] = f2;
            tot += edge[i].l;
            flag--;
        }
        if (flag == 0)	break;
    }
    if (flag == 0) {
        cout << tot;
    } else {
        cout << "orz";
    }
    return 0;
}

Prim

#include <bits/stdc++.h>
#define MAX_N 5000
#define INF 2147483647
using namespace std;
vector <int> G[MAX_N+5], E[MAX_N+5];
int n, m, dis[MAX_N+5], tot;	bool col[MAX_N+5];
void addedge(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c);}
void Prim() {
    for (int i = 1; i <= n; i++) dis[i] = INF;	dis[1] = 0;
    for (int i = 1, u = -1; i <= n; i++, u = -1) {
        for (int j = 1; j <= n; j++)
            if (!col[j] && (u == -1 || dis[u] > dis[j]))	u = j;
        col[u] = true, tot += dis[u];
        for (int j = 0; j < (int)G[u].size(); j++) {
            int v = G[u][j], c = E[u][j];
            if (!col[v] && dis[v] > c)	dis[v] = c;
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, u, v, c; i < m; i++)
        scanf("%d%d%d", &u, &v, &c), addedge(u, v, c), addedge(v, u, c);
    Prim();	printf("%d", tot);
    return 0;
}

Shortest Path

Dijkstra

#include <bits/stdc++.h>
#define MAX_N 10000
#define INF 2147483647
#define pii pair <int, int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
int n, m, s, dis[MAX_N+5];
vector <int> G[MAX_N+5], E[MAX_N+5];
void addedge(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c);}
void Dijkstra() {
    for (int i = 1; i <= n; i++)	dis[i] = INF;	dis[s] = 0;
    priority_queue <pii> que;	que.push(mp(0, s));
    while (!que.empty()) {
        int u = que.top().sec, d = que.top().fir;
        que.pop();	if (dis[u] != -d)	continue;
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i], c = E[u][i];
            if (dis[u]+c >= dis[v])	continue;
            dis[v] = dis[u]+c, que.push(mp(-dis[v], v));
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0, u, v, c; i < m; i++)
        scanf("%d%d%d", &u, &v, &c), addedge(u, v, c);
    Dijkstra();
    for (int i = 1; i <= n; i++)	printf("%d ", dis[i]);
    return 0;
}

SPFA

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_M 500000
#define MAX_N 10000
#define INF 2147483647
using namespace std;
struct node {
    int v, len, next;
    node() {
        v = len = next = 0;
    }
} edge[MAX_M+5];
int n, m, s;
int first[MAX_N+5], cnt = 0;
int dis[MAX_N+5];
void insert(int u, int v, int l) {
    cnt++;
    edge[cnt].v = v;
    edge[cnt].len = l;
    edge[cnt].next = first[u];
    first[u] = cnt;
}
void SPFA() {
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
    }
    int que[MAX_N*20+5], mark[MAX_N+5];
    int head = 0, tail = 1;
    memset(mark, 0, sizeof(mark));
    que[1] = s;
    mark[s] = 1;
    dis[s] = 0;
    while (head <= tail) {
        head++;
        for (int tmp = first[que[head]]; tmp; tmp = edge[tmp].next) {
            if (dis[que[head]]+edge[tmp].len < dis[edge[tmp].v]) {
                dis[edge[tmp].v] = dis[que[head]]+edge[tmp].len;
                if (mark[edge[tmp].v] == 0) {
                    mark[edge[tmp].v] = 1;
                    tail++;
                    que[tail] = edge[tmp].v;
                }
            }
        }
        mark[que[head]] = 0;
    }
}
int main() {
    cin >> n >> m >> s;
    memset(first, 0, sizeof(first));
    int u, v, l;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> l;
        insert(u, v, l);
    }
    SPFA();
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    return 0;
}

Tarjan

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define MAX_N 100000
using namespace std;
int n, m, c[MAX_N+5], f[MAX_N+5];
int dfn[MAX_N+5], low[MAX_N+5], col[MAX_N+5], val[MAX_N+5], ind, cnt;
vector <int> G[MAX_N+5], E[MAX_N+5];
stack <int> sta;
bool insta[MAX_N+5];
void tarjan(int u) {
    dfn[u] = low[u] = ++ind, sta.push(u), insta[u] = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!dfn[v])	tarjan(v), low[u] = min(low[u], low[v]);
        else if (insta[v])	low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        cnt++;
        for (int i = sta.top(); ; i = sta.top()) {
            col[i] = cnt, val[cnt] += c[i], insta[i] = false;
            sta.pop();	if (u == i)	break;
        }
    }
}
int DFS(int u) {
    if (f[u])	return f[u];
    int mx = 0;
    for (int i = 0; i < E[u].size(); i++)	mx = max(mx, DFS(E[u][i]));
    return f[u] = val[u]+mx;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	scanf("%d", &c[i]);
    while (m--) {
        int u, v;	scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])	tarjan(i);
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];	if (col[u] == col[v])	continue;
            E[col[u]].push_back(col[v]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= cnt; i++)
        if (!f[i])	ans = max(ans, DFS(i));
    printf("%d", ans);
    return 0;
}

Cut Vertex

#include <iostream>
#include <cstdio>
#define MAX_N 100000
#define MAX_M 200000
using namespace std;
struct Edge {
    int v, next;
} edge[MAX_M+5];
int first[MAX_N+5], flag[MAX_N+5], num[MAX_N+5], low[MAX_N+5];
int n, m, cnt = 0;
void insert(int u, int v, int pos) {
    edge[pos].next = first[u];
    edge[pos].v = v;
    first[u] = pos;
}
void dfs(int cur, int father) {
    int child = 0;
    num[cur] = low[cur] = ++cnt;
    for (int tmp = first[cur]; tmp; tmp = edge[tmp].next) {
        if (!num[edge[tmp].v]) {
            child++;
            dfs(edge[tmp].v, cur);
            low[cur] = min(low[cur], low[edge[tmp].v]);
            if (low[edge[tmp].v] >= num[cur]) {
                flag[cur] = 1;
            }
        } else if (num[edge[tmp].v] < num[cur] && edge[tmp].v != father) {
            low[cur] = min(low[cur], num[edge[tmp].v]);
        }
    }
    if (father == -1 && child == 1) {
        flag[cur] = 0;
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        insert(u, v, i*2+1);
        insert(v, u, i*2+2);
    }
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        if (!num[i]) {
            dfs(i, -1);
        }
        if (flag[i]) {
            tot++;
        }
    }
    cout << tot << endl;
    for (int i = 1; i <= n; i++) {
        if (flag[i]) {
            cout << i << " ";
        }
    }
    return 0;
}

Lowest Common Ancestor

Multiplication

#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 500000
using namespace std;
struct Edge {
    int next, to;
} edge[(MAX_N<<1)+5];
int n, m, s, x, y, cnt;
int d[MAX_N+5], p[MAX_N+5][25], first[MAX_N+5];
bool vis[MAX_N+5];
inline int read() {
    int ret = 0;	char ch = getchar();
    while (ch < '0' || ch > '9')	ch = getchar();
    while (ch >= '0' && ch <= '9')	ret = ret*10+ch-'0', ch = getchar();
    return ret;
}
void INSERT(int a, int b) {
    edge[++cnt].next = first[a];
    edge[cnt].to = b;
    first[a] = cnt;
}
void DFS(int u) {
    vis[u] = true;
    for (int i = 1; (1<<i) <= n; i++) {
        if ((1<<i) <= d[u]) {
            p[u][i] = p[p[u][i-1]][i-1];
        }
    }
    for (int i = first[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!vis[v]) {
            d[v] = d[u]+1;
            p[v][0] = u;
            DFS(v);
        }
    }
}
int LCA(int a, int b) {
    int i, j;
    if (d[a] < d[b])	swap(a, b);
    for (i = 0; (1<<i) <= d[a]; i++) {}
    i--;
    for (j = i; j >= 0; j--) {
        if (d[a]-(1<<j) >= d[b]) {
            a = p[a][j];
        }
    }
    if (a == b) {
        return a;
    }
    for (j = i; j >= 0; j--) {
        if (p[a][j] != p[b][j]) {
            a = p[a][j];
            b = p[b][j];
        }
    }
    return p[a][0];
}
int main() {
    n = read(), m = read(), s = read();
    for (int i = 1; i < n; i++) {
        x = read(), y = read();
        INSERT(x, y);
        INSERT(y, x);
    }
    DFS(s);
    for (int i = 0; i < m; i++) {
        x = read(), y = read();
        cout << LCA(x, y) << endl; 
    }
    return 0;
}

TreeChainDivision

#include <bits/stdc++.h>
#define MAX_N 500000
using namespace std;
vector <int> G[MAX_N+5];
int n, m, r, dep[MAX_N+5], sz[MAX_N+5];
int fa[MAX_N+5], son[MAX_N+5], top[MAX_N+5];
void DFS(int u) {
    sz[u] = 1;
    for (auto v : G[u]) {
        if (v == fa[u])	continue;
        fa[v] = u, dep[v] = dep[u]+1, DFS(v), sz[u] += sz[v];
        if (!son[u] || sz[son[u]] < sz[v])	son[u] = v;
    }
}
void DFS(int u, int tp) {
    top[u] = tp;	if (son[u])	DFS(son[u], tp);
    for (auto v : G[u])	if ((v^fa[u]) && (v^son[u]))	DFS(v, v);
}
int LCA(int u, int v) {
    while (top[u]^top[v])
        if (dep[top[u]] > dep[top[v]])	u = fa[top[u]];
        else	v = fa[top[v]];
    return dep[u] < dep[v] ? u : v;
}
int main() {
    scanf("%d%d%d", &n, &m, &r);	for (int i = 1, u, v; i < n; i++) scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
    DFS(r), DFS(r, r);	while (m--) {int u, v;	scanf("%d%d", &u, &v);	printf("%d\n", LCA(u, v));}	return 0;
}

Negative Loop

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 200000
#define SIZE 25000000
using namespace std;
int f;	char BUF[SIZE], *buf = BUF;
inline void read(int &x) {
    bool flag = 0;	while (*buf < 48)	if (*buf++ == 45)	flag = 1;
    x = 0;	while (*buf > 32)	x = x*10+*buf++-48;	x = flag ? -x : x;
}
vector <int> G[MAX_N+5], E[MAX_N+5];
int dis[MAX_N+5];
bool insta[MAX_N+5], flag;
void init(int n) {
    flag = false;
    for (int i = 1; i <= n; i++)	G[i].clear(), E[i].clear();
    memset(dis, 0, sizeof(dis)), memset(insta, false, sizeof(insta));
}
void DFS(int u) {
    insta[u] = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i], c = E[u][i];
        if (dis[u]+c >= dis[v])	continue;
        if (insta[v] || flag) {flag = true;	break;}
        dis[v] = dis[u]+c, DFS(v);
    }
    insta[u] = false;
}
int main() {
    f = fread(BUF, 1, SIZE, stdin);
    int T;	read(T);
    while (T--) {
        int n, m;	read(n), read(m);	init(n);
        while (m--) {
            int u, v, c;	read(u), read(v), read(c);
            G[u].push_back(v), E[u].push_back(c);
            if (c >= 0)	G[v].push_back(u), E[v].push_back(c);
        }
        for (int i = 1; i <= n; i++) {DFS(i);	if (flag)	break;}
        if (flag)	printf("YE5\n");
        else	printf("N0\n");
    }
    return 0;
}

Network Flow

#include <bits/stdc++.h>
#define MAX_N 10000
#define MAX_M 100000
#define INF 0x7f7f7f7f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[(MAX_M<<1)+5];
void init() {memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow;	int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = 1; i <= n; i++) cr[i] = pr[i];}
void rec() {for (int i = 1; i <= n; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0;	cpy();	while (BFS()) ret += DFS(s, INF), rec();	return ret;}
int main() {
    read(n), read(m), read(s), read(t), init();
    for (int i = 1, u, v, c; i <= m; i++)
        read(u), read(v), read(c), addedge(u, v, c);
    return printf("%d\n", Dinic()), 0;
}

Minimum Cost Maximum Flow

#include <bits/stdc++.h>
#define MAX_N 5000
#define MAX_M 50000
#define INF 0x7f7f7f7f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[(MAX_M<<1)+5];
void init() {memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t]*flow;	return true;
}
int main() {
    read(n), read(m), read(s), read(t), init();
    for (int i = 1, u, v, c, w; i <= m; i++)
        read(u), read(v), read(c), read(w), addedge(u, v, c, w);
    while (SPFA()) ;	printf("%d %d\n", mxf, mic);
    return 0;
}

Bipartite Matching

Hungary

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 1000
using namespace std;
int n, m, e, match[MAX_N+5], cnt;
vector <int> G[MAX_N+5];
bool vis[MAX_N+5];
bool DFS(int u) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) {
            vis[v] = true;
            if (!match[v] || DFS(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}
int main() {
    cin >> n >> m >> e;
    int a, b;
    for (int i = 0; i < e; i++) {
        cin >> a >> b;
        if (a > n || b > m)	continue;
        G[a].push_back(b);
    }
    for (int i = 1; i <= n; i++) {
        memset(vis, false, sizeof(vis));
        if (DFS(i)) {
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

Dinic

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 2000
#define MAX_M 1000000
#define INF 2147483647
using namespace std;
int n, m, s, t, n1, n2;
int pre[MAX_N+5], tmp[MAX_N+5], d[MAX_N+5], cnt;
struct node {int v, c, nxt;} E[MAX_M*2+MAX_N*2+5];
void init() {cnt = 0; s = 0, t = n; memset(pre, -1, sizeof(pre));}
void insert(int u, int v, int c) {E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pre[u], pre[u] = cnt++;}
bool BFS() {
    memset(d, -1, sizeof(d));
    queue <int> que;
    que.push(s), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();
        for (int i = pre[u]; i != -1; i = E[i].nxt) {
            int v = E[i].v;
            if (E[i].c && d[v] == -1) {
                d[v] = d[u]+1;
                que.push(v);
            }
        }
        que.pop();
    }
    return d[t] != -1;
}
int DFS(int u, int flow) {
    if (u == t)	return flow;
    int ret = 0;
    for (int &i = pre[u]; i != -1; i = E[i].nxt) {
        int v = E[i].v;
        if (E[i].c && d[u]+1 == d[v]) {
            int tmp = DFS(v, min(flow, E[i].c));
            E[i].c -= tmp, E[i^1].c += tmp, flow -= tmp, ret += tmp;
            if (!flow)	break;
        }
    }
    if (!ret)	d[u] = -1;
    return ret;
}
int Dinic() {
    int ret = 0;
    for (int i = 0; i <= n; i++)	tmp[i] = pre[i];
    while (BFS()) {
        ret += DFS(s, INF);
        for (int i = 0; i <= n; i++)	pre[i] = tmp[i];
    }
    return ret;
}
int main() {
    scanf("%d%d%d", &n1, &n2, &m);	n = n1+n2+1;
    init();
    for (int i = 1; i <= n1; i++)	insert(s, i, 1), insert(i, s, 0);
    for (int i = n1+1; i <= n1+n2; i++)	insert(i, t, 1), insert(t, i, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (u > n1 || v > n2)	continue;
        insert(u, n1+v, 1), insert(n1+v, u, 0);
    }
    printf("%d", Dinic());
    return 0;
}

Math Theory

Gauss Elimination

#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 100
#define EXP 1e-7
using namespace std;
typedef double fnt;
int n;	vector <fnt> f[MAX_N+5];	fnt ans[MAX_N+5];
bool gauss() {
    for (int i = 1, tmp; i <= n; i++) {
        for (tmp = i; tmp <= n; tmp++)	if (f[tmp][i] <= -EXP || f[tmp][i] >= EXP)	break;
        if (tmp > n)	return false;	swap(f[i], f[tmp]);
        for (int j = 1; j <= n; j++) {
            fnt div = f[j][i]/f[i][i];	if (j == i)	continue;
            for (int k = i; k <= n+1; k++)	f[j][k] -= f[i][k]*div;
        }
    }
    for (int i = 1; i <= n; i++)	ans[i] = f[i][n+1]/f[i][i];
    return true;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        f[i].push_back(0);
        for (int j = 1; j <= n+1; j++) {
            fnt x;	scanf("%lf", &x);
            f[i].push_back(x);
        }
    }
    if (gauss())	for (int i = 1; i <= n; i++)	printf("%.2lf\n", ans[i]);
    else	printf("No Solution");
    return 0;
}

Inverse

#include <iostream>
#include <cstdio>
#define MAX_N 3000000
using namespace std;
typedef long long lnt;
lnt inv[MAX_N+5];
void init(int n, lnt p) {inv[0] = inv[1] = 1;	for (int i = 2; i <= n; i++)	inv[i] = (p-p/i*inv[p%i]%p)%p;}
int main() {
    int n;	lnt p;	scanf("%d%lld", &n, &p);
    init(n, p);
    for (int i = 1; i <= n; i++)	printf("%lld\n", inv[i]);
    return 0;
}

Linear Basis

#include <iostream>
#include <cstdio>
#define MAX_N 50
using namespace std;
typedef long long lnt;
int n;	lnt base[MAX_N+5], pow[MAX_N+5];
int main() {
    scanf("%d", &n);	pow[0] = 1;
    for (int i = 1; i <= MAX_N; i++)	pow[i] = pow[i-1]*2;
    for (int i = 1; i <= n; i++) {
        lnt x;	scanf("%lld", &x);
        for (int j = MAX_N; j >= 0; j--)	if (pow[j]&x) {
            if (base[j])	x ^= base[j];
            else {base[j] = x;	break;}
        }
    }
    lnt ans = 0;
    for (int i = MAX_N; i >= 0; i--)	if ((ans^pow[i]) > ans)	ans ^= base[i];
    printf("%lld", ans);
    return 0;
}

Lucas

#include <iostream>
#include <cstdio>
#define MAX_P 100000
using namespace std;
typedef long long lnt;
lnt f[MAX_P+5] = {1};
void init(lnt p) {for (int i = 1; i <= MAX_P; i++)	f[i] = f[i-1]*i%p;}
lnt FLT(lnt x, lnt p) {
    lnt ret = 1;	x %= p;
    for (int k = p-2; k; k >>= 1)	ret = k%2 ? ret*x%p : ret, x = x*x%p;
    return ret;
}
lnt lucas(lnt n, lnt m, lnt p) {return m ? (n%p >= m%p ? f[n%p]*FLT(f[m%p]*f[n%p-m%p], p)*lucas(n/p, m/p, p)%p : 0) : 1;}
int main() {
    int T;	scanf("%d", &T);
    while (T--) {
        lnt n, m, p;	scanf("%lld%lld%lld", &n, &m, &p);
        init(p), printf("%lld\n", lucas(n+m, min(n, m), p)%p);
    }
    return 0;
}

Matrix Fast Power

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100
#define MOD 1000000007
using namespace std;
int n;
struct Matrix {
    long long ele[MAX_N][MAX_N];
    inline Matrix operator * (const Matrix &x) const {
        Matrix ret;
        memset(ret.ele, 0, sizeof(ret.ele));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    ret.ele[i][j] = (ret.ele[i][j]+ele[i][k]*x.ele[k][j])%MOD;
        return ret;
    }
};
Matrix Power(Matrix a, long long k) {
    if (k == 1)    return a;
    Matrix ret = Power(a, k/2);
    if (k%2)    return a*ret*ret;
    return ret*ret;
}
int main() {
    long long k;
    Matrix a;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a.ele[i][j];
    a = Power(a, k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << a.ele[i][j] << " ";
        cout << endl;
    }
    return 0;
}

Prime Sieve

#include <bits/stdc++.h>
#define MAX_N 10000000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;	bool NotPri[MAX_N+5];
int pri[MAX_N+5], mu[MAX_N+5], phi[MAX_N+5], cnt;
void init() {
    NotPri[1] = true, mu[1] = phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1, phi[i] = i-1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > n) break;	NotPri[i*pri[j]] = true;
            if (i%pri[j]) phi[i*pri[j]] = phi[i]*phi[pri[j]], mu[i*pri[j]] = -mu[i];
            else {phi[i*pri[j]] = phi[i]*pri[j], mu[i*pri[j]] = 0; break;}
        }
    }
}
int main() {
    read(n), read(m), init();
    for (int x; m; m--)
        read(x), puts(NotPri[x] ? "No" : "Yes");
    return 0;
}

Trigeminal Search

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
double s, t;
double a[14];
double calc(double x) {
    double tot = 0, tmp = 1;
    for (int i = 0; i <= n; i++) {
        tot += tmp*a[i];
        tmp *= x;
    }
    return tot;
}
void f(double l, double r) {
    if (abs(r-l) <= 0.000001) {
        printf("%.5f", l);
        return;
    }
    double ml = (2*l+r)/3, mr = (l+2*r)/3;
    if (calc(ml) > calc(mr)) {
        f(l, mr);
    } else {
        f(ml, r);
    }
}
int main() {
    cin >> n >> s >> t;
    for (int i = n; i >= 0; i--) {
        cin >> a[i];
    }
    f(s, t);
    return 0;
}

Fast Fourier Transformation

#include <bits/stdc++.h>
#define MAX_N 1000000
using namespace std;
typedef double dnt;
const dnt Pi = acos(-1);
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct Complex {dnt r, i;} a[(MAX_N<<2)+5], b[(MAX_N<<2)+5], c[(MAX_N<<2)+5];
Complex operator + (Complex x, Complex y) {return (Complex){x.r+y.r, x.i+y.i};}
Complex operator - (Complex x, Complex y) {return (Complex){x.r-y.r, x.i-y.i};}
Complex operator * (Complex x, Complex y) {return (Complex){x.r*y.r-x.i*y.i, x.r*y.i+x.i*y.r};}
void Rader(Complex *s, int l) {
    for (int i = 1, j = l/2, k; i < l-1; i++) {
        if (i < j) swap(s[i], s[j]);	k = l/2;
        while (j >= k) j -= k, k >>= 1;	j += k;
    }
}
void FFT(Complex *s, int l, int f) {
    Rader(s, l);	Complex wn, w;
    for (int i = 2; i <= l; i <<= 1) {
        wn = (Complex){cos(2*Pi/i), f*sin(2*Pi/i)};
        for (int j = 0; j < l; j += i) {
            w = (Complex){1, 0};
            for (int k = j; k < j+i/2; k++, w = w*wn) {
                Complex x = s[k], y = w*s[k+i/2];
                s[k] = x+y, s[k+i/2] = x-y;
            }
        }
    }
    if (f == -1) for (int i = 0; i <= l; i++) s[i].r /= l;
}
int main() {
    int n, m;	read(n), read(m);
    for (int i = 0, x; i <= n; i++) read(x), a[i].r = x;
    for (int i = 0, x; i <= m; i++) read(x), b[i].r = x;
    int l;	for (l = 1; l <= n+m; l <<= 1) ;	FFT(a, l, 1), FFT(b, l, 1);
    for (int i = 0; i <= l; i++) c[i] = a[i]*b[i];	FFT(c, l, -1);
    for (int i = 0; i <= n+m; i++) printf("%d ", (int)(c[i].r+0.5));
    return 0;
}

Data Structure

Heap

#include <iostream>
using namespace std;
int n, heap[1000000+5], size = 0;
void insert(int x) {
    size++;
    heap[size] = x;
    int current = size;
    int father = current/2;
    while (father > 0 && heap[father] > heap[current]) {
        swap(heap[father], heap[current]);
        current = father;
        father = current/2;
    }
}
void pop() {
    heap[1] = heap[size];
    size--;
    int current = 1;
    int child = current*2;
    if (child < size && heap[child] > heap[child+1])    child++;
    while (child <= size && heap[current] > heap[child]) {
        swap(heap[current], heap[child]);
        current = child;
        child = 2*current;
        if (child < size && heap[child] > heap[child+1])    child++;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int f;
        cin >> f;
        if (f == 1) {
            int x;
            cin >> x;
            insert(x);
        } else if (f == 2) {
            cout << heap[1] << endl;
        } else {
            pop();
        }
    }
    return 0;
}

Mergeable Heap

#include <iostream>
#include <cstdio>
#define MAX_N 100000
using namespace std;
struct node {int val, dis, ls, rs;} heap[MAX_N+5];
int n, m, fa[MAX_N+5];
int getf(int x) {return fa[x] == x ? fa[x] : getf(fa[x]);}
int merge(int a, int b) {
    if (!a || !b)	return a^b;
    if (heap[a].val > heap[b].val || (heap[a].val == heap[b].val && a > b))	swap(a, b);
    heap[a].rs = merge(heap[a].rs, b), fa[heap[a].rs] = a;
    if (heap[heap[a].rs].dis > heap[heap[a].ls].dis)	swap(heap[a].ls, heap[a].rs);
    heap[a].dis = heap[a].rs == 0 ? 0 : heap[heap[a].rs].dis+1;	return a;
}
int pop(int a) {
    int l = heap[a].ls, r = heap[a].rs;
    heap[a].ls = heap[a].rs = heap[a].val = 0, fa[l] = l, fa[r] = r;
    return merge(l, r);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	scanf("%d", &heap[i].val), fa[i] = i;
    while (m--) {
        int opt;	scanf("%d", &opt);
        if (opt == 1) {
            int x, y;	scanf("%d%d", &x, &y), x = getf(x), y = getf(y);
            if (heap[x].val && heap[y].val && x != y)	merge(x, y);
        }
        if (opt == 2) {
            int x;	scanf("%d", &x), x = getf(x);
            if (!heap[x].val)	printf("-1\n");
            else	printf("%d\n", heap[x].val), pop(x);
        }
    }
    return 0;
}

Binary Indexed Tree

1

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 500000
using namespace std;
int n, m;
int tree[MAX_N+5];
int lowbit(int x) {
    return x&(-x);
}
void modify(int pos, int x) {
    while (pos <= n) {
        tree[pos] += x;
        pos += lowbit(pos);
    }
}
long long query(int t) {
    long long tot = 0;
    while (t > 0) {
        tot += tree[t];
        t -= lowbit(t);
    }
    return tot;
}
int main() {
    memset(tree, 0, sizeof(tree));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        modify(i, tmp);
    }
    for (int i = 0; i < m; i++) {
        int f, a, b;
        cin >> f >> a >> b;
        if (f == 1) {
            modify(a, b);
        } else {
            cout << query(b)-query(a-1) << endl;
        }
    }
    return 0;
}

2

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 500000
using namespace std;
int n, m;
int tree[MAX_N+5];
int lowbit(int x) {
    return x&(-x);
}
void modify(int pos, int x) {
    while (pos <= n) {
        tree[pos] += x;
        pos += lowbit(pos);
    }
}
long long query(int pos) {
    long long tot = 0;
    while (pos > 0) {
        tot += tree[pos];
        pos -= lowbit(pos);
    }
    return tot;
}
int main() {
    memset(tree, 0, sizeof(tree));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        modify(i, x);
        modify(i+1, -x);
    }
    for (int i = 0; i < m; i++) {
        int f;
        cin >> f;
        if (f == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            modify(l, x);
            modify(r+1, -x);
        } else {
            int x;
            cin >> x;
            cout << query(x) << endl;
        }
    }
    return 0;
}

Segment Tree

1

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100000
using namespace std;
int n, k;
long long tree[MAX_N*4+50], tag[MAX_N*4+50];
void updata(int v) {
    tree[v] = tree[v*2]+tree[v*2+1];
}
void downtag(int v, int s, int t) {
    tag[v*2] += tag[v];
    tag[v*2+1] += tag[v];
    int m = (s+t)/2;
    tree[v*2] += tag[v]*(m-s+1);
    tree[v*2+1] += tag[v]*(t-m);
    tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        tree[v] += x*(t-s+1);
        tag[v] += x;
        return;
    }
    int m = (s+t)/2;
    downtag(v, s, t);
    if (l <= m) {
        modify(v*2, s, m, l, r, x);
    }
    if (r >= m+1) {
        modify(v*2+1, m+1, t, l, r, x);
    }
    updata(v);
}
void build(int v, int s, int t) {
    if (s == t) {
        cin >> tree[v];
        return;
    }
    int m = (s+t)/2;
    build(v*2, s, m);
    build(v*2+1, m+1, t);
    updata(v);
}
long long query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) {
        return tree[v];
    }
    int m = (s+t)/2;
    downtag(v, s, t);
    long long ret = 0;
    if (l <= m) {
        ret += query(v*2, s, m, l, r);
    }
    if (r >= m+1) {
        ret += query(v*2+1, m+1, t, l, r);
    }
    updata(v);
    return ret;
}
int main() {
    cin >> n >> k;
    build(1, 1, n);
    for (int i = 0; i < k; i++) {
        int f, l, r, x;
        cin >> f;
        if (f == 1) {
            cin >> l >> r >> x;
            modify(1, 1, n, l, r, x);
        } else {
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << endl;
        }
    }
    return 0;
}

2

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100000
#define ll long long
using namespace std;
int n, m;
ll p;
ll tree[MAX_N*4+5], mul[MAX_N*4+5], add[MAX_N*4+5];
void updata(int v) {
    tree[v] = (tree[v*2]+tree[v*2+1])%p;
}
void downtag(int v, int s, int t, int mid) {
    if (mul[v] == 1 && add[v] == 0)	return;
    mul[v*2] = mul[v*2]*mul[v]%p;
    add[v*2] = (add[v*2]*mul[v]%p+add[v])%p;
    tree[v*2] = (tree[v*2]*mul[v]%p+add[v]*(ll)(mid-s+1)%p)%p;
    mul[v*2+1] = mul[v*2+1]*mul[v]%p;
    add[v*2+1] = (add[v*2+1]*mul[v]%p+add[v])%p;
    tree[v*2+1] = (tree[v*2+1]*mul[v]%p+add[v]*(ll)(t-mid)%p)%p;
    mul[v] = 1;
    add[v] = 0;
    return;
}
void create(int v, int s, int t) {
    mul[v] = 1;
    add[v] = 0;
    if (s == t) {
        cin >> tree[v];
        tree[v] %= p;
        return;
    }
    int mid = (s+t)/2;
    create(v*2, s, mid);
    create(v*2+1, mid+1, t);
    updata(v);
}
void modify1(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        add[v] = (add[v]+(ll)x)%p;
        tree[v] = (tree[v]+(ll)x*(ll)(t-s+1)%p)%p;
        return;
    }
    int mid = (s+t)/2;
    downtag(v, s, t, mid);
    if (l <= mid) {
        modify1(v*2, s, mid, l, r, x);
    }
    if (r >= mid+1) {
        modify1(v*2+1, mid+1, t, l, r, x);
    }
    updata(v);
}
void modify2(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        mul[v] = mul[v]*(ll)x%p;
        add[v] = add[v]*(ll)x%p;
        tree[v] = tree[v]*(ll)x%p;
        return; 
    }
    int mid = (s+t)/2;
    downtag(v, s, t, mid);
    if (l <= mid) {
        modify2(v*2, s, mid, l, r, x);
    }
    if (r >= mid+1) {
        modify2(v*2+1, mid+1, t, l, r, x);
    }
    updata(v);
}
ll query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) {
        return tree[v];
    }
    int mid = (s+t)/2;
    ll ret = 0;
    downtag(v, s, t, mid);
    if (l <= mid) {
        ret = (ret+query(v*2, s, mid, l, r))%p;
    }
    if (r >= mid+1) {
        ret = (ret+query(v*2+1, mid+1, t, l, r))%p;
    }
    updata(v);
    return ret;
}
int main() {
    cin >> n >> m >> p;
    create(1, 1, n);
    for (int i = 0; i < m; i++) {
        int f;
        cin >> f;
        if (f == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            modify2(1, 1, n, l, r, x%p);
        } else if (f == 2) {
            int l, r, x;
            cin >> l >> r >> x;
            modify1(1, 1, n, l, r, x%p);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << endl;
        }
    }
    return 0;
}

Sparse Table

#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX_N 100000
using namespace std;
int n, m, num[MAX_N+5], mx[MAX_N+5][20];
void setTable() {
    for (int i = 1; i <= n; i++)	mx[i][0] = num[i];
    for (int j = 1; (1<<j) <= n; j++)
        for (int i = 1; i+(1<<j)-1 <= n; i++)
            mx[i][j] = max(mx[i][j-1], mx[i+(1<<j-1)][j-1]);
}
int query(int l, int r) {
    int range = (int)(log(r-l+1)/log(2));
    return max(mx[l][range], mx[r-(1<<range)+1][range]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	scanf("%d", &num[i]);
    setTable();
    while (m--) {
        int l, r;	scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }
    return 0;
}

Chairman Tree

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 200000
using namespace std;
int n, m, num[MAX_N+5], hash[MAX_N+5], tot, root[MAX_N+5], cnt;
struct pre {int id, val;} p[MAX_N+5];
bool cmp (const pre &a, const pre &b) {return a.val < b.val;}
struct node {int ls, rs, val;} tr[MAX_N*50];
void updata(int v) {tr[v].val = tr[tr[v].ls].val+tr[tr[v].rs].val;}
void build(int v, int s, int t) {
    if (s == t)	return;	int mid = s+t>>1;
    tr[v].ls = ++cnt, tr[v].rs = ++cnt;
    build(tr[v].ls, s, mid), build(tr[v].rs, mid+1, t);
}
void modify(int v, int o, int s, int t, int x) {
    tr[v] = tr[o];	if (s == t) {tr[v].val++;	return;}
    int mid = s+t>>1;
    if (x <= mid)	modify(tr[v].ls = ++cnt, tr[o].ls, s, mid, x);
    else	modify(tr[v].rs = ++cnt, tr[o].rs, mid+1, t, x);
    updata(v);
}
int query(int v1, int v2, int s, int t, int k) {
    if (s == t)	return s;
    int mid = s+t>>1, tmp = tr[tr[v2].ls].val-tr[tr[v1].ls].val;
    if (k <= tmp)	return query(tr[v1].ls, tr[v2].ls, s, mid, k);
    else	return query(tr[v1].rs, tr[v2].rs, mid+1, t, k-tmp);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	p[i].id = i, scanf("%d", &p[i].val);
    sort(p+1, p+n+1, cmp);
    for (int i = 1; i <= n; i++) {if (p[i].val != p[i-1].val || i == 1)	hash[++tot] = p[i].val;	num[p[i].id] = tot;}
    root[0] = ++cnt, build(root[0], 1, tot);
    for (int i = 1; i <= n; i++)	root[i] = ++cnt, modify(root[i], root[i-1], 1, tot, num[i]);
    while (m--) {
        int l, r, k;	scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", hash[query(root[l-1], root[r], 1, tot, k)]);
    }
    return 0;
}

Treap

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MAX_N 100000
using namespace std;
struct TNode {
    TNode* s[2];
    int val, k, size;
    TNode() {}
    TNode(int _val, TNode* _s) {val = _val, s[0] = s[1] = _s, k = rand(), size = 1;}
    void updata() {size = s[0]->size+s[1]->size+1;}
} nil, tr[MAX_N+5], *null, *root, *cnt;
typedef TNode* P_TNode;
void init() {
    srand(19260817);
    nil = TNode(0, NULL), null = &nil;
    null->s[0] = null->s[1] = null, null->size = 0;
    cnt = tr, root = null;
}
P_TNode newnode(int val) {
    *cnt = TNode(val, null);
    return cnt++;
}
P_TNode merge(P_TNode a, P_TNode b) {
    if (a == null)    return b;
    if (b == null)    return a;
    if (a->k > b->k) {a->s[1] = merge(a->s[1], b), a->updata(); return a;}
    if (a->k <= b->k) {b->s[0] = merge(a, b->s[0]), b->updata(); return b;}
}
void split(P_TNode v, int val, P_TNode &ls, P_TNode &rs) {
    if (v == null) {ls = rs = null; return;}
    if (val < v->val) {rs = v; split(rs->s[0], val, ls, rs->s[0]);}
    if (val >= v->val) {ls = v;    split(ls->s[1], val, ls->s[1], rs);}
    v->updata();
}
void insert(int val) {
    P_TNode ls, rs;
    split(root, val, ls, rs);
    root = merge(merge(ls, newnode(val)), rs);
}
void remove(int val) {
    P_TNode ls, mids, rs;
    split(root, val-1, ls, rs);
    split(rs, val, mids, rs);
    root = merge(ls, merge(merge(mids->s[0], mids->s[1]), rs));
}
int get_rank(int val) {
    P_TNode ls, rs;
    split(root, val-1, ls, rs);
    int ret = ls->size+1;
    root = merge(ls, rs);
    return ret;
}
int get_kth(P_TNode v, int k) {
    if (k <= v->s[0]->size)    return get_kth(v->s[0], k);
    if (k > v->s[0]->size+1)    return get_kth(v->s[1], k-v->s[0]->size-1);
    return v->val;
}
int get_nearest(P_TNode v, int sn) {
    while (v->s[sn] != null)    v = v->s[sn];
    return v->val;
}
int predecessor(int val) {
    P_TNode ls, rs;
    split(root, val-1, ls, rs);
    int ret = get_nearest(ls, 1);
    root = merge(ls, rs);
    return ret;
}
int successor(int val) {
    P_TNode ls, rs;
    split(root, val, ls, rs);
    int ret = get_nearest(rs, 0);
    root = merge(ls, rs);
    return ret;
}
int main() {
    init();
    int n, opt, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &opt, &x);
        if (opt == 1)    insert(x);
        if (opt == 2)    remove(x);
        if (opt == 3)    printf("%d\n", get_rank(x));
        if (opt == 4)    printf("%d\n", get_kth(root, x));
        if (opt == 5)    printf("%d\n", predecessor(x));
        if (opt == 6)    printf("%d\n", successor(x));
    }
    return 0;
}

Splay

Normal

#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define flag (cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;	int val, w, sz;
    void updata() {sz = w+(s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0);}
};
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = _val, v->w = v->sz = 1;
        return v;
    }
    SplayTree() {
        rt = newnode(-INF), rt->s[1] = newnode(INF);
        rt->s[1]->fa = rt, rt->updata();
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* predecessor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val > cur->val])
            if (cur->val < _val) cpy = cur;
        return cpy;
    }
    SplayNode* successor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val >= cur->val])
            if (cur->val > _val) cpy = cur;
        return cpy;
    }
    void insert(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) suc->s[0]->w++, suc->s[0]->sz++;
        else suc->s[0] = newnode(_val), suc->s[0]->fa = suc;
        suc->updata(), rt->updata();
    }
    void remove(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        suc->s[0]->w--, suc->s[0]->sz--;
        if (!suc->s[0]->w) suc->s[0] = NULL;
        suc->updata(), rt->updata();
    }
    int get_rank(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc == NULL) return rt->sz;
        return rt->sz-suc->sz;
    }
    SplayNode* get_kth(SplayNode* v, int k) {
        int lsz = v->s[0] ? v->s[0]->sz : 0;
        if (k <= lsz) return get_kth(v->s[0], k);
        if (k > lsz+v->w) return get_kth(v->s[1], k-lsz-v->w);
        return v;
    }
} BBST;
int main() {
    int n, opt, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &opt, &x);
        if (opt == 1)	BBST.insert(x);
        if (opt == 2)	BBST.remove(x);
        if (opt == 3)	printf("%d\n", BBST.get_rank(x));
        if (opt == 4)	printf("%d\n", BBST.get_kth(BBST.rt, x+1)->val);
        if (opt == 5)	printf("%d\n", BBST.predecessor(x)->val);
        if (opt == 6)	printf("%d\n", BBST.successor(x)->val);
    }
    return 0;
}

Reverse

#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define flag (cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;
    int val, w, sz;	bool rev;
    void updata() {sz = w+(s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0);}
    void downtag() {
        if (!rev) return;	rev = false, swap(s[0], s[1]);
        if (s[0]) s[0]->rev ^= 1;	if (s[1]) s[1]->rev ^= 1;
    }
};
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = _val, v->sz = v->w = 1;
        v->rev = false;	return v;
    }
    SplayTree(int n) {
        rt = newnode(-INF), rt->s[1] = newnode(INF);
        rt->s[1]->fa = rt, rt->updata();
        for (int i = 1; i <= n; i++) insert(i);
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* predecessor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val > cur->val])
            if (cur->val < _val) cpy = cur;
        return cpy;
    }
    SplayNode* successor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val >= cur->val])
            if (cur->val > _val) cpy = cur;
        return cpy;
    }
    void insert(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) suc->s[0]->w++, suc->s[0]->sz++;
        else suc->s[0] = newnode(_val), suc->s[0]->fa = suc;
        suc->updata(), rt->updata();
    }
    void reverse(int l, int r) {
        SplayNode *nl = get_kth(rt, l), *nr = get_kth(rt, r+2);
        splay(nl, rt), splay(nr, rt->s[1]), nr->s[0]->rev ^= 1;
    }
    SplayNode* get_kth(SplayNode* v, int k) {
        v->downtag();
        int lsz = v->s[0] == NULL ? 0 : v->s[0]->sz;
        if (k <= lsz) return get_kth(v->s[0], k);
        if (k > lsz+v->w) return get_kth(v->s[1], k-lsz-v->w);
        return v;
    }
    void output(SplayNode* v) {
        if (v == NULL) return;	v->downtag(), output(v->s[0]);
        if (v->val != -INF && v->val != INF) printf("%d ", v->val);
        output(v->s[1]);
    }
};
int main() {
    int n, m;	scanf("%d%d", &n, &m);	SplayTree BBST(n);
    for (int i = 1, l, r; i <= m; i++)	scanf("%d%d", &l, &r), BBST.reverse(l, r);
    return BBST.output(BBST.rt), 0;
}

Range Tree

#include <bits/stdc++.h>
#define MAX_N 200000
#define INF 2147483647
#define mid ((s+t)>>1)
#define flag (cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
int n, m, c[MAX_N+5];
struct SplayNode {
    SplayNode *s[2], *fa;	int val, w, sz;
    void updata() {sz = w+(s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0);}
};
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = _val, v->w = v->sz = 1;
        return v;
    }
    SplayTree() {
        rt = newnode(-INF), rt->s[1] = newnode(INF);
        rt->s[1]->fa = rt, rt->updata();
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* predecessor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val > cur->val])
            if (cur->val < _val) cpy = cur;
        return cpy;
    }
    SplayNode* successor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val >= cur->val])
            if (cur->val > _val) cpy = cur;
        return cpy;
    }
    void insert(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) suc->s[0]->w++, suc->s[0]->sz++;
        else suc->s[0] = newnode(_val), suc->s[0]->fa = suc;
        suc->updata(), rt->updata();
    }
    void remove(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        suc->s[0]->w--, suc->s[0]->sz--;
        if (!suc->s[0]->w) suc->s[0] = NULL;
        suc->updata(), rt->updata();
    }
    int get_rank(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc == NULL) return rt->sz-1;
        return rt->sz-suc->sz-1;
    }
} tr[(MAX_N<<2)+5];
void ins(int v, int s, int t, int p, int x) {
    tr[v].insert(x);	if (s == t) return;
    if (p <= mid) ins(v<<1, s, mid, p, x);
    else ins(v<<1|1, mid+1, t, p, x);
}
void modify(int v, int s, int t, int p, int x, int o) {
    tr[v].remove(o), tr[v].insert(x);	if (s == t) return;
    if (p <= mid) modify(v<<1, s, mid, p, x, o);
    else modify(v<<1|1, mid+1, t, p, x, o);
}
int query(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) return tr[v].get_rank(x);	int ret = 0;
    if (l <= mid) ret += query(v<<1, s, mid, l, r, x);
    if (r >= mid+1) ret += query(v<<1|1, mid+1, t, l, r, x);
    return ret;
}
int get_ind(int l, int r, int k) {
    int s = 0, t = INF, ret = -1;
    while (s <= t)
        if (query(1, 1, n, l, r, mid) >= k) t = mid-1;
        else ret = mid, s = mid+1;
    return ret;
}
int get_pre(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) return tr[v].predecessor(x)->val;	int ret = -INF;
    if (l <= mid) ret = max(ret, get_pre(v<<1, s, mid, l, r, x));
    if (r >= mid+1) ret = max(ret, get_pre(v<<1|1, mid+1, t, l, r, x));
    return ret;
}
int get_suc(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) return tr[v].successor(x)->val;	int ret = INF;
    if (l <= mid) ret = min(ret, get_suc(v<<1, s, mid, l, r, x));
    if (r >= mid+1) ret = min(ret, get_suc(v<<1|1, mid+1, t, l, r, x));
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", c+i), ins(1, 1, n, i, c[i]);
    while (m--) {
        int opt, l, r, p, k, x;	scanf("%d", &opt);
        if (opt == 1) scanf("%d%d%d", &l, &r, &x), printf("%d\n", query(1, 1, n, l, r, x)+1);
        if (opt == 2) scanf("%d%d%d", &l, &r, &k), printf("%d\n", get_ind(l, r, k));
        if (opt == 3) scanf("%d%d", &p, &x), modify(1, 1, n, p, x, c[p]), c[p] = x;
        if (opt == 4) scanf("%d%d%d", &l, &r, &x), printf("%d\n", get_pre(1, 1, n, l, r, x));
        if (opt == 5) scanf("%d%d%d", &l, &r, &x), printf("%d\n", get_suc(1, 1, n, l, r, x));
    }
}

Tree Chain Division

#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 100000
using namespace std;
int n, m, r, p, ind;
vector <int> G[MAX_N+5];
int c[MAX_N+5];
int dep[MAX_N+5], fa[MAX_N+5], size[MAX_N+5], son[MAX_N+5];
int top[MAX_N+5], dfn[MAX_N+5], last[MAX_N+5];
int seg[(MAX_N<<2)+5], tag[(MAX_N<<2)+5];
void DFS1(int u) {
    size[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa[u])	continue;
        dep[v] = dep[u]+1;
        fa[v] = u;
        DFS1(v);
        size[u] += size[v];
        if (!son[u] || size[son[u]] < size[v])	son[u] = v;
    }
}
void DFS2(int u, int tp) {
    top[u] = tp, dfn[u] = ++ind;
    if (son[u])	DFS2(son[u], tp);
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa[u] || v == son[u])	continue;
        DFS2(v, v);
    }
    last[u] = ind;
}
void updata(int v) {seg[v] = (seg[v<<1]+seg[v<<1|1])%p;}
void downtag(int v, int s, int t) {
    if (!tag[v])	return;
    int mid = s+t>>1;
    seg[v<<1] = (seg[v<<1]+tag[v]*(mid-s+1))%p;
    seg[v<<1|1] = (seg[v<<1|1]+tag[v]*(t-mid))%p;
    tag[v<<1] = (tag[v<<1]+tag[v])%p;
    tag[v<<1|1] = (tag[v<<1|1]+tag[v])%p;
    tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {seg[v] = (seg[v]+x*(t-s+1))%p, tag[v] = (tag[v]+x)%p;	return;}
    downtag(v, s, t);
    int mid = s+t>>1;
    if (l <= mid)	modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1)	modify(v<<1|1, mid+1, t, l, r, x);
    updata(v);
}
int query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r)	return seg[v];
    downtag(v, s, t);
    int mid = s+t>>1, ret = 0;
    if (l <= mid)	ret = (ret+query(v<<1, s, mid, l, r))%p;
    if (r >= mid+1)	ret = (ret+query(v<<1|1, mid+1, t, l, r))%p;
    updata(v);
    return ret;
}
void solve1(int x, int y, int z) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])	swap(x, y);
        modify(1, 1, n, dfn[top[x]], dfn[x], z);
        x = fa[top[x]];
    }
    modify(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z);
}
int solve2(int x, int y) {
    int ret = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])	swap(x, y);
        ret = (ret+query(1, 1, n, dfn[top[x]], dfn[x]))%p;
        x = fa[top[x]];
    }
    ret = (ret+query(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])))%p;
    return ret;
}
void solve3(int x, int z) {modify(1, 1, n, dfn[x], last[x], z);}
int solve4(int x) {return query(1, 1, n, dfn[x], last[x]);}
int main() {
    scanf("%d%d%d%d", &n, &m, &r, &p);
    for (int i = 1; i <= n; i++)	scanf("%d", &c[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    DFS1(r);
    DFS2(r, r);
    for (int i = 1; i <= n; i++)	modify(1, 1, n, dfn[i], dfn[i], c[i]);
    while (m--) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            solve1(x, y, z);
        }
        if (opt == 2) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", solve2(x, y));
        }
        if (opt == 3) {
            int x, z;
            scanf("%d%d", &x, &z);
            solve3(x, z);
        }
        if (opt == 4) {
            int x;
            scanf("%d", &x);
            printf("%d\n", solve4(x));
        }
    }
    return 0;
}

Link-Cut Tree

#include <bits/stdc++.h>
#define MAX_N 300000
#define INF 0x7f7f7f7f
#define flag (!tar(cur->fa->fa)&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;	int val, sum;	bool rev;
    void updata() {sum = val^(s[0]?s[0]->sum:0)^(s[1]?s[1]->sum:0);}
    void downtag() {
        if (fa && (fa->s[0] == this || fa->s[1] == this)) fa->downtag();
        if (rev && s[0]) swap(s[0]->s[0], s[0]->s[1]), s[0]->rev ^= 1;
        if (rev && s[1]) swap(s[1]->s[0], s[1]->s[1]), s[1]->rev ^= 1;
        rev = false;
    }
} *tr[MAX_N+5];
struct LinkCutTree {
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = v->sum = _val, v->rev = 0;
        return v;
    }
    SplayNode* get_rt(SplayNode* v) {for (; v->fa; v = v->fa) ;	return v;}
    bool tar(SplayNode* v) {return (v&&v->fa==NULL)||(v&&v->fa->s[0]!=v&&v->fa->s[1]!=v);}
    LinkCutTree(int n) {for (int i=1,_val;i<=n;i++) scanf("%d", &_val), tr[i]=newnode(_val);}
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa && !tar(f)) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur) {
        cur->downtag();
        while (!tar(cur) && !tar(cur->fa)) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (!tar(cur) && tar(cur->fa))
            rotate(cur, cur->fa->s[0] == cur);
        cur->updata();
    }
    void access(SplayNode* cur) {
        for (SplayNode* cpy = NULL; cur; cpy = cur, cur = cur->fa)
            splay(cur), cur->s[1] = cpy, cur->updata();
    }
    void mroot(SplayNode* v) {
        access(v), splay(v);
        swap(v->s[0], v->s[1]), v->rev ^= 1;
    }
    void link(SplayNode* u, SplayNode* v) {
        if (get_rt(u) == get_rt(v)) return;
        mroot(u), u->fa = v;
    }
    void cut(SplayNode* u, SplayNode* v) {
        if (u == v || get_rt(u) != get_rt(v)) return;
        mroot(u), access(v), splay(v);
        if (v->s[0] == u) u->fa = v->s[0] = NULL, v->updata();
    }
    void modify(SplayNode* v, int _val) {
        splay(v), v->val = _val, v->updata();
    }
    int query(SplayNode* u, SplayNode* v) {
        mroot(u), access(v), splay(v);
        return v->sum;
    }
};
int main() {
    int n, m;	scanf("%d%d", &n, &m);
    LinkCutTree LCT(n);
    while (m--) {
        int opt, x, y;	scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0) printf("%d\n", LCT.query(tr[x], tr[y]));
        if (opt == 1) LCT.link(tr[x], tr[y]);
        if (opt == 2) LCT.cut(tr[x], tr[y]);
        if (opt == 3) LCT.modify(tr[x], y);
    }
    return 0;
}

String

Knuth-Morris-Pratt Algorithm

#include <iostream>
#include <cstdio>
#include <string>
#define MAX_M 1000
using namespace std;
int next[MAX_M];
void CalcNext(string& s) {
    int m = s.length();
    int begin = 1, matched = 0;
    while (begin+matched < m) {
        if (s[begin+matched] == s[matched]) {
            matched++;
            next[begin+matched-1] = matched;
        } else {
            if (matched == 0) {
                begin++;
            } else {
                begin += matched-next[matched-1];
                matched = next[matched-1];
            }
        }
    }
}
void KMP(string& T, string& P) {
    int n = T.length(), m = P.length();
    int begin = 0, matched = 0;
    while (begin <= n-m) {
        if (matched < m && T[begin+matched] == P[matched]) {
            matched++;
            if (matched == m) {
                cout << begin+1 << endl;
            }
        } else {
            if (matched == 0) {
                begin++;
            } else {
                begin += matched-next[matched-1];
                matched = next[matched-1];
            }
        }
    }
}
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    CalcNext(s2);
    KMP(s1, s2);
    for (int i = 0; i < s2.length(); i++) {
        cout << next[i] << " ";
    }
    return 0;
}

Manacher

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_L 11000000
using namespace std;
char s[MAX_L*2+5];
int f[MAX_L*2+5];
int manacher (char* s0) {
    int len = strlen(s0);
    for (int i = 0; i < len; i++)	s[i*2+1] = '#', s[i*2+2] = s0[i];
    s[len = len*2+1] = '#';
    int pos = 0, r = 0, ret = 0;
    for (int i = 1; i <= len; i++) {
        f[i] = (i < r) ? min(f[2*pos-i], r-i) : 1;
        while (i-f[i] >= 1 && i+f[i] <= len && s[i-f[i]] == s[i+f[i]])	f[i]++;
        if (i+f[i] > r)	pos = i, r = i+f[i];
        ret = max(ret, f[i]-1);
    }
    return ret;
}
int main() {
    char s0[MAX_L+5];	scanf("%s", s0);
    printf("%d\n", manacher(s0));
    return 0;
}

Aho-Corasick Automation

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define DICNUM 26
#define MAX_LETTER 10500
#define MAX_LENGTH 1000000
using namespace std;
char P[155][75], T[MAX_LENGTH+5];
int root = 1, cnt, trie[MAX_LETTER+5][DICNUM], fail[MAX_LETTER+5], end[MAX_LETTER+5], tot[155];
void init() {
    memset(P, 0, sizeof(P)), memset(T, 0, sizeof(T)), memset(tot, 0, sizeof(tot));
    for (int i = 1; i <= cnt; i++)	memset(trie[i], 0, sizeof(trie[i])), fail[i] = end[i] = 0;	cnt = 1;
}
void insert(int id, char s[]) {
    int cur = 1, len = strlen(s);
    for (int i = 0; i < len; cur = trie[cur][s[i++]-'a'])
        if (!trie[cur][s[i]-'a'])	trie[cur][s[i]-'a'] = ++cnt;
    end[cur] = id;
}
void SetFail() {
    queue <int> que;	que.push(root);
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = 0; i < DICNUM; i++)
            if (trie[u][i])	fail[trie[u][i]] = trie[fail[u]][i], que.push(trie[u][i]);
            else trie[u][i] = trie[fail[u]][i];
    }
}
void query() {
    int cur = root, index, len = strlen(T);
    for (int i = 0; i < len; i++) {
        index = T[i]-'a';
        while (!trie[cur][index])	cur = fail[cur];
        cur = trie[cur][index];
        for (int j = cur; j; j = fail[j])	tot[end[j]]++;
    }
}
int main() {
    int n;
    for (int i = 0; i < DICNUM; i++)	trie[0][i] = root;
    while (scanf("%d", &n) && n) {
        init();
        for (int i = 1; i <= n; i++)	scanf("%s", P[i]), insert(i, P[i]);
        SetFail(), scanf("%s", T), query();
        int ans = 0;
        for (int i = 1; i <= n; i++)	ans = max(ans, tot[i]);
        printf("%d\n", ans);
        for (int i = 1; i <= n; i++)	if (tot[i] == ans)	printf("%s\n", P[i]);
    }
    return 0;
}

Hash Table

#include <iostream>
#include <cstdio>
#include <string>
#define size 15000
using namespace std;
int n, cnt = 0;
string tmp;
string hash[size];
int calc(string& index) {
    int ret = 0;
    for (int i = 0; i < index.length(); i++) {
        ret = (ret*256+index[i]+128)%size;
    }
    return ret;
}
bool search(string& index, int& pos) {
    pos = calc(index);
    while (hash[pos] != "" && hash[pos] != index) {
        pos = (pos+1)%size;
    }
    if (hash[pos] == index) {
        return true;
    } else {
        return false;
    }
}
int insert(string& index) {
    int pos;
    if (search(index, pos)) {
        return 0;
    } else {
        hash[pos] = index;
        return 1;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        cnt += insert(tmp);
    }
    cout << cnt << endl;
    return 0;
}

Suffix Array

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 1000000
using namespace std;
int n;	char ch[MAX_N+5];
int s[MAX_N+5], sa[MAX_N+5], tx[MAX_N+5], ty[MAX_N+5], cnt[MAX_N+5], rank[MAX_N+5];
int trans(char c) {
    if (c >= '0' && c <= '9')	return c-'0'+1;
    if (c >= 'A' && c <= 'Z')	return c-'A'+11;
    if (c >= 'a' && c <= 'z')	return c-'a'+37;
}
void getSA() {
    int *x = tx, *y = ty;	int DICNUM = 63;
    for (int i = 1; i <= n; i++)	cnt[x[i] = s[i]]++;
    for (int i = 2; i <= DICNUM; i++)	cnt[i] += cnt[i-1];
    for (int i = n; i; i--)	sa[cnt[x[i]]--] = i;
    for (int h = 1; h <= n; h <<= 1) {
        int c = 0;
        for (int i = n-h+1; i <= n; i++)	y[++c] = i;
        for (int i = 1; i <= n; i++)	if (sa[i] > h)	y[++c] = sa[i]-h;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)	cnt[x[i]]++;
        for (int i = 2; i <= DICNUM; i++)	cnt[i] += cnt[i-1];
        for (int i = n; i; i--)	sa[cnt[x[y[i]]]--] = y[i];
        swap(x, y), c = 0, x[sa[1]] = ++c;
        for (int i = 2; i <= n; i++)	x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+h] == y[sa[i-1]+h]) ? c : ++c;
        DICNUM = c;	if (c == n)	break;
    }
}
int main() {
    scanf("%s", ch);	n = strlen(ch);
    for (int i = 0; i < n; i++)	s[i+1] = trans(ch[i]);
    getSA();
    printf("%d", sa[1]);	for (int i = 2; i <= n; i++)	printf(" %d", sa[i]);
    return 0;
}

Suffix Automaton

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 1000000
using namespace std;
typedef long long lnt;
struct node {int ch[26], par, len;} SAM[MAX_N*2+500];
int sz, root, last, cnt[MAX_N*2+500], dfn[MAX_N*2+500], f[MAX_N*2+500];
int newnode(int _len) {SAM[++sz].len = _len;	return sz;}
void init() {sz = 0, root = last = newnode(0);}
void extend(int c) {
    int p = last, np = newnode(SAM[p].len+1);	last = np, f[np] = 1;
    for (; p && !SAM[p].ch[c]; p = SAM[p].par)	SAM[p].ch[c] = np;
    if (!p)	SAM[np].par = root;
    else {
        int q = SAM[p].ch[c];
        if (SAM[q].len == SAM[p].len+1)	SAM[np].par = q;
        else {
            int nq = newnode(SAM[p].len+1);
            memcpy(SAM[nq].ch, SAM[q].ch, sizeof(SAM[q].ch));
            SAM[nq].par = SAM[q].par, SAM[q].par = SAM[np].par = nq;
            for (; p && SAM[p].ch[c] == q; p = SAM[p].par)	SAM[p].ch[c] = nq;
        }
    }
}
int main() {
    char s[MAX_N+5];	init(), scanf("%s", s);	int l = strlen(s);
    for (int i = 0; i < l; i++)	extend(s[i]-'a');
    for (int i = 1; i <= sz; i++)	cnt[SAM[i].len]++;
    for (int i = 1; i <= l; i++)	cnt[i] += cnt[i-1];
    for (int i = 1; i <= sz; i++)	dfn[cnt[SAM[i].len]--] = i;
    lnt ans = 0;
    for (int i = sz; i >= 1; i--) {
        int p = dfn[i];	f[SAM[p].par] += f[p];
        if (f[p] > 1)	ans = max(ans, (lnt)f[p]*SAM[p].len);
    }
    printf("%lld", ans);
    return 0;
}

BZOJ1787【AHOI2008】Meet紧急集合

发表于 2017-09-27

字数统计: 894 | 阅读时长 ≈ 4

Problem

【AHOI2008】Meet 紧急集合

Description

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有个等待点，有条道路连接着它们，每条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一点到另一点要花费一个游戏币。参加游戏的三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对讲机（用于和同组的成员联系）。当集合号吹响后，每个成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在个等待点中确定一个集合点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。
小可可和他的朋友邀请你一起参加这个游戏，有你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

Input

第一行两个正整数和（，），之间用一个空格隔开。分别表示等待点的个数（等待点也从到进行编号）和获奖所需完成的集合次数。
随后有行，每行两个正整数和，之间用空格隔开，表示编号为和编号为的等待点之间有一条路。
接着还有行，每行用三个正整数表示某次集合前小可可、小可可的朋友以及你所在的等待点的编号。

Output

一共有行，每行两个数和，用一个空格隔开。其中第行表示第次集合点选择在编号为的等待点，集合总共的花费是个游戏币。

阅读全文 »

BZOJ2038 小Z的袜子 <莫队>

发表于 2017-09-25

字数统计: 954 | 阅读时长 ≈ 5

Problem

小Z的袜子

Description

作为一个生活散漫的人，小每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小把这只袜子从到编号，然后从编号到(尽管小并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬)。
你的任务便是告诉小，他有多大的概率抽到两只颜色相同的袜子。当然，小希望这个概率尽量高，所以他可能会询问多个以方便自己选择。

Input

输入文件第一行包含两个正整数和。为袜子的数量，为小所提的询问的数量。接下来一行包含个正整数，其中表示第只袜子的颜色，相同的颜色用相同的数字表示。再接下来行，每行两个正整数，表示一个询问。

Output

包含行，对于每个询问在一行中输出分数表示从该询问的区间中随机抽出两只袜子颜色相同的概率。若该概率为则输出，否则输出的必须为最简分数。

阅读全文 »

UVa12345 Dynamic len(set(a[L:R])) <带修莫队>

发表于 2017-09-25

字数统计: 882 | 阅读时长 ≈ 5

Problem

Dynamic len(set(a[L:R]))

Description

In python, we can use len(start(a[L:R])) to calculate the number of distinct values of elements .
Tere are some interactive examples that may help you understand how it is done. Remember that the indices of python lists start from .

>>>
a=[1,2,1,3,2,1,4]
>>> print a[1:6]
[2, 1, 3, 2, 1]
>>> print set(a[1:6])
set([1, 2, 3])
>>> print
len(set(a[1:6]))
3
>>> a[3]=2
>>> print
len(set(a[1:6]))
2
>>> print len(set(a[3:5]))
1

Your task is to simulate this process.

Input

There will be only one test case. The first line contains two integers and .
The next line contains the original list.
All the integers are between and (inclusive). The next m lines contain the statements
that you need to execute.
A line formatted as ‘ ’ means , and a line formatted as ‘
’ means .
It is guaranteed that the statements will not cause error.

Output

Print the simulated result, one line for each query.

阅读全文 »

BZOJ1103【POI2007】大都市meg <树上差分+树状数组>

发表于 2017-09-25

字数统计: 907 | 阅读时长 ≈ 4

Problem

【POI2007】大都市meg

Description

经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员也开始骑着摩托车传递邮件了。不过，她经常回忆起以前在乡间漫步的情景。昔日，乡下有依次编号为的个小村庄，某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄（即比特堡）。并且，对于每个村庄，它到比特堡的路径恰好只经过编号比它的编号小的村庄。另外，对于所有道路而言，它们都不在除村庄以外的其他地点相遇。在这个未开化的地方，从来没有过高架桥和地下铁道。随着时间的推移，越来越多的土路被改造成了公路。至今，还清晰地记得最后一条土路被改造为公路的情景。现在，这里已经没有土路了——所有的路都成为了公路，而昔日的村庄已经变成了一个大都市。想起了在改造期间她送信的经历。她从比特堡出发，需要去某个村庄，并且在两次送信经历的间隔期间,有某些土路被改造成了公路.现在需要你的帮助：计算出每次送信她需要走过的土路数目。（对于公路，她可以骑摩托车；而对于土路，她就只好推车了。）