A+B problem 解法100种 - 洛谷保存站

### 算法一、DFS一号
```cpp
#include <bits/stdc++.h>
using namespace std;
int n = 2, a[5], s;
int dfs(int x, int sum) {
    if (x > n) return sum;
    int i = dfs(x + 1, sum);
    int j = dfs(x + 1, sum + a[x]);
    if (i == s) return i;
    if (j == s) return j;
    return -1;
}
int main() {
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]), s += a[i];
    cout << dfs(1, 0) << endl;
    return 0;
}
```

### 算法二、DFS二号
```cpp
#include <bits/stdc++.h>
using namespace std;
int a, b;
int dfs(int x) {
    if (x <= 5) return x;
    return dfs(x / 2) + dfs(x - x / 2);
} 
int main() {
    scanf("%d%d", &a, &b);
    printf("%d\n", dfs(a) + dfs(b));
    return 0;
}
```

### 算法三、BFS
```cpp
#include <bits/stdc++.h>
using namespace std;
int n = 2, a[5], s;
queue<int> q;
void bfs() {
    q.push(0);
    int c = 0;
    while (q.size()) {
        c++;
        int f = q.front(); q.pop();
        if (f == s) {printf("%d\n", f); exit(0);}
        q.push(f + a[c]);
        q.push(f);
    }
}
int main() {
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]), s += a[i];
    bfs();
    return 0;
}

```
### 算法四、直接算咯
```cpp
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
} 
```

### 算法五、二分
```cpp
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
    scanf("%d%d", &a, &b);
    int l = 0, r = 200000000;
    while (l < r) {
        int mid = l + r >> 1;
        if (mid == a + b) {printf("%d\n", mid); return 0;}
        if (mid <  a + b) l = mid + 1;
        if (mid >  a + b) r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

```
### 算法六、稍微有点暴力的枚举
```cpp
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
    scanf("%d%d", &a, &b);
    for (int i = 0;i <= 200000000; i++) if (a + b == i) {printf("%d\n", i); break;}
    return 0;
} 
```

### 算法七、最短路之dijkstra
```cpp
#include <bits/stdc++.h>
using namespace std;
int w[5][5], d[5], v[5];
int n = 3;
void dijkstra() {
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    d[1] = 0;
    for (int i = 1;i < n; i++) {
        int x = 0;
        for (int j = 1;j <= n; j++)
            if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
        v[x] = 1;
        for (int y = 1;y <= n; y++)
            d[y] = min(d[y], d[x] + w[x][y]);
    }
}
int main() {
    int a, b; scanf("%d%d", &a, &b);
    memset(w, 0x3f, sizeof w);
    w[1][2] = a; w[2][3] = b;
    dijkstra();
    printf("%d\n", d[3]);
    return 0;
}

```
### 算法八、最短路之SPFA
```cpp
#include <bits/stdc++.h>
using namespace std;
int a, b, n = 3;
int w[5][5], d[5], v[5];
queue<int> q;
void spfa() {
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    d[1] = 0, v[1] = 1;
    q.push(1);
    while (q.size()) {
        int x = q.front(); q.pop();
        v[x] = 0;
        for (int i = 1;i <= n; i++) {
//          if (w[x][i] == 0x3f) continue;
            if (d[i] > d[x] + w[x][i]) {
                d[i] = d[x] + w[x][i];
                if (!v[i]) q.push(i), v[i] = 1;
            }
        }
    }
}
int main() {
    scanf("%d%d", &a, &b);
    memset(w, 0x3f, sizeof w);
    w[1][2] = a; w[2][3] = b;
    spfa();
    printf("%d\n", d[3]);
    return 0;
}

```
### 算法九、最短路之Floyd
```cpp
#include <bits/stdc++.h>
using namespace std;
int d[5][5], n = 3;
int main() {
    int a, b; scanf("%d%d", &a, &b);
    memset(d, 0x3f, sizeof d);
    d[1][2] = a; d[2][3] = b;
    for (int k = 1;k <= n; k++)
        for (int i = 1;i <= n; i++)
            for (int j = 1;j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    printf("%d\n", d[1][3]);
    return 0;
}
```

### 算法十、高精
```cpp
#include<bits/stdc++.h>
using namespace std;
string a0, b0;
int a[1005], b[1005];
int main(){
    cin >> a0 >> b0;
    int l1 = a0.size(), l2 = b0.size();
    for (int i = 0;i < l1; i++) a[l1 - i] = a0[i] - 48;
    for (int i = 0;i < l2; i++) b[l2 - i] = b0[i] - 48;
    l1 = max(l1, l2);
    for (int i = 1;i <= l1; i++) {
        a[i] += b[i];
        if (a[i] > 9) a[i + 1] += 1, a[i] %= 10;
    }
    if (a[max(l1, l2) + 1] > 0) l1++;
    for (int i = l1;i >= 1; i--) printf("%d", a[i]);
    return 0;
}

```
### 算法十一、最小生成树之kruskal
```cpp
#include <bits/stdc++.h>
using namespace std;
struct rec {
    int x, y, z;
} edge[5];

int fa[5], m = 2, ans = 0;

int get(int x) {
    if (x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}
int cmp(rec a, rec b) { return a.z < b.z; }

int main() {
    int a, b; scanf("%d%d", &a, &b);
    edge[1] = (rec){1, 2, a};
    edge[2] = (rec){2, 3, b};
    for (int i = 1;i <= m + 1; i++) fa[i] = i;
    sort(edge + 1, edge + 1 + m, cmp);
    for (int i = 1;i <= m; i++) {
        int x = get(edge[i].x);
        int y = get(edge[i].y);
        if (x == y) continue;
        fa[x] = y;
        ans += edge[i].z;
    }
    printf("%d\n", ans);
    return 0;
}

```
### 算法十二、最小生成树之prim
```cpp
#include <bits/stdc++.h>
using namespace std;
int w[5][5], d[5], n = 3, ans, v[5];

void prim() {
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    d[1] = 0;
    for (int i = 1;i < n; i++) {
        int x = 0;
        for (int j = 1;j <= n; j++)
            if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
        v[x] = 1;
        for (int y = 1;y <= n; y++)
            if (!v[y]) d[y] = min(d[y], w[x][y]);
    }
}
int main() {
    int a, b; scanf("%d%d", &a, &b);
    memset(w, 0x3f, sizeof w);
    w[1][2] = a; w[2][3] = b;
    prim();
    int ans = 0;
    for (int i = 2;i <= n; i++) ans += d[i];
    printf("%d\n", ans);
    return 0;
}

```
### 算法十三、前缀和
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[5], s[5];
int main() {
    for (int i = 1;i <= 2; i++) scanf("%d", &a[i]), s[i] += a[i] + s[i - 1];
    printf("%d\n", s[2]);
    return 0;
}

```
### 算法十四、后缀和
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[5], s[5];
int main() {
    for (int i = 2;i >= 1; i--) scanf("%d", &a[i]), s[i] += a[i] + s[i + 1];
    printf("%d\n", s[1]);
    return 0;
}
```
### 算法十五、位运算
```cpp
#include <bits/stdc++.h>
using namespace std;
int add(int a, int b) {
    if (b == 0) return a;
    return add(a ^ b, (a & b) << 1);
}
int main() {
    int a, b; scanf("%d%d", &a, &b);
    printf("%d\n", add(a, b));
    return 0;
}
```
### 算法十六、树的直径——BFS
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int head[maxn * 2],edge[maxn * 2],Next[maxn * 2],ver[maxn * 2];
int vis[maxn], dist[maxn];
int n = 3, p, q, d;
int tot = 0;
int maxd = 0;
void add(int u,int v,int w) {
    ver[ ++ tot] = v,edge[tot] = w;
    Next[tot] = head[u],head[u] = tot;
}
int BFS(int u) {
    queue<int>Q;
    while(!Q.empty()) Q.pop();
    memset(vis, 0, sizeof vis);
    memset(dist, 0, sizeof dist);  
    Q.push(u);
    int x, max_num = 0;
    while(!Q.empty()) {
        x = Q.front();
        Q.pop();
        vis[x] = 1;
        for(int i = head[x]; i ; i = Next[i]) {
            int y = ver[i];
            if(vis[y]) continue;
            vis[y] = 1;
            dist[y] = dist[x] + edge[i];
            if(dist[y] > maxd) {
                maxd = dist[y];
                max_num = y;
            }
            Q.push(y);
        }
    }
    return max_num;
}
int main(void) {
    int a, b; scanf("%d%d", &a, &b);
    add(1, 2, a); add(2, 1, a);
    add(2, 3, b); add(3, 2, b);
    BFS(BFS(1));
    int ans = 0;
    for (int i = 1;i <= n; i++) ans = max(ans, dist[i]);
    printf("%d\n", ans);
    return 0;
}
```
### 算法十七、树的直径——DFS
```cpp
#include<bits/stdc++.h>
#define maxn 100000
using namespace std;
struct node {
    int u, v, w, nex;
} edge[2 * maxn + 10];
int n = 3, d[maxn + 10], head[maxn + 10], f_num, cnt = 0, ans;
inline void add(int x,int y,int z) {
    edge[++cnt].u = x;
    edge[cnt].v = y;
    edge[cnt].w = z;
    edge[cnt].nex = head[x];
    head[x] = cnt;
}
inline void dfs(int x, int fa) {
    if(ans < d[x]) {
        ans = d[x];
        f_num = x;
    }
    for (int i = head[x]; i != -1; i = edge[i].nex) {
        int j = edge[i].v;
        if (j == fa)continue;
        d[j] = d[x] + edge[i].w;    
        dfs(j, x);
    }
}
int main() {
    memset(head, -1, sizeof(head));
    int a, b; scanf("%d%d", &a, &b);
    add(1, 2, a); add(2, 1, a);
    add(2, 3, b); add(3, 2, b);
    dfs(1, 0);
    ans = 0;
    d[f_num] = 0;
    dfs(f_num, 0);
    for (int i = 1;i <= n; i++) ans = max(ans, d[i]);
    printf("%d", ans);
    return 0;
}
```
### 算法十八、树的直径——树形DP
```cpp
#include <bits/stdc++.h>
using namespace std;
int f[5], n = 3, cnt, h[5], ans, dis[5];
struct edge {
    int to, next, vi;
} e[5];
void add(int u, int v, int w) {
    e[cnt].to= v;
    e[cnt].vi = w;
    e[cnt].next = h[u];
    h[u] = cnt++;
}
void dp(int u, int fa) {
    for (int i = h[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == fa) continue;
        dp(v, u);
        ans = max(ans, dis[v] + dis[u] + e[i].vi);
        dis[u] = max(dis[u], dis[v] + e[i].vi);
    }
}
int main() {
    memset(h, -1, sizeof h);
    int a, b; scanf("%d%d", &a, &b);
    add(1, 2, a); add(2, 1, a);
    add(2, 3, b); add(3, 2, b);
    dp(1, 0);
    printf("%d\n", ans);
    return 0;
}
```
### 算法十九、网络流
```cpp
#include<bits/stdc++.h>
using namespace std;
#define set(x) Set(x)
#define REP(i,j,k) for (int i=(j),_end_=(k);i<=_end_;++i)
#define DREP(i,j,k) for (int i=(j),_start_=(k);i>=_start_;--i)
#define mp make_pair
#define x first
#define y second
#define pb push_back
template<typename T> inline bool chkmin(T &a,const T &b){ return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a,const T &b){ return a < b ? a = b, 1 : 0; }
typedef long long LL;
typedef pair<int,int> node;
const int dmax = 1010, oo = 0x3f3f3f3f;
int n, m;
int a[dmax][dmax] , ans;
int d[dmax], e[dmax];
priority_queue <node> q;
inline bool operator >(node a,node b){ return a.y>b.y; }
bool p[dmax];
void Set(int x){ p[x] = 1; }
void unset(int x){ p[x] = 0; }
bool check(int x){ return x != 1 && x != n && !p[x] && e[x] > 0; }
void preflow(){
    e[1] = oo;
    d[1] = n - 1;
    q.push(mp(1, n - 1));
    set(1);
    while (!q.empty()) {
        bool flag = 1;
        int k = q.top().x;
        q.pop(), unset(k);
        DREP(i, n, 1)
        if ((d[k] == d[i] + 1 || k == 1) && a[k][i] > 0){
            flag = 0;
            int t = min(a[k][i], e[k]);
            e[k] -= t;
            a[k][i] -= t;
            e[i] += t;
            a[i][k] += t;
            if (check(i)) {
                q.push(mp(i, d[i]));
                set(i);
            }
            if (e[k] == 0) break;
        }
        if (flag) {
            d[k] = oo;
            REP(i, 1, n)
            if (a[k][i] > 0) chkmin(d[k], d[i] + 1);
        }
        if (check(k)) {
            q.push(mp(k, d[k]));
            set(k);
        }
    }
    ans = e[n];
}
int main() {
    n = 2, m = 2;
    int x, y;
    scanf("%d%d", &x, &y);
    a[1][2] += x + y;
    preflow();
    printf("%d\n", ans);
    return 0;
}
```
### 算法二十、线段树
```cpp
#include <bits/stdc++.h>
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
using namespace std;
struct SegmentTree {
    int l, r; //区间左右端点 
    long long sum, add; //sum 区间和  add 延迟标记 
} tree[400010];
int a[100010], n = 1, m = 2;
void build (int p, int l, int r) {
    l(p) = l, r(p) = r;
    if(l == r) {sum(p) = a[l]; return;}
    int mid = l + r >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    sum(p) = sum(p * 2) + sum(p * 2 + 1);
}
void spread(int p) {
    if(add(p)) { //节点p有标记 
        sum(p * 2) += add(p) * (r(p * 2) - l(p * 2) + 1); //更新左子节点信息 
        sum(p * 2 + 1) += add(p) * (r(p * 2 + 1) - l(p * 2 + 1) + 1); //更新右子节点
        add(p * 2) += add(p); //给左子节点打延迟标记 
        add(p * 2 + 1) += add(p); //给右子节点打延迟标记 
        add(p) = 0; //清除p的标记 
    }
}
void change(int p, int l, int r, int d) {
    if(l <= l(p) && r >= r(p)) { //完全覆盖 
        sum(p) += (long long) d * (r(p) - l(p) + 1);
        add(p) += d;
        return;
    }
    spread(p);
    int mid = l(p) + r(p) >> 1;
    if(l <= mid) change(p * 2, l, r, d);
    if(r > mid) change(p * 2 + 1, l, r, d);
    sum(p) = sum(p * 2) + sum(p * 2 + 1);
}
long long ask(int p, int l, int r) {
    if(l <= l(p) && r >= r(p)) return sum(p);
    spread(p);
    int mid = l(p) + r(p) >> 1;
    long long val = 0;
    if(l <= mid) val += ask(p * 2, l, r);
    if(r > mid) val += ask(p * 2 + 1, l, r);
    return val;
}
int main() {
    a[1] = 0;
    build(1, 1, n);
    while(m--) { 
        int d = 0;
        scanf("%d", &d);
        change(1, 1, 1, d);
    }
    printf("%lld\n", ask(1, 1, 1));
    return 0;
}
```
### 算法二十一、树状数组
```cpp
#include<bits/stdc++.h>
using namespace std;
const int SIZE = 100010;
int a[SIZE], n = 1, m = 2;
long long c[2][SIZE], sum[SIZE];

long long ask(int k, int x) {
    long long ans = 0;
    for(; x ; x -= x & -x) ans += c[k][x];
    return ans;
}

void add(int k,int x,int y) {
    for(; x <= n; x += x & -x) c[k][x] += y;
}

int main() {
    a[1] = 0;
    while(m--) {
        int d = 0;
        scanf("%d", &d);
        add(0, 1, d);
        add(0, 2, -d);
        add(1, 1, d);
        add(1, 2, -2 * d);
    }
    long long ans = sum[1] + 2 * ask(0, 1) - ask(1, 1);
    ans -= sum[0] + 1 * ask(0, 0) - ask(1, 0);
    printf("%lld\n", ans);
    return 0;
}
```
### 算法二十二、分块
```cpp
#include<bits/stdc++.h>
using namespace std;
long long a[50000010], sum[50000010], add[50000010];
int L[50000010], R[50000010];
int pos[50000010];
int n = 1, m = 2, t;

void change(int l, int r, long long d) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) a[i] += d;
        sum[p] += d*(r - l + 1);
    }
    else {
        for (int i = p + 1; i <= q - 1; i++) add[i] += d;
        for (int i = l; i <= R[p]; i++) a[i] += d;
        sum[p] += d*(R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) a[i] += d;
        sum[q] += d*(r - L[q] + 1);
    }
}

long long ask(int l, int r) {
    int p = pos[l], q = pos[r];
    long long ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) ans += a[i];
        ans += add[p] * (r - l + 1);
    }
    else {
        for (int i = p + 1; i <= q - 1; i++)
            ans += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = l; i <= R[p]; i++) ans += a[i];
        ans += add[p] * (R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) ans += a[i];
        ans += add[q] * (r - L[q] + 1);
    }
    return ans;
}

int main() {
    a[1] = 0;
    t = sqrt(n*1.0);
    for (int i = 1; i <= t; i++) {
        L[i] = (i - 1)*sqrt(n*1.0) + 1;
        R[i] = i*sqrt(n*1.0);
    }
    if (R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;
    for (int i = 1; i <= t; i++)
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            sum[i] += a[j];
        }
    while (m--) {
        int d;
        scanf("%d", &d);
        change(1, 1, d);
    }
    printf("%lld\n", ask(1, 1));
}
```
### 算法二十三、LCT  
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data,rev,sum;
    node *son[2],*pre;
    bool judge();
    bool isroot();
    void pushdown();
    void update();
    void setson(node *child,int lr);
}lct[233];
int top,a,b;
node *getnew(int x)
{
    node *now=lct+ ++top;
    now->data=x;
    now->pre=now->son[1]=now->son[0]=lct;
    now->sum=0;
    now->rev=0;
    return now;
}
bool node::judge()
{
    return pre->son[1]==this;
}
bool node::isroot()
{
    if(pre==lct)return true;
    return !(pre->son[1]==this||pre->son[0]==this);
}
void node::pushdown()
{
    if(this==lct||!rev)return;
    swap(son[0],son[1]);
    son[0]->rev^=1;
    son[1]->rev^=1;
    rev=0;
}
void node::update()
{
    sum=son[1]->sum+son[0]->sum+data;
}
void node::setson(node *child,int lr)
{
    this->pushdown();
    child->pre=this;
    son[lr]=child;
    this->update();
}
void rotate(node *now)
{
    node *father=now->pre,*grandfa=father->pre;
    if(!father->isroot()) grandfa->pushdown();
    father->pushdown();
    now->pushdown();
    int lr=now->judge();
    father->setson(now->son[lr^1],lr);
    if(father->isroot()) now->pre=grandfa;
    else grandfa->setson(now,father->judge());
    now->setson(father,lr^1);
    father->update();
    now->update();
    if(grandfa!=lct) grandfa->update();
}
void splay(node *now)
{
    if(now->isroot())return;
    for(; !now->isroot(); rotate(now))
    if(!now->pre->isroot())
    now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now)
{
    node *last=lct;
    for(; now!=lct; last=now,now=now->pre) {
        splay(now);
        now->setson(last,1);
    }
    return last;
}
void changeroot(node *now)
{
    access(now)->rev^=1;
    splay(now);
}
void connect(node *x,node *y)
{
    changeroot(x);
    x->pre=y;
    access(x);
}
void cut(node *x,node *y)
{
    changeroot(x);
    access(y);
    splay(x);
    x->pushdown();
    x->son[1]=y->pre=lct;
    x->update();
}
int query(node *x,node *y)
{
    changeroot(x);
    node *now=access(y);
    return now->sum;
}
int main()
{
    scanf("%d%d",&a,&b);
    node *A=getnew(a);
    node *B=getnew(b);
    connect(A,B);
    cut(A,B);
    connect(A,B);
    printf("%d",query(A,B));
    return 0;
}
```
### 算法二十四、Splay
```cpp
#include <bits/stdc++.h>
#define ll long long
#define N 100000
using namespace std;
int sz[N], rev[N], tag[N], sum[N], ch[N][2], fa[N], val[N];
int n, m, rt, x;
void push_up(int x){
    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
    sum[x] = sum[ch[x][1]] + sum[ch[x][0]] + val[x];
}
void push_down(int x){
    if(rev[x]){
        swap(ch[x][0], ch[x][1]);
        if(ch[x][1]) rev[ch[x][1]] ^= 1;
        if(ch[x][0]) rev[ch[x][0]] ^= 1;
        rev[x] = 0;
    }
    if(tag[x]){
        if(ch[x][1]) tag[ch[x][1]] += tag[x], sum[ch[x][1]] += tag[x];
        if(ch[x][0]) tag[ch[x][0]] += tag[x], sum[ch[x][0]] += tag[x];
        tag[x] = 0;
    }
}
void rotate(int x, int &k){
    int y = fa[x], z = fa[fa[x]];
    int kind = ch[y][1] == x;
    if(y == k) k = x;
    else ch[z][ch[z][1]==y] = x;
    fa[x] = z; fa[y] = x; fa[ch[x][!kind]] = y;
    ch[y][kind] = ch[x][!kind]; ch[x][!kind] = y;
    push_up(y); push_up(x);
}
void splay(int x, int &k){
    while(x != k){
        int y = fa[x], z = fa[fa[x]];
        if(y != k) if(ch[y][1] == x ^ ch[z][1] == y) rotate(x, k);
        else rotate(y, k);
        rotate(x, k);
    }
}
int kth(int x, int k){
    push_down(x);
    int r = sz[ch[x][0]]+1;
    if(k == r) return x;
    if(k < r) return kth(ch[x][0], k);
    else return kth(ch[x][1], k-r);
}
void split(int l, int r){
    int x = kth(rt, l), y = kth(rt, r+2);
    splay(x, rt); splay(y, ch[rt][1]);
}
void rever(int l, int r){
    split(l, r);
    rev[ch[ch[rt][1]][0]] ^= 1;
}
void add(int l, int r, int v){
    split(l, r);
    tag[ch[ch[rt][1]][0]] += v;
    val[ch[ch[rt][1]][0]] += v;
    push_up(ch[ch[rt][1]][0]);
}
int build(int l, int r, int f){
    if(l > r) return 0;
    if(l == r){
        fa[l] = f;
        sz[l] = 1;
        return l;
    }
    int mid = l + r >> 1;
    ch[mid][0] = build(l, mid-1, mid);
    ch[mid][1] = build(mid+1, r, mid);
    fa[mid] = f;
    push_up(mid);
    return mid;
}
int asksum(int l, int r){
    split(l, r);
    return sum[ch[ch[rt][1]][0]];
}
int main(){
    //总共两个数
    n = 2;
    rt = build(1, n+2, 0);//建树
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        add(i, i, x);//区间加
    }
    rever(1, n);//区间翻转
    printf("%d\n", asksum(1, n));//区间求和
    return 0;
}
```

### 算法二十五、LCA
```cpp
#include<cstdio>
#define NI 2
struct edge
{
    int to,next,data;
}e[30];
int v[10],d[10],lca[10][NI+1],f[10][NI+1],tot=0;
void build(int x,int y,int z)
{
    e[++tot].to=y; e[tot].data=z; e[tot].next=v[x]; v[x]=tot;
    e[++tot].to=x; e[tot].data=z; e[tot].next=v[y]; v[y]=tot;
}
void dfs(int x)
{
    for(int i=1;i<=NI;i++)
        f[x][i]=f[x][i-1]+f[lca[x][i-1]][i-1],
        lca[x][i]=lca[lca[x][i-1]][i-1];
    for(int i=v[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if(lca[x][0]==y) continue;
        lca[y][0]=x;
        f[y][0]=e[i].data;
        d[y]=d[x]+1;
        dfs(y);
    }
}
int ask(int x,int y)
{                                                                        
    if(d[x]<d[y]) {int t=x;x=y;y=t;}
    int k=d[x]-d[y],ans=0;
    for(int i=0;i<=NI;i++)
        if(k&(1<<i))
            ans+=f[x][i],
            x=lca[x][i];
    for(int i=NI;i>=0;i--)
        if(lca[x][i]!=lca[y][i])
            ans+=f[x][i]+f[y][i],
            x=lca[x][i],y=lca[y][i];
    return ans+f[x][0]+f[y][0];
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    build(1,2,a);
    build(1,3,b);
    dfs(1);
    printf("%d",ask(2,3));
}
```
### 算法二十六、字典树
```cpp
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node{
    int str[26];
    int sum;
}s[1000];
char str1[100];
int t=0,tot=0,ss=0;
bool f1;
void built()
{
    t=0;
    for(int i=0;i<strlen(str1);i++)
    {
         if(str1[i]=='-'){
             f1=true;continue;
         }
         if(!s[t].str[str1[i]-'0'])
         s[t].str[str1[i]-'0']=++tot;
         t=s[t].str[str1[i]-'0'];
         s[t].sum=str1[i]-'0';
    }
}
int query()
{
   int t=0;int s1=0;
   for(int i=0;i<strlen(str1);i++)
   {
           if(str1[i]=='-') continue;
           if(!s[t].str[str1[i]-'0']) return s1;
           t=s[t].str[str1[i]-'0'];
           s1=s1*10+s[t].sum;
   }
   return s1;
}
int main()
{    
  for(int i=1;i<=2;i++)
  {
      f1=false;
      scanf("%s",str1);
    built();
    if(f1)
      ss-=query();
      else ss+=query();
  }
  printf("%d",ss);
  return 0;    
}
```
### 算法二十七、Bellman-Ford
```cpp
#include <bits/stdc++.h>
using namespace std;
int dis[50], u[50], v[50], w[50], n, m;
void bellman(int start) {
    for (int i = 1;i <= n; i++) dis[i] = 0x3f3f3f3f;
    dis[start] = 0;
    for (int i = 1;i < n; i++)
        for (int j = 1;j <= m; j++)
            if (dis[v[j]] > dis[u[j]] + w[j]) dis[v[j]] = dis[u[j]] + w[j];
}
int main() {
    n = 3; m = 2;
    for (int i = 1;i <= m; i++) cin  >> w[i], u[i] = i, v[i] = i + 1;
    bellman(1);
    printf("%d\n", dis[3]);
    return 0;
}
```
### 算法二十八、打表
```cpp
#include <bits/stdc++.h>
using namespace std;
int a, b; int main() { 
    scanf("%d%d", &a, &b);
    if(a==3&&b==4) printf("7");
    else if(a==45&&b==55) printf("100");
    else if(a==123&&b==321) printf("444");
    else if(a==91086199&&b==18700332)printf("109786531");
    else if(a==42267194&&b==60645282)printf("102912476")
    else if(a==69274392&&b==10635835)printf("79910227");
    else if(a==5710219&& b==85140568)printf("90850787");
    else if(a==75601477&&b==24005804)printf("99607281");
    else if(a==70597795&&b==90383234)printf("160981029");
    else if(a==82574652&&b==22252146)printf("104826798");
}
```
### 算法二十九、SPFA求最短路之SLF优化
```cpp
#include<bits/stdc++.h>
using namespace  std;
const int maxn = 100000 + 10;
const int INF = 0x7FFFFFFF;

int pre[maxn], dis[maxn], path[maxn];
bool vis[maxn];
int head[maxn], n, m;

int tot, cnt;
struct node {
    int v, w, next;
} E[2 * maxn];
void add(int u, int v, int w) {
    E[tot].v = v;
    E[tot].w = w;
    E[tot].next = head[u];
    head[u] = tot++;
}
void init() {
    tot = 0;
    memset(vis, 0, sizeof vis);
    memset(head, -1, sizeof head);
}
void spfa(int st) {
    for (int i = 1;i <= n; i++) vis[i] = false, dis[i] = INF;
    int now, next;
    dis[st] = 0; vis[st] = 1;
    deque<int> q;
    q.push_back(st);
    pre[st] = -1;
    while(!q.empty()) {
        now = q.front();
        q.pop_front();
        vis[now] = 0;
        for (int i = head[now]; i != -1;i = E[i].next) {
            next = E[i].v;
            if(dis[next] > dis[now] + E[i].w) {
                dis[next] = dis[now] + E[i].w;
                pre[next] = now;
                if(!vis[next]) {
                        vis[next] = 1; 
                        if (q.empty() || dis[next] > dis[q.front()]) q.push_back(next);
                        else q.push_front(next);
                }
            }
        }
    }
}
void print(int x) {
    if(pre[x] == -1) return;
    print(pre[x]);
    printf("%d ", x);
}
int main() {
    init();
    n = 3; m = 2;
    int w;
    for (int i = 1;i <= m; i++) {scanf("%d", &w); add(i, i + 1, w);}
    spfa(1);
    if(dis[n] == INF) puts("-1");
    else printf("%d\n", dis[n]);
    return 0;
}
```
### 算法三十、SPFA之LLL优化
```cpp
#include<bits/stdc++.h>
#define MAXN 10010
#define MAXM 500010
#define MAX 2147483647
using namespace std;
int n, m, t, c = 1;
int head[MAXN], path[MAXN];
bool vis[MAXN];
struct node {
    int next, to, w;
}a[MAXM << 1];
inline int relax (int u, int v, int w) {
    if (path[v] > path[u] + w) {
        path[v] = path[u] + w;
        return 1;
    }
    return 0;
}
inline void add(int u, int v, int w) {
    a[c].to = v;
    a[c].w = w;
    a[c].next = head[u];
    head[u] = c++;
}
void spfa() {
    int u, v, num = 0;
    long long x = 0;
    list<int> q;
    for (int i = 1;i <= n; i++){path[i] = MAX; vis[i] = 0;}
    path[1] = 0;
    vis[1] = 1;
    q.push_back(1);
    num++;
    while (!q.empty()) {
        u = q.front();
        q.pop_front();
        num--; x -= path[u];
        while (num && path[u] > x / num){
            q.push_back(u);
            u = q.front();
            q.pop_front();
        }
        vis[u] = 0;
        for (int i = head[u]; i ; i = a[i].next) {
            v = a[i].to;
            if (relax(u, v, a[i].w) && !vis[v]) {
                vis[v] = 1;
                if(!q.empty() && path[v] < path[q.front()]) q.push_front(v);
                else q.push_back(v);
                num++; x += path[v];
            }
        }
    }
}
int main() {
    n = 3; m = 2;
    for (int i = 1;i <= m; i++) {
        int w;
        scanf("%d", &w);
        add(i, i + 1, w);
    }
    spfa();
    printf("%d\n", path[n]);
    return 0;
}
```
### 算法三十一、SPFA之SLF+LLL优化算法
```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
const int gg = 200000 + 11;
int head[gg], dis[gg], n, m, cnt;
bool vis[gg];
int sum, tot;
struct node{
    int net, to, w;
} a[gg];

inline void add(int i, int j, int w) {
    a[++cnt].to = j;
    a[cnt].net = head[i];
    a[cnt].w = w;
    head[i] = cnt;
}

inline void spfa(int s) {
    deque<int> q;
    for (int i = 1;i <= n; i++) dis[i] = INF;
    dis[s] = 0; vis[s] = 1;    
    q.push_back(s);
    tot = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop_front();
        vis[u] = false;
        tot--;
        sum -= dis[u];
        for (int i = head[u]; ~i ; i = a[i].net) {
            int v = a[i].to;
            if (dis[v] > dis[u] + a[i].w) {
                dis[v] = dis[u] + a[i].w;
                if(!vis[v]) {
                    vis[v] = 1;
                    if (q.empty() || dis[v] > dis[q.front()] || dis[v] * tot <= sum) q.push_back(v);
                    tot++;
                    sum += dis[v];
                }
            }
        }
    }
}

int main() {
    memset(head, -1, sizeof head);
    n = 3; m = 2;
    for (int i = 1;i <= m; i++) {
        int w = 0;
        scanf("%d", &w);
        add(i, i + 1, w);
    }
    spfa(1);
    if (dis[n] == INF)  puts("-1");
    else printf("%d\n", dis[n]);
    return 0;
}
```
### 算法三十二、只用一个变量跑A+B
```cpp
#include<iostream>
using namespace std;
long long a;
int main() {
    scanf("%d%d", (int*)(&a), (int*)(&a+1));
    printf("%d\n", *((int*)&a) + *((int*)(&a+1)));
    return 0;
}
```
### 算法三十三、矩阵乘法
```cpp
#include<bits/stdc++.h>
using namespace std;
int a, b;
int x[2][2] = {
    {0, 1},
    {1, 1}
};
void mo(int f[]) {
    int ans[2] = {0};
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++) ans[i] += f[j] * x[i][j];
    for(int i = 0; i < 2; i++) f[i] = ans[i];
}
int main() {
    cin >> a >> b;
    int f[3] = {a, b};
    mo(f);
    cout << f[1];
    return 0;
}
```
### 算法三十四、STL+dijkstra
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <ctime>
#include <string>
#include <cstring>
using namespace std;
const int N=405;
struct Edge {
    int v,w;
};
vector<Edge> edge[N*N];
int n;
int dis[N*N];
bool vis[N*N];
struct cmp {
    bool operator()(int a,int b) {
        return dis[a]>dis[b];
    }
};
int Dijkstra(int start,int end)
{
    priority_queue<int,vector<int>,cmp> dijQue;
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dijQue.push(start);
    dis[start]=0;
    while(!dijQue.empty()) {
        int u=dijQue.top();
        dijQue.pop();
        vis[u]=0;
        if(u==end)
            break;
        for(int i=0; i<edge[u].size(); i++) {
            int v=edge[u][i].v;
            if(dis[v]==-1 || dis[v]>dis[u]+edge[u][i].w) {
                dis[v]=dis[u]+edge[u][i].w;
                if(!vis[v]) {
                    vis[v]=true;
                    dijQue.push(v);
                }
            }
        }
    }
    return dis[end];
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    Edge Qpush;

Qpush.v=1;
    Qpush.w=a;
    edge[0].push_back(Qpush);

Qpush.v=2;
    Qpush.w=b;
    edge[1].push_back(Qpush);

printf("%d",Dijkstra(0,2));
    return 0;
}
```
### 算法三十五、数学表达式
```cpp
#include <bits/stdc++.h>
using namespace std;
long long a, b;
int main() {
    cin >> a >> b;
    cout << a - b + (a * 2) - (a - b) - a + (a + (b - a)) << endl;
    return 0;
}
```
### 算法三十六、define大法
```cpp
#include <bits/stdc++.h>
#define ___ int
#define
$ main 
#define _$_$_ return 
#define _ cin 
#define $ cout 
#define __ using 
#define
$ main #define _$_$_ return #define _ cin #define $ cout #define __ using #define
namespace
#define o_o std
__
o_o; 
___
o_o; ___
$(){
    ___ _$o$_,$o_o$;
    _ >> _$o$_ >> $o_o$;
    $ << _$o$_ + $o_o$;
    _$_$_ 0;
}
```
### 算法三十七、压位高精度加法
```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 100000000;
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % mod);
        t /= mod;
    }
    if (t) C.push_back(t);
    return C;
}
int main() {
    string a, b; cin >> a >> b;
    vector<int> A, B, C;
    for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i--) {
        s += (a[i] - '0') * t;
        j++; t *= 10;
        if (j == 8 || i == 0) A.push_back(s), s = 0, j = 0, t = 1;
    }
    for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i--) {
        s += (b[i] - '0') * t;
        j++; t *= 10;
        if (j == 8 || i == 0) B.push_back(s), s = 0, j = 0, t = 1;
    }
    C = add(A, B);
    cout << C.back();
    for (int i = C.size() - 2; i >= 0; i--) printf("%08d", C[i]);
    return 0;
}
```
### 算法三十八、加一大堆东东…… 
听说手动开O3优化……
```cpp
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b; scanf("%d%d", &a, &b);
    printf("%d", a + b);
    return 0;
}
```
### 算法三十九、暴力枚举优化版
和算法六区别“不大”但是时间优化了300ms……  
时间：1567ms
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b; scanf("%d%d", &a, &b);
    for (int i = min(2 * a, 2 * b);i <= max(2 * a, 2 * b); i++)
        if (a + b == i) {
            printf("%d", i); //注意要输出i，不然如果输出a+b循环就没意义了……
            return 0;
        }
}
```
### 算法四十、矩阵DP
就是和方格取数之类的这些同样的思维~
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[110][110], n = 2;
int main() {
    for (int i = 1;i <= n; i++)
        for (int j = 1;j <= n; j++) scanf("%d", &a[i][j]);
    for (int i = 1;i <= n; i++)
        for (int j = 1;j <= n; j++) 
            if (max(a[i - 1][j], a[i][j - 1]) > -1) a[i][j] += max(a[i - 1][j], a[i][j - 1]);
    printf("%d\n", a[n][n]);
    return 0;
}
```
### 算法四十一、拖延时间大法
```cpp
#include <algorithm>//STL 通用算法
#include <bitset>//STL 位集容器
#include <cctype>//字符处理
#include <cerrno>//定义错误码
#include <cfloat>//浮点数处理
#include <ciso646>//对应各种运算符的宏
#include <climits>//定义各种数据类型最值的常量
#include <clocale>//定义本地化函数
#include <cmath>//定义数学函数#include <complex>//复数类
#include <csignal>//信号机制支持
#include <csetjmp>//异常处理支持
#include <cstdarg>//不定参数列表支持
#include <cstddef>//常用常量
#include <cstdio>//定义输入／输出函数
#include <cstdlib>//定义杂项函数及内存分配函数
#include <cstring>//字符串处理
#include <ctime>//定义关于时间的函数
#include <cwchar>//宽字符处理及输入／输出
#include <cwctype>//宽字符分类
#include <deque>//STL 双端队列容器
#include <exception>//异常处理类
#include <fstream>//文件输入／输出
#include <functional>//STL 定义运算函数（代替运算符）
#include <limits>//定义各种数据类型最值常量
#include <list>//STL 线性列表容器
#include <locale>//本地化特定信息
#include <map>//STL 映射容器
#include <memory>//STL通过分配器进行的内存分配
#include <new>//动态内存分配
#include <numeric>//STL常用的数字操作
#include <iomanip>//参数化输入／输出
#include <ios>//基本输入／输出支持
#include <iosfwd>//输入／输出系统使用的前置声明
#include <iostream>//数据流输入／输出
#include <istream>//基本输入流
#include <iterator>//STL迭代器
#include <ostream>//基本输出流
#include <queue>//STL 队列容器
#include <set>//STL 集合容器
#include <sstream>//基于字符串的流
#include <stack>//STL 堆栈容器
#include <stdexcept>//标准异常类
#include <streambuf>//底层输入／输出支持
#include <string>//字符串类
#include <typeinfo>//运行期间类型信息
#include <utility>//STL 通用模板类
#include <valarray>//对包含值的数组的操作
#include <vector>//STL 动态数组容器
using namespace std;
int main(){
    int a; int b; //不用int a, b;，拖延运行时间
    cin >> a >> b; //cin拖延运行时间
    int ans=0；
    for(int i=1;i<=a;i++)ans++;//拖延时间 
    for(int i=1;i<=b;i++)ans++;//拖延时间 
    ans=ans-ans+ans+ans-ans;//表达式拖延时间
    cout<<ans<<endl; //cout和多输出回车拖延时间 
    return 0;
}
```
### 算法四十二、极限卡点
卡到了9970ms……
```cpp
#include <bits/stdc++.h>
using namespace std;
int st = clock();
int main() {
    int a, b; scanf("%d%d", &a, &b);
    while (clock() - st < 995000) {}
    printf("%d", a + b);
    return 0;
}
```
### 算法四十三、快读快写
```cpp
#include<bits/stdc++.h>
using namespace std;
int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {  
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}
void write(int x) {
    if(x < 0) {
        putchar('-'); 
        x = -x;
    }
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}
int main() {
    int a, b; a = read(); b = read();
    write(a + b);
    return 0;
}
```
### 算法四十四、终极大杀器快读快写
```cpp
#include<bits/stdc++.h>
using namespace std;
static char buf[100000], *pa = buf, *pd = buf;
#define gc pa == pd && (pd = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pd) ? EOF : *pa++
inline int read() {
    register int x(0); register char c(gc);
    while (c < '0' || c > '9') c = gc;
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = gc;
    return x;
}
void write(int x) {
    if(x < 0) {
        putchar('-'); 
        x = -x;
    }
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}
int main() {
    int a, b; a = read(); b = read();
    write(a + b);
    return 0;
}
```
### 算法四十五、sort大法
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}
```
### 算法四十六、冒泡排序
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = n;i > 1; i--)
        for(int j = 1;j < i; j++)
            if(a[j] > a[j + 1]) swap(a[j], a[j + 1]);
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}
```
### 算法四十七、选择排序
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1;i < n; i++) {
        int w = i, Min = a[i];
        for (int j = i;j <= n; j++) if(Min > a[j])w=j,Min=a[j]; //寻找最小数和它的位置
        swap(a[i], a[w]);
    }
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}
```
### 算法四十八、插入排序
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
    n = 2;
    for (int i = 1;i <= n; i++) {
        scanf("%d", &a[i]); int x = i - 1;
        while(a[x] > a[x + 1] && x > 0) swap(a[x], a[x + 1]), x--;
    }
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}
```
### 算法四十九、希尔排序
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
    n = 2;
    for (int i = 0;i < n; i++) scanf("%d", &a[i]);
    for (int step = n / 2; step > 0; step /= 2)
        for (int i = 0;i < step; i++)
            for (int j = i + step;j < n; j += step)
                if(a[j] < a[j - step]) {
                    int temp = a[j];
                    int k = j - step;
                    while (k >= 0 && temp < a[k]) {
                        swap(a[k + step], a[k]);
                        k -= step;
                    }
                }
    int ans = 0;
    for (int i = 0;i < n; i++) ans += a[i]; printf("%d ", ans);
    return 0;
}
```
### 算法五十、归并排序
```cpp
#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN], T[MAXN];
void Mergesort(int l, int r) {
    if (l == r) return; //区间内只有一个数，返回
    int mid = l + r >> 1; //相当于(l + r) / 2
    Mergesort(l, mid); //递归左半部分
    Mergesort(mid + 1, r); //递归右半部分
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) //合并
        if (a[i] <= a[j]) T[k++] = a[i++];
        else T[k++] = a[j++];
    while (i <= mid) T[k++] = a[i++];
    while (j <= r) T[k++] = a[j++];
    for (int q = l; q <= r; q++) a[q] = T[q]; //转移
}
int main() {
    n = 2;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    Mergesort(1, n);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}
```
### 算法五十一、快速排序
```cpp
#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
void quickSort(int l, int r) {
    if (l >= r) return;
    int i = l, j = r, base = a[l]; //base取最左边的数为基准数
    while(i < j) {
        while (a[j] >= base && i < j) j--;
        while (a[i] <= base && i < j) i++;
        if (i < j) swap(a[i], a[j]);
    }
    a[l] = a[i]; a[i] = base; //基准数归位
    quickSort (l, i - 1); //递归左边
    quickSort (i + 1, r); //递归右边
}
int main() {
    n = 2;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    quickSort(1, n);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}
```
### 算法五十二、堆排序
```cpp
#include  <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 1e8 + 10;
int h[MAXN], s;
void down(int u) {
    int t = u;  // t记录最小值
    if (2 * u <= s && h[2 * u] < h[t]) t = 2 * u; // 左儿子
    if (2 * u + 1 <= s && h[2 * u + 1] < h[t]) t = 2 * u + 1; // 右儿子
    if (t != u) { //需要调整
        swap(h[t], h[u]);
        down(t); //递归
    }
}
int main() {
    n = 2;
    for (int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    s = n;
    for (int i = n / 2; i >= 1; i--) down(i); //初始化堆j
    int ans = 0;
    while (n--) {
        ans += h[1];
        h[1] = h[s]; s--;
        down(1); 
    }
    printf("%d", ans);
    return 0;
}
```
### 算法五十三、计数排序
```cpp
#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
long long n, cnt[MAXN];
int main() {
    n = 2; int x = 0, Max = -0x3f3f3f, Min = 0x3f3f3f; //初始化最大值和最小值
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &x); cnt[x]++; //统计
        Max = max(Max, x); Min = min(Min, x); //更新最大值和最小值
    }
    int ans = 0;
    for (int i = Min;i <= Max; i++)
        while(cnt[i]) cnt[i]--, ans += i;
    printf("%d", ans);
    return 0;
}
```
### 算法五十四、桶排序
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, Min = MAXN, Max = 0, sum[MAXN], ans;
bool f[45];
vector<int> bucket[45];//定义桶，这里定义40个桶
void insertsort(int s) {
    for (int i = 0;i < bucket[s].size(); i++)
        for (int j = i;j >= 1; j--) if(bucket[s][j - 1] > bucket[s][j]) swap(bucket[s][j], bucket[s][j - 1]);//这里是从小到大排序
    for (int i = 0;i < bucket[s].size(); i++) ans += bucket[s][i];
}
void bucketsort() {
    for (int i = 1;i <= n; i++)
        bucket[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))].push_back(sum[i]), f[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))] = 1;//运用最大最小值来合理分配桶
    for (int i = 0;i <= 40; i++) if(f[i]) insertsort(i); //如果当前桶有数值，则对桶内的数进行排序（这里用选择排序）
}
int main() {
    n = 2;
    for (int i = 1;i <= n; i++) {
        scanf("%d", &sum[i]);
        Min = min(Min, sum[i]), Max = max(Max, sum[i]); //为了能够合理利用空间，确保第一个桶和最后一个桶都有数，所以存储最大最小值
    }
    bucketsort(); printf("%d", ans);
    return 0; 
}
```
### 算法五十五、基数排序
```cpp
#include <bits/stdc++.h>
using namespace std;
int maxbit(int data[], int n) {
    int d = 1, p = 10; //d保存最大的位数 
    for (int i = 0;i < n; i++) while(data[i] >= p) p *= 10, d++;
    return d;
}
void radixsort(int data[], int n) { //基数排序 
    int d = maxbit(data, n);
    int tmp[n];
    int cnt[15], i, j, k, radix = 1;
    for (i = 1;i <= d; i++) { //进行d次排序
        memset(cnt, 0, sizeof(cnt)); //清空计数器
        for (j = 0;j < n; j++) {
            k = (data[j] / radix) % 10;
            cnt[k]++;
        }
        for (j = 1;j < 10; j++) cnt[j] += cnt[j - 1];
        for (j = n - 1;j >= 0; j--) {
            k = (data[j] / radix) % 10;
            tmp[cnt[k] - 1] = data[j];
            cnt[k]--;
        }
        for (j = 0;j < n; j++) data[j] = tmp[j];
        radix *= 10;
    }
}
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
    n = 2;
    for (int i = 0;i < n; i++) scanf("%d", &a[i]);
    radixsort(a, n);
    int ans = 0;
    for (int i = 0;i < n; i++) ans +=  a[i]; printf("%d", ans);
}
```
### 算法五十六、鸡尾酒排序
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main() {
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    int cnt = 0;
    while (1) {
        int f = 0; cnt++;
        if(cnt & 1)
            for (int i = 1;i < n; i++) if(a[i] > a[i + 1]) swap(a[i], a[i + 1]), f = 1;
        else
            for (int i = n;i > 1; i--) if(a[i] < a[i - 1]) swap(a[i], a[i - 1]), f = 1;
        if(!f) break;
    }
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}
```
### 算法五十七、二叉排序树排序
```cpp
#include<bits/stdc++.h>
#define LL long long
#define INF 0x7FFFFFFF
using namespace std;
const int N = 1e8 + 10;
int n, idx, rt, ans;
int a[N], t[N];
int ch[N][2];
void insert(int &x, int val) {
    if (!x) {
        x = ++ idx;
        t[x] = val;
        return;
    }
    else {
        if(val < t[x]) insert(ch[x][0], val);
        else insert(ch[x][1], val);
    }
}
void dfs(int x) { //中序遍历二叉排序树
    if(!x) return;
    dfs(ch[x][0]);
    ans += t[x];
    dfs(ch[x][1]);
}
int main() {
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1;i <= n; i++) insert(rt, a[i]);
    dfs(rt); printf("%d", ans);
    return 0;
}
```
### 算法五十八、侏儒排序
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main() {
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    int s = 1;
    while(s <= n) {
        if(a[s - 1] <= a[s] || s == 0) s++;
        else swap(a[s], a[s - 1]), s--;
    }
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
} 
```
### 算法五十九、猴子排序
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int check() {
    for (int i = 1;i < n; i++) if(a[i] > a[i + 1]) return 0;
    return 1;
}
int main() {
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    while (1) {
        random_shuffle(a + 1, a + 1 + n);   //随机打乱数组的系统函数 
        if(check()) break;
    }
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}
```
### 算法六十、快速幂
```cpp
#include<bits/stdc++.h>
using namespace std;
int qmi(int m, int k, int p) {
    int res = 1 % p, t = m;
    while (k) {
        if (k & 1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
int main() {
    int a, b; scanf("%d%d", &a, &b);
    printf("%d", qmi(a, 1, 100000010) + qmi(b, 1, 100000010));
    return 0;
}
```
### 算法六十一、差分
```cpp
#include <bits/stdc++.h>
using namespace std;
int n = 2, m = 5, b[10];
int main() {
    for (int i = 1;i <= n; i++) {
        int x; scanf("%d", &x);
        b[1] += x; b[m + 1] -= x;
    }
    int ans = 0, x = 0;
    for (int i = 1;i <= m; i++) {
        x += b[i]; ans = max(ans, x);
    }
    printf("%d", ans);
    return 0;
}
```
### 算法六十二、模拟人工计算
```cpp
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
    scanf("%d%d", &a, &b); //人眼看见数据
    if (a == 0) {printf("%d", b); return 0;}  //大脑瞬间“打表”被老师发现了，血量减少50……
    if (b == 0) {printf("%d", a); return 0;}  //大脑瞬间“打表”被老师发现了，血量减少50……
    int f1 = 0, f2 = 0; //大脑申请了两个空间……
    if (a < 0) f1 = 1;  //大脑正在判断，请勿打扰……
    if (b < 0) f2 = 1;  //大脑正在判断，请勿打扰……
    a = abs(a); b = abs(b);  //哇！大脑使用了去掉负号的大法！！！
    int ans = 0;   //大脑申请了一个空间
    if (f1) ans -= a;  //大脑正在艰难地判断着……
    //大脑指挥手拿起笔在草稿纸上划来划去……
    //大脑感到烦躁
    //眼睛看到老师转了一下身子，立刻反馈给大脑
    //大脑指挥手在计算器键盘上写下了算式……
    //眼睛看到答案，反馈给大脑，大脑立刻指挥手关掉了计算器……
    //眼睛看到老师转回来了
    else ans += a;  //大脑正在艰难地判断着……
    if (f2) ans -= b;//大脑正在艰难地判断着……
    //大脑指挥手拿起笔在草稿纸上划来划去……
    //大脑感到烦躁
    //眼睛看到老师转了一下身子，立刻反馈给大脑
    //大脑指挥手在计算器键盘上写下了算式……
    //眼睛看到答案，反馈给大脑，大脑立刻指挥手关掉了计算器……
    //眼睛看到老师转回来了
    else ans += b;//大脑正在艰难地判断着……
    //眼睛观察到老师正在身后冷冷地看着……
    //大脑感到紧张
    //大脑让身体不由自主地颤抖起来
    //大脑差点死机
    //大脑复活
    //立刻写下答案
    printf("%d", ans);
    //大脑又死机了……
    //耳朵听到老师在叫自己起来
    //大脑指挥身体起来了
    //开始下一题……（下一个数据）
    return 0;
}
```
### 算法六十三、二进制
```cpp
#include<bits/stdc++.h>
using namespace std;
int a, b, s, s1, i, na, nb;
int main() {
    scanf("%d%d", &a, &b);
    if (a <= 0) na = 1, a = abs(a);
    while(a) {
        if ((a & 1) != 0) s += pow(2, (a & 1) * i);
        a >>= 1; i++;
    }
    i = 0;
    if (na == 1) s = abs(s);
    if (b <= 0) nb = 1, b = abs(b);
    while(b) {
        if ((b & 1) != 0) s1 += pow(2, (b & 1) * i);
        b >>= 1; i++;
    }
    if (nb == 1) s1 = abs(s1);
    printf("%d", s + s1);
    return 0;
}
```
### 算法六十四、ST表
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, a[10], st1[10][17], st2[10][17];
void ST_work1() {
    for (int i = 1; i <= n; i++) st1[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; j++) {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
            st1[i][j] = max(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
    }
}
int ST_query1(int l, int r) {
    int k = log(r - l + 1) / log(2);
    return max(st1[l][k], st1[r - (1 << k) + 1][k]);
}
void ST_work2() {
    for (int i = 1; i <= n; i++) st1[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; j++) {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
            st1[i][j] = min(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
    }
}
int ST_query2(int l, int r) {
    int k = log(r - l + 1) / log(2);
    return min(st1[l][k], st1[r - (1 << k) + 1][k]);
}
int main() {
    n = 2;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    ST_work1(); int ans1 = ST_query1(1, 2);
    ST_work2(); int ans2 = ST_query2(1, 2);
    printf("%d", ans1 + ans2);
    return 0;
}
```
### 算法六十五、01背包
```cpp
#include <bits/stdc++.h>
using namespace std;
int c[1010], w[1010], dp[1010], n, m;
int main() {
    n = 2; m = 2;  //2个物体，背包容积2
    for (int i = 1;i <= n; i++) c[1] = 1, scanf("%d", &w[i]);  //设体积为1，读入价值
    for (int i = 1;i <= n; i++)
        for (int j = m; j >= c[i]; j--)
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    printf ("%d\n", dp[m]);
    return 0;
}
```
### 算法六十六、完全背包
```cpp
#include <bits/stdc++.h>
using namespace std;
int c[1010], w[1010], dp[1010], n, m;
int main() {
    n = 2; m = 3;
    for (int i = 1;i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1;i <= n; i++)
        for (int j = c[i]; j <= m; j++)
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    printf ("%d\n", dp[m]);
    return 0;
}
```
### 算法六十七、多重背包之暴力拆分法
```cpp
#include <bits/stdc++.h>
using namespace std;
int c[110], w[110], s[110], dp[1010], n, m;
int main() {
    n = 2; m = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &w[i]), c[i] = s[i] = 1;
    for (int i = 1;i <= n; i++)
        for (int x = 1;x <= s[i]; x++)
            for (int j = m; j >= c[i]; j--)
                dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    printf ("%d\n", dp[m]);
    return 0;
}
```
### 算法六十八、多重背包之二进制拆分
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, v[10010], w[10010], f[2010];
int main() {
    n = 2; m = 2;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int a = 1, b, s = 1, k = 1; scanf("%d", &b);
        while (k <= s) {
            cnt++;
            v[cnt] = a * k; w[cnt] = b * k;
            s -= k; k <<= 1;
        }
        if (s > 0) {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    printf("%d\n", f[m]);
    return 0;
}
```
### 算法六十九、二维费用背包问题
```cpp
#include <bits/stdc++.h>
using namespace std;
int N, V, M;
int v[1010], m[1010], w[1010], f[1010][1010];
int main () {
    N = V = M = 2;
    for (int i = 1; i <= N; i++) scanf("%d", &w[i]), v[i] = m[i] = 1;
    for (int i = 1; i <= N; i++)
        for (int j = V; j >= v[i]; j--)
            for (int k = M; k >= m[i]; k--)
                f[j][k] = max(f[j - v[i]][k - m[i]] + w[i], f[j][k]);
    printf("%d\n", f[V][M]);
    return 0;
}
```
### 算法七十、分组背包问题
```cpp
#include <bits/stdc++.h>
using namespace std;
int f[110][110], v[110][110], w[110][110], s[110];
int n, m, k;
int main() {
    n = m = 2;
    for (int i = 1; i <= n; i++) {
        s[i] = 1;
        for (int j = 0; j < s[i]; j++) scanf("%d", &w[i][j]), v[i][j] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            for (int k = 0; k < s[i]; k++)
                if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        }
    }
    printf("%d", f[n][m]);
    return 0;
}
```
### 算法七十一、有依赖的背包问题
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, v[110], w[110];
int h[110], e[110], ne[110], idx;
int f[110][110];
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void dfs(int u) {
    for (int i =h[u];~i;i=ne[i]){
        int son = e[i];
        dfs(e[i]);// 分组背包
        for (int j = m - v[u]; j >= 0; j -- )// 循环体积
            for (int k = 0; k <= j; k ++ )// 循环决策
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }// 将物品u加进去
    for (int i = m; i >= v[u]; i -- ) f[u][i] = f[u][i - v[u]] + w[u];
    for (int i = 0; i < v[u]; i ++ ) f[u][i] = 0;
}
int main() {
    n = m = 2;
    memset(h, -1, sizeof h);
    int root;
    for (int i = 1; i <= n; i++) {
        int p; v[i] = 1; scanf("%d", &w[i]);
        if (i == 1) p = -1; else p=1;//A+B中的特判
        if (p == -1) root = i;
        else add(p, i);
    }
    dfs(root);
    printf("%d", f[root][m]);
    return 0;
}
```
### 算法七十二、多重背包队列优化
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[20010], g[20010], q[20010];
int main() {
    n = m = 2;
    for (int i = 1; i <= n; i ++ ) {
        int v = 1, w, s = 1; scanf("%d", &w);
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++ ) {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v) {
                if (hh <= tt && q[hh] < k - s * v) hh ++ ; //剔除超出长度元素
                if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w); //更新当前答案
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
                //维持单调性
                //这里也可以这样写，更易理解
                //while (hh <= tt && g[q[tt]] <= g[k] - (k - q[tt]) / v * w) tt -- ;
                q[++tt] = k;
            } 
        }
    }
    printf("%d", f[m]);
    return 0;
}
```
### 算法七十三、istream_iterator
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#include<iterator>
using namespace std;
int main()
{
    istream_iterator<int> in(cin), eof;
    cout << accumulate(in, eof ,0) << endl;
    return 0;
}
```
### 算法七十四、进制转换
```cpp
#include <bits/stdc++.h>
using namespace std;
int A[30], B[30], a, b;
int check(int mod) {
    int x = a, y = b, ta = 0, tb = 0;
    while (x) {
        A[++ta] = x % mod;
        x /= mod;
    }
    while (y) {
        B[++tb] = y % mod;
        y /= mod;
    }
    for (int i = 1; i <= max(ta, tb); i++) {
        A[i] += B[i];
        if (A[i] >= mod) A[i + 1] += A[i] / mod, A[i] %= mod;
    }
    if (A[ta + 1]) ta++;
    int Ans = 0;
    for (int i = ta; i > 0; i--) Ans = Ans * mod + A[i];
    return Ans;
}
int main() {
    scanf("%d%d", &a, &b);
    int ans[100010];
    for (int i = 1; i <= 100000; i++) {
        srand((unsigned)time(NULL));
        int o = (int) rand() % 1000000 + 2;  //取随机进制
        ans[i] = check(o);
    }
    bool f = 1;
    for (int i = 2; i <= 100000; i++) if (ans[i] != ans[i - 1]) { f = 0; break; }
    if (f) printf("%d\n", ans[1]);
    else puts("老子不干了！WA就WA吧！一行WA上西天！");
    return 0;
}
```
### 算法七十五、指针算法
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b;
    cin>>a>>b;
    int *c = &a, *d = &b, ans;
    ans = *c + *d;
    cout << ans << endl;
}
```
### 算法七十六、vector
```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int main() {
    int x = 0;
    while (cin>>x) v.push_back(x);
    int ans = 0;
    for (int i = 0; i < v.size(); i++) ans += v[i];
    cout << ans;
    return 0;
}
```
### 算法七十七、queue
```cpp
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main() {
    int x;
    while (cin>>x) q.push(x);
    int ans = 0;
    while (q.size()) ans += q.front(), q.pop();
    cout << ans;
    return 0;
}
```
### 算法七十八、deque
```cpp
#include <bits/stdc++.h>
using namespace std;
deque<int> a, b;
int main() {
    int x;
    while (cin>>x) a.push_front(x);
    int ans = 0;
    while (a.size()) ans += a.back(), b.push_back(a.back()), a.pop_back();
    int res = 0;
    while (b.size()) res += b.front(), b.pop_front();
    if (ans == res) cout << (ans + res) / 2;
    return 0;
}
```
### 算法七十九、list
```cpp
#include <bits/stdc++.h>
using namespace std;
list<int> a, b;
int main() {
    int x;
    while (cin>>x) a.push_front(x);
    int ans = 0;
    while (a.size()) b.push_back(a.back()), ans += a.back(), a.pop_back();
    int res = 0;
    while (b.size()) res += b.front(), b.pop_front();
    if (ans == res) cout << (ans + res) / 2;
    return 0;
}
```
### 算法八十、map
```cpp
#include <bits/stdc++.h>
using namespace std;
map<int, string> m;
int main() {
    int x = 0;
    while (cin>>x) m[x] = "老子不会老子WA行了吧？？？";
    int ans = 0;
    for (auto iter = m.begin(); iter != m.end(); ++iter) {
        ans += iter->first;
    }
    cout << ans;
    return 0;
}
```
### 算法八十一、set
```cpp
#include <bits/stdc++.h>
using namespace std;
set<int> s;
int main() {
    int x = 0;
    while (cin>>x) s.insert(x);
    int ans = 0;
    for (auto iter = s.begin(); iter != s.end(); ++iter) {
        ans += *iter; 
    }
    cout << ans;
    return 0;
}
```
### 算法八十二、pair
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    pair<int, int> a[110];
    int x = 0, c = 0, t = 1;
    while (cin>>x) {
        if (c == 0) a[t].first = x, c = 1;
        else a[t].second = x, t++, c = 0;
    }
    int ans = 0;
    for (int i = 1; i <= 100; i++) {
        ans += a[i].first + a[i].second;
    }
    cout << ans;
    return 0;
}
```
### 算法八十三、stack
```cpp
#include <bits/stdc++.h>
using namespace std;
stack<int> s;
int main() {
    int x = 0;
    while (cin>>x) s.push(x);
    int ans = 0;
    while (s.size()) ans += s.top(), s.pop();
    cout << ans;
    return 0;
}
```

### 算法八十四、priority_queue
```cpp
#include <bits/stdc++.h>
using namespace std;
priority_queue<int> q;
int main() {
    int x = 0;
    while (cin>>x) q.push(x);
    int ans = 0;
    while (q.size()) ans += q.top(), q.pop();
    cout << ans;
    return 0;
}
```
### 算法八十五、不用变量
```cpp
#include <iostream>
using namespace std;
int main ()
{
    cin >> *new int () >> *new int ();
    cout << *(new int () - 16) + *(new int () - 16);
}
```
### 算法八十六、点分治
```cpp
#include<bits/stdc++.h>
#define ll long long
#define T(x) ((x)%mod)
using namespace std;
const int N=2e5+5,mod=1e9+7;
int n,a[N],root,mn,siz[N];
ll ans,cnt1[2],cnt2[2];
int h[N],e[N<<1],ne[N<<1],idx;
bool vis[N];
void add(int x,int y)
{
    e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void dfs1(int x,int fa,int num)
{
    int mxp=0;
    siz[x]=1;
    for(int i=h[x];~i;i=ne[i])
    {
        int y=e[i];
        if(y==fa||vis[y]) continue;
        dfs1(y,x,num);
        siz[x]+=siz[y];
        mxp=max(mxp,siz[y]);
    }
    mxp=max(mxp,num-siz[x]);
    if(mxp<mn) mn=mxp,root=x;
}
void dfs2(int x,int fa,int par,ll val)
{
    cnt1[par]++,cnt2[par]=T(cnt2[par]+val);
    for(int i=h[x];~i;i=ne[i])
    {
        int y=e[i];
        if(y==fa||vis[y]) continue;
        if(par) dfs2(y,x,0,val+a[y]);
        else dfs2(y,x,1,val-a[y]);
    }
}
int calc(int x,int par,ll val,ll p)
{
    cnt1[0]=cnt2[0]=cnt1[1]=cnt2[1]=0;
    dfs2(x,0,par,val);
    cnt2[1]*=-1;
    return T((cnt1[0]*cnt2[0]+cnt1[1]*cnt2[1])*2+
           p*T(cnt1[0]*cnt1[0]-cnt1[1]*cnt1[1]));
}
void dfs3(int x,int num)
{
    vis[x]=1;
    ans=T(ans+calc(x,0,0,a[x]));
    for(int i=h[x];~i;i=ne[i])
    {
        int y=e[i];
        if(vis[y]) continue;
        ans=T(ans-calc(y,1,-a[y],a[x]));
        mn=1e9;
        dfs1(y,0,siz[y]),dfs3(root,siz[y]);
    }
}
int main()
{
    memset(h,-1,sizeof(h));
    int aa,bb;
    cin>>aa>>bb;
    a[1]=0,a[2]=aa,a[3]=bb;
    add(1,2),add(2,1);
    add(1,3),add(3,1); 
    mn=1e9,root=0;
    dfs1(1,0,n),dfs3(root,n);
    printf("%d\n",((ans+mod)%mod)/3);
}
```
### 算法八十七、FHQ-Treap+队列优化空间+分治优化Build
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,INF=0x3f3f3f3f;
struct BST
{
    int l,r,x,siz,sum,res,pre,suf,chg;
    bool f,cgd;
}a[N];
int n,m,idx,root,b[N];
queue<int> q;
int New(int x)
{
    idx=q.front(),q.pop();
    a[idx].l=a[idx].r=a[idx].cgd=a[idx].chg=0;
    a[idx].x=a[idx].sum=a[idx].res=x;
    a[idx].pre=a[idx].suf=max(x,0);
    a[idx].siz=1;
    return idx;
}
void PushUp(int u)
{
    a[u].siz=a[a[u].l].siz+a[a[u].r].siz+1;
    a[u].sum=a[u].x+a[a[u].l].sum+a[a[u].r].sum;
    a[u].pre=max(a[a[u].l].pre,a[a[u].l].sum+a[u].x+a[a[u].r].pre);
    a[u].suf=max(a[a[u].r].suf,a[a[u].r].sum+a[u].x+a[a[u].l].suf);
    a[u].res=max(a[u].x,a[a[u].l].suf+a[u].x+a[a[u].r].pre);
    if(a[u].l) a[u].res=max(a[u].res,a[a[u].l].res);
    if(a[u].r) a[u].res=max(a[u].res,a[a[u].r].res);
}
void Reverse(int u)
{
    swap(a[u].l,a[u].r);
    swap(a[u].pre,a[u].suf);
    a[u].f^=1;
}
void Change(int u,int x)
{
    a[u].x=a[u].chg=x;
    a[u].sum=a[u].siz*x;
    a[u].pre=a[u].suf=max(a[u].sum,0);
    a[u].res=max(x,a[u].sum);
    a[u].cgd=1;
}
void PushDown(int u)
{
    if(a[u].f)
    {
        Reverse(a[u].l);
        Reverse(a[u].r);
        a[u].f=0;
    }
    if(a[u].cgd)
    {
        Change(a[u].l,a[u].chg);
        Change(a[u].r,a[u].chg);
        a[u].cgd=0;
    }
}
int Merge(int u,int v)
{
    if(!u||!v) return u+v;
    if(90000008%(a[u].siz+a[v].siz)<a[u].siz)
    {
        PushDown(u);
        a[u].r=Merge(a[u].r,v);
        PushUp(u);
        return u;
    }
    PushDown(v);
    a[v].l=Merge(u,a[v].l);
    PushUp(v);
    return v;
}
void Split(int u,int x,int &l,int &r)
{
    if(!u)
    {
        l=r=0;
        return;
    }
    PushDown(u);
    if(a[a[u].l].siz<x) l=u,Split(a[u].r,x-a[a[u].l].siz-1,a[u].r,r);
    else r=u,Split(a[u].l,x,l,a[u].l);
    PushUp(u);
}
int Build(int l,int r)
{
    if(l==r) return New(b[l]);
    int mid=(l+r)>>1;
    return Merge(Build(l,mid),Build(mid+1,r));
}
void Delete(int u)
{
    if(!u) return;
    q.push(u);
    Delete(a[u].l);
    Delete(a[u].r);
}
int main()
{
    for(int i=1;i<=5e5;i++) q.push(i);
    scanf("%d%d",&b[1],&b[2]);
    root=Build(1,2);
    int x=0,y=0,z=0;
    Split(root,0,x,y);
    Split(y,2,y,z);
    a[y].f^=1;
    root=Merge(x,Merge(y,z));
    Split(root,0,x,y);
    Split(y,2,y,z);
    cout<<a[y].res<<endl;
    root=Merge(x,Merge(y,z));
}
```
### 算法八十八、文艺平衡树(FHQ-Treap实现)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=(1ll<<31)-1;
struct BST
{
    int l,r,x,p,siz;
    bool f;
}a[N];
int n,m,idx,root;
int New(int x)
{
    a[++idx].x=x;
    a[idx].p=rand();
    a[idx].siz=1;
    return idx;
}
void PushUp(int u)
{
    a[u].siz=a[a[u].l].siz+a[a[u].r].siz+1;
}
void PushDown(int u)
{
    swap(a[u].l,a[u].r);
    if(a[u].l) a[a[u].l].f^=1;
    if(a[u].r) a[a[u].r].f^=1;
    a[u].f=0;
}
int Merge(int u,int v)
{
    if(!u||!v) return (u?u:v);
    if(a[u].p<a[v].p)
    {
        if(a[u].f) PushDown(u);
        a[u].r=Merge(a[u].r,v);
        PushUp(u);
        return u;
    }
    if(a[v].f) PushDown(v);
    a[v].l=Merge(u,a[v].l);
    PushUp(v);
    return v;
}
void Split(int u,int x,int &l,int &r)
{
    if(!u)
    {
        l=r=0;
        return;
    }
    if(a[u].f) PushDown(u);
    if(a[a[u].l].siz<x)
        l=u,Split(a[u].r,x-a[a[u].l].siz-1,a[u].r,r);
    else r=u,Split(a[u].l,x,l,a[u].l);
    PushUp(u);
}
int main()
{
    cin>>n>>m;
    root=Merge(root,New(n));
    root=Merge(root,New(m));
    int x=0,y=0,z=0;
    Split(root,0,x,y);
    Split(y,2,y,z);
    a[y].f^=1;
    root=Merge(x,Merge(y,z));
    Split(root,0,x,y);
    Split(y,2,y,z);
    cout<<a[1].x+a[2].x<<endl;
    root=Merge(x,Merge(y,z));
}
```
### 算法八十九、EXCRT
```cpp
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL i,n,x,y;
LL a[3],b[3];
LL time_mod(LL a,LL b,LL p)
{
    LL ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%p;
        a=(a*2)%p;
        b>>=1;
    }
    return ans;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    LL gcd=exgcd(b,a%b,x,y),temp;
    temp=x;
    x=y;
    y=temp-a/b*y;
    return gcd;
}
LL calc()
{
    LL x,y,ans=a[1],p=b[1];
    for(int i=2;i<=n;i++)
    {
        LL at=p,bt=b[i],ct=(a[i]-ans%bt+bt)%bt,gcd=exgcd(at,bt,x,y),lm=bt/gcd;
        x=time_mod(x,ct/gcd,lm);
        ans+=x*p;
        p*=lm;
        ans=(ans%p+p)%p;
    }
    return (ans%p+p)%p;
}
int main()
{
    n=2;
    cin>>x>>y;
    b[1]=x*2;
    a[1]=(b[1]-x+y)%b[1];
    b[2]=y*2;
    a[2]=(b[2]-y+x)%b[2];
    cout<<calc();
}
```
### 算法九十、Treap（平衡树）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=(1ll<<31)-1;
struct BST
{
    int l,r,x,p,siz,cnt;
}a[N];
int q,p,idx,root;
int New(int x)
{
    a[++idx].x=x;
    a[idx].p=rand();
    a[idx].siz=a[idx].cnt=1;
    return idx;
}
void Update(int u)
{
    a[u].siz=a[a[u].l].siz+a[a[u].r].siz+a[u].cnt;
}
void Build()
{
    New(-INF),New(INF);
    root=1,a[1].r=2;
    Update(root);
}
int GetRank(int u,int x)
{
    if(!u) return 0;
    if(x==a[u].x) return a[a[u].l].siz;
    if(x<a[u].x) return GetRank(a[u].l,x);
    else return GetRank(a[u].r,x)+a[a[u].l].siz+a[u].cnt;
}
int GetValue(int u,int x)
{
    if(!u) return INF;
    if(a[a[u].l].siz>=x) return GetValue(a[u].l,x);
    if(a[a[u].l].siz+a[u].cnt>=x) return a[u].x;
    return GetValue(a[u].r,x-a[a[u].l].siz-a[u].cnt);
}
void zig(int &u)
{
    int v=a[u].l;
    a[u].l=a[v].r,a[v].r=u,u=v;
    Update(a[u].r),Update(u);
}
void zag(int &u)
{
    int v=a[u].r;
    a[u].r=a[v].l,a[v].l=u,u=v;
    Update(a[u].l),Update(u);
}
void Insert(int &u,int x)
{
    if(!u)
    {
        u=New(x);
        return;
    }
    if(x==a[u].x)
    {
        a[u].cnt++,Update(u);
        return;
    }
    if(x<a[u].x){
        Insert(a[u].l,x);
        if(a[u].p<a[a[u].l].p)
            zig(u);
    } else{
        Insert(a[u].r,x);
        if(a[u].p<a[a[u].r].p)
            zag(u);
    }
    Update(u);
}
int GetPrev(int u,int x,int res)
{
    if(a[u].x>=x){
        if(!a[u].l) return res;
        return GetPrev(a[u].l,x,res);
    }
    if(!a[u].r) return a[u].x;
    return GetPrev(a[u].r,x,a[u].x);
}
int GetNext(int u,int x,int res)
{
    if(a[u].x<=x){
        if(!a[u].r) return res;
        return GetNext(a[u].r,x,res);
    }
    if(!a[u].l) return a[u].x;
    return GetNext(a[u].l,x,a[u].x);
}
void Remove(int &u,int x)
{
    if(!u) return;
    if(x==a[u].x){
        if(a[u].cnt>1){
            a[u].cnt--,Update(u);
            return;
        }
        if(a[u].l||a[u].r){
            if(!a[u].r||a[a[u].l].p>a[a[u].r].p)
                zig(u),Remove(a[u].r,x);
            else zag(u),Remove(a[u].l,x);
            Update(u);
            return;
        }
        u=0;
        return;
    }
    if(x<a[u].x) Remove(a[u].l,x);
    else Remove(a[u].r,x);
    Update(u);
}
int main()
{
    cin>>q>>p;
    if(q>p) swap(q,p);
    Build();
    Insert(root,q);Insert(root,p);
    Remove(root,p);Insert(root,p);
    cout<<(GetPrev(root,p,-INF)+GetNext(root,q,INF)+GetValue(root,GetRank(root,q)+1)+GetValue(root,GetRank(root,p)+1))/2<<endl;
}
```
### 算法九十一、BST（二叉查找树）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,INF=(1ll<<31)-1;
struct BST
{
    int l,r,x,siz,cnt;
}a[N];
int q,p,idx,root;
int New(int x){
    a[++idx].x=x,a[idx].siz=a[idx].cnt=1;
    return idx;
}
void Build()
{
    a[++idx].x=-INF,a[++idx].x=INF;
    root=1,a[1].r=2;
}
int GetRank(int u,int x)
{
    if(!u) return 0;
    if(x==a[u].x) return a[a[u].l].siz;
    if(x<a[u].x) return GetRank(a[u].l,x);
    else return GetRank(a[u].r,x)+a[a[u].l].siz+a[u].cnt;
}
int GetValue(int u,int x)
{
    if(!u) return INF;
    if(a[a[u].l].siz>=x) return GetValue(a[u].l,x);
    if(a[a[u].l].siz+a[u].cnt<x) return GetValue(a[u].r,x-a[a[u].l].siz-a[u].cnt);
    return a[u].x;
}
void Insert(int &u,int x)
{
    if(!u)
    {
        u=New(x);
        return;
    }
    a[u].siz++;
    if(x==a[u].x)
    {
        a[u].cnt++;
        return;
    }
    if(x<a[u].x) Insert(a[u].l,x);
    else Insert(a[u].r,x);
}
int GetPrev(int u,int x,int res)
{
    if(a[u].x>=x)
    {
        if(!a[u].l) return res;
        return GetPrev(a[u].l,x,res);
    }
    if(!a[u].r) return a[u].x;
    return GetPrev(a[u].r,x,a[u].x);
}
int GetNext(int u,int x,int res)
{
    if(a[u].x<=x)
    {
        if(!a[u].r) return res;
        return GetNext(a[u].r,x,res);
    }
    if(!a[u].l) return a[u].x;
    return GetNext(a[u].l,x,a[u].x);
}
int main()
{
    cin>>q>>p;
    if(q>p) swap(q,p);
    Build();
    Insert(root,q);
    Insert(root,p);
    cout<<(GetPrev(root,p,-INF)+GetNext(root,q,INF)+GetValue(root,GetRank(root,q)+1)+GetValue(root,GetRank(root,p)+1))/2<<endl;
}
```
### 算法九十二、Dijkstra 堆优化
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], nxt[M], d[N];
bool st[N];
int n, m, tot;
priority_queue< pair<int, int> > q;
void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
    memset(d, 0x3f3f3f3f, sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    q.push({0, 1});
    while (q.size()) {
        int x = q.top().second;
        q.pop();
        if (st[x]) continue;
        st[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
}
int main() {
    n = 3, m = 2;
    for (int i =1 ; i <= m; i++) {
        int x = i, y = i + 1, z;
        scanf("%d", &z);
        add(x, y, z);
    }
    dijkstra();
    if (d[n] != 0x3f3f3f3f) cout<<d[n];
    else puts("-1");
}
```
### 算法九十三、FFT
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct complex
{
    double a,b;
    complex(double x=0,double y=0)
    {
        a=x,b=y;
    }
    complex operator + (const complex& t) const
    {
        return complex(a+t.a,b+t.b);
    }

complex operator - (const complex& t) const
    {
        return complex(a - t.a, b - t.b);
    }

complex operator * (const complex& t) const
    {
        return complex(a * t.a - b * t.b, a * t.b + b * t.a);
    }
} cp;

const int N = 18;
const double pi = 2 * acos(-1);
char f[N], g[N], c[N];
int n, m, r[N];
cp a[N], w[N];

int log_2(int x)
{
    int res = 0;
    if (x & 0xffff0000) res += 16, x >>= 16;
    if (x & 0xff00) res += 8, x >>= 8;
    if (x & 0xf0) res += 4, x >>= 4;
    if (x & 0xc) res += 2, x >>= 2;
    if (x & 2) res ++ ;

return res;
}

void init()
{
    m += n;
    int bit = log_2(m);

n = 1 << bit + 1;

for (int i = 0; i < n; i ++ ) r[i] = r[i >> 1] >> 1 | (i & 1) << bit;

cp t(cos(pi / n), sin(pi / n));
    w[0].a = 1;

for (int i = 1; i < n; i ++ ) w[i] = w[i - 1] * t;
}

void swap(cp& a, cp& b) 
{
    static cp t;
    t = a, a = b, b = t;
}

void FFT(bool type)
{
    for (int i = 0; i < n; i ++ ) if (i < r[i]) swap(a[i], a[r[i]]);

static cp x, y;
    for (int len = 2; len <= n; len <<= 1)
        for (int l = 0; l < n; l += len)
            for (int i = 0, j = len >> 1; j < len; i ++ , j ++ )
            {
                x = a[l + i], y = w[n / len * i];
                if (type) y = y * a[l + j];
                else y = cp(y.a, -y.b) * a[l + j];

a[l + i] = x + y, a[l + j] = x - y;
            }
}

int main()
{
    scanf("%s\n%s", f, g);
    n = strlen(f) - 1, m = strlen(g) - 1;

for (int i = n; ~i; i -- ) a[i].a = (double)(f[n - i] ^ 48);
    for (int i = m; ~i; i -- ) a[i].b = (double)(g[m - i] ^ 48);

init();

FFT(1);
    for (int i = 0; i < n; i ++ ) a[i] = a[i] * a[i];
    FFT(0);

int t = 0;
    for (int i = 0; i <= m; i ++ )
    {
        t += (int)(a[i].b / n / 2.0 + 0.5);
        c[i] = t % 10 ^ 48, t /= 10;
    }

int res = 0;
    if (t) res = res * 10 + t;
    for (int i = m; i >= 0; i -- ) res = res * 10 + (c[i] - '0');

n = strlen(f) - 1, m = strlen(g) - 1;
    int a = 0, b = 0;
    for (int i = 0; i <= n; i ++ ) a = a * 10 + (f[i] - '0'); 
    for (int i = 0; i <= m; i ++ ) b = b * 10 + (g[i] - '0');
    printf("%d\n", res - a * b + a + b);

return 0;
}
```

### 算法九十四、珂朵莉树
```cpp
#include <iostream>
#include <cstring>
#include <set>

using namespace std;

const int N = 35;

struct Node
{
    int l, r;
    mutable int v;

bool operator < (const Node& t) const
    {
        return l < t.l;
    }
};

typedef set<Node>::iterator iter;

set<Node> ODT;
int a, b;

iter split(int x)
{
    if (x > 2) return ODT.end();
    auto it = -- ODT.upper_bound({x, 0, 0});

if (it -> l == x) return it;

int l = it -> l, r = it -> r, v = it -> v;
    ODT.erase(it);
    ODT.insert({l, x - 1, v});
    return ODT.insert({x, r, v}).first;
}

void assign(int l, int r, int x)
{
    auto itr = split(r + 1), itl = split(l);
    ODT.erase(itl, itr);
    ODT.insert({l, r, x});
}

int query(int l, int r)
{
    static int cnt[N] = {0};
    memset(cnt, 0, sizeof cnt);

auto itr = split(r + 1), itl = split(l); int res = 0;
    for (; itl != itr; itl ++ ) res = res + ((itl -> r) - (itl -> l) + 1) * (itl -> v);
    return res;
}

int main()
{
    scanf("%d%d", &a, &b);
    ODT.insert({1, 2, 0});
    assign(1, 1, a), assign(2, 2, b);
    printf("%d\n", query(1, 2));

return 0;
}
```
### 算法九十五、64位0.5MB虚拟机
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned int
#define N 65536
int memory[N];
ull code[N] = {
0x0000000000000000, 0x0000000000000001, 0x5000000000010002, 0x1000000000000002, 0xf000000000000000
};
/*
0 Input
1 Output
2 Write
3 Copy
4 Calculate (& | ~ ^ << >>)
5 Calculate (+ - * / %)
6 Goto
7 If-goto
8 x++
9 x--
f Exit
*/
signed main()
{
	for(int i=0;;i=(i+1)%N)
	{
		int op=code[i]>>60;
		if(op==0)		//Input
		{
			int p=code[i]&65535;
			cin >> memory[ (code[i]>>56)&1 ? memory[p] : p ];
		}
		else if(op==1)	//Output
		{
			int p=code[i]&65535, val = memory[ (code[i]>>56)&1 ? memory[p] : p ];
			if((code[i]>>57)&1)
			{
				cout<<char(val&127);
			}
			else
			{
				cout<<val;
			}
		}
		else if(op==2)	//Write
		{
			int p = (code[i]>>32)&65535, val = code[i]&((1ll<<32)-1);
			memory[ (code[i]>>56)&1 ? memory[p] : p ] = val;
		}
		else if(op==3)	//Copy
		{
			int pf = (code[i]>>16)&65535, pt = code[i]&65535;
			int val = memory[ (code[i]>>55)&1 ? memory[pf] : pf ];
			memory[ (code[i]>>56)&1 ? memory[pt] : pt ] = val;
		}
		else if(op==4)	//Calculate (& | ~ ^ << >>)
		{
			int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
			int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
			val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ], val3;
			int op2 = (code[i]>>52)&15;
			if(op2==0)
			{
				val3=val1&val2;
			}
			else if(op2==1)
			{
				val3=val1|val2;
			}
			else if(op2==2)
			{
				val3=~val2;
			}
			else if(op2==3)
			{
				val3=val1^val2;
			}
			else if(op2==4)
			{
				val3=((val2>>6)?0:val1<<val2);
			}
			else
			{
				val3=((val2>>6)?0:val1>>val2);
			}
			memory[ (code[i]>>56)&1 ? memory[p3] : p3 ] = val3;
		}
		else if(op==5)	//Calculate (+ - * / %)
		{
			//想要乘方的建议自己写一个快速幂, 应该是能写的 
			int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
			int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
			val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ], val3;
			int op2 = (code[i]>>52)&15;
			if(op2==0)
			{
				val3=val1+val2;
			}
			else if(op2==1)
			{
				val3=val1-val2;
			}
			else if(op2==2)
			{
				val3=val1*val2;
			}
			else if(op2==3)
			{
				val3=(val2?val1/val2:0);
			}
			else
			{
				val3=(val2?val1%val2:0);
			}
			memory[ (code[i]>>56)&1 ? memory[p3] : p3 ] = val3;
		}
		else if(op==6)	//Goto
		{
			int p=code[i]&65535;
			i = (code[i]>>56)&1 ? memory[p] : p;
			i = (i+N-1)%N;
		}
		else if(op==7)	//If-goto (> < == >= <= !=)
		{
			int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
			int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
			val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ];
			int op2 = (code[i]>>52)&15;
			bool flag;
			if(op2==0)
			{
				flag=(val1>val2);
			}
			else if(op2==1)
			{
				flag=(val1<val2);
			}
			else if(op2==2)
			{
				flag=(val1==val2);
			}
			else if(op2==3)
			{
				flag=(val1>=val2);
			}
			else if(op2==4)
			{
				flag=(val1<=val2);
			}
			else
			{
				flag=(val1!=val2);
			}
			if(flag)
			{
				i = (code[i]>>56)&1 ? memory[p3] : p3;
				i = (i+N-1)%N;
			}
		}
		else if(op==8)	//x++
		{
			int p=code[i]&65535;
			memory[ (code[i]>>56)&1 ? memory[p] : p ]++;
		}
		else if(op==9)	//x--
		{
			int p=code[i]&65535;
			memory[ (code[i]>>56)&1 ? memory[p] : p ]--;
		}
		else if(op==15)	//Exit
		{
			break;
		}
		else
		{
			cout<<"\n\nError: Invalid code\n\n";
		}
	}
	return 0;
}

```
### 算法九十六、64位8MB虚拟机
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned int
#define N 1048576
int memory[N],pos;
string code[N]={
"input 0", "input 1", "calc add 0 1 2", "output int 2", "exit"
};
string readStr(int x,int y)	// 从 code[x][y] 开始读取一个字符串, 读到空格为止 
{
	pos=y;
	string ret="";
	int len=code[x].length();
	while(pos<len && code[x][pos]==' ')
	{
		++pos;
	}
	while(pos<len && code[x][pos]!=' ')
	{
		ret=ret+code[x][pos++];
	}
	return ret;
}
int readInt(int x,int y)	// 从 code[x][y] 开始读取一个整数, 读到非数字为止 
{
	pos=y;
	int ret=0, len=code[x].length();
	bool f=0;
	while(pos<len && !isdigit(code[x][pos]))
	{
		if(code[x][pos]=='-')
		{
			f=1;
		}
		++pos;
	}
	while(pos<len && isdigit(code[x][pos]))
	{
		ret=(ret<<3)+(ret<<1)+(code[x][pos++]^48);
	}
	return f?-ret:ret;
}
signed main()
{
	for(int i=0;;i=(i+1)%N)
	{
		string op=readStr(i,0);
		if(op=="input")
		{
			int x=readInt(i,pos);
			cin>>memory[x];
		}
		else if(op=="output")
		{
			string mode=readStr(i,pos);
			if(mode=="int")
			{
				int x=readInt(i,pos);
				cout<<memory[x];
			}
			else if(mode=="char")
			{
				int x=readInt(i,pos);
				cout<<char(memory[x]%128);
			}
			else
			{
				cout<<"\n\nError: Invalid Code\n\n";
				break;
			}
		}
		else if(op=="write")
		{
			int x=readInt(i,pos), y=readInt(i,pos);
			memory[x]=y;
		}
		else if(op=="copy")
		{
			int x=readInt(i,pos), y=readInt(i,pos);
			memory[y]=memory[x];
		}
		else if(op=="calc")	// and or not xor add sub mul div mod
		{
			string mode=readStr(i,pos);
			int x=readInt(i,pos), y=readInt(i,pos), z=(mode=="not" ? 0 : readInt(i,pos));
			x=memory[x], y=memory[y];
			if(mode=="and")
			{
				memory[z]=x&y;
			}
			else if(mode=="or")
			{
				memory[z]=x|y;
			}
			else if(mode=="not")
			{
				memory[y]=~x;
			}
			else if(mode=="xor")
			{
				memory[z]=x^y;
			}
			else if(mode=="add")
			{
				memory[z]=x+y;
			}
			else if(mode=="sub")
			{
				memory[z]=x-y;
			}
			else if(mode=="mul")
			{
				memory[z]=x*y;
			}
			else if(mode=="div")
			{
				if(y==0)
				{
					cout<<"\n\nError: Division by Zero\n\n";
					break;
				}
				memory[z]=x/y;
			}
			else if(mode=="mod")
			{
				memory[z]=x%y;
			}
			else
			{
				cout<<"\n\nError: Invalid Code\n\n";
				break;
			}
		}
		else if(op=="goto")
		{
			int x=readInt(i,pos);
			i=x-1;
		}
		else if(op=="if")	// < > == <= >= !=
		{
			string mode=readStr(i,pos);
			int x=readInt(i,pos), y=readInt(i,pos), z=readInt(i,pos);
			x=memory[x], y=memory[y];
			if(mode=="<")
			{
				if(x<y)
				{
					i=z-1;
				}
			}
			else if(mode==">")
			{
				if(x>y)
				{
					i=z-1;
				}
			}
			else if(mode=="==")
			{
				if(x==y)
				{
					i=z-1;
				}
			}
			else if(mode=="<=")
			{
				if(x<=y)
				{
					i=z-1;
				}
			}
			else if(mode==">=")
			{
				if(x>=y)
				{
					i=z-1;
				}
			}
			else if(mode=="!=")
			{
				if(x!=y)
				{
					i=z-1;
				}
			}
			else
			{
				cout<<"\n\nError: Invalid Code\n\n";
				break;
			}
		}
		else if(op=="++")
		{
			int x=readInt(i,pos);
			memory[x]++;
		}
		else if(op=="--")
		{
			int x=readInt(i,pos);
			memory[x]--;
		}
		else if(op=="exit")
		{
			break;
		}
		else
		{
			cout<<"\n\nError: Invalid Code\n\n";
			break;
		}
	}
	return 0;
}

```
### 算法九十七、多项式乘法
```cpp
#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
const int N = 1e5 + 10, P = 998244353;
namespace IO {
	int rnt () {
		int x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
}
namespace POLY {
	const int N=3e5+10,P=998244353,g=3,invg=332748118;int rev[N],omega[2][N];
	std::mt19937 rnd (std::chrono::system_clock::now ().time_since_epoch ().count ());
	template<typename T1,typename T2>inline T1 add(T1 a,T2 b){return(a+=b)>=POLY::P?a-POLY::P:a;}template<typename T1,typename T2>inline void addi(T1&a,T2 b){(a+=b)>=POLY::P?a-=POLY::P:a;return;}template<typename T1,typename...Args>inline T1 add(T1 a,Args...b){return add(a,add(b...));}template<typename T1,typename...Args>inline void addi(T1&a,Args...b){addi(a,add(b...));return;}
	template<typename T1,typename T2>inline T1 sub(T1 a,T2 b){return(a-=b)<0?a+POLY::P:a;}template<typename T1,typename T2>inline void subi(T1&a,T2 b){(a-=b)<0?a+=POLY::P:a;return;}template<typename T1,typename...Args>inline T1 sub(T1 a,Args...b){return sub(a,add(b...));}template<typename T1,typename...Args>inline void subi(T1&a,Args...b){subi(a,add(b...));return;}
	template<typename T1,typename T2>inline T1 mul(T1 a,T2 b){return(1ll*a*b)%POLY::P;}template<typename T1,typename T2>inline void muli(T1&a,T2 b){a=mul(a,b);return;}template<typename T1,typename...Args>T1 inline mul(T1 a,Args...b){return mul(a,mul(b...));}template<typename T1,typename...Args>inline void muli(T1&a,Args...b){muli(a,mul(b...));return;}
	template<typename T1,typename T2>inline T1 FastPow(T1 a,T2 b){T1 ans=1;while(b){if(b&1)muli(ans,a);muli(a,a),b>>=1;}return ans;}template<typename T>inline T Inv(T a){return FastPow(a,POLY::P-2);}
	inline int PreWork(const int &n){int lim=1,l=0;while(lim<=n)lim<<=1,++l;_for(i,0,lim)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));omega[0][0]=omega[1][0]=1;omega[0][1]=FastPow(g,(POLY::P-1)/lim);omega[1][1]=FastPow(invg,(POLY::P-1)/lim);_for(i,2,lim)omega[0][i]=mul(omega[0][i-1],omega[0][1]),omega[1][i]=mul(omega[1][i-1],omega[1][1]);return lim;}
	namespace Cipolla{int _i_;class Complex{public:int real,imag;Complex()=default;Complex(int _real,int _imag):real(_real),imag(_imag){}inline void operator*=(Complex b){int tmp1=add(mul(real,b.real),mul(imag,b.imag,_i_));int tmp2=add(mul(real,b.imag),mul(imag,b.real));real=tmp1,imag=tmp2;return;}};inline int FastPow(Complex a,int b){Complex ans(1,0);while(b){if(b&1)ans*=a;a*=a,b>>=1;}return ans.real;}inline int Cipolla(int n){if (!n)return 0;if (POLY::FastPow(n,(POLY::P-1)>>1)==POLY::P-1)return -1;int a;while(a){a=rnd()%POLY::P,_i_=sub(mul(a,a),n);if(POLY::FastPow(_i_,(POLY::P-1)>>1)==POLY::P-1)break;}return FastPow(Complex(a,1),(POLY::P+1)>>1);}};
	template<typename T = int> class Poly {
	private:std::vector<T>A;
	public:
		Poly()=default;Poly(int len){A.resize(len);return;}Poly(std::vector<T> _A):A(_A){}Poly(typename std::vector<T>::iterator bg,typename std::vector<T>::iterator ed){A.assign(bg,ed);return;}Poly(typename std::vector<T>::iterator bg,int len){A.assign(bg,bg+len);return;}
		inline T& operator[](const int& x){return A[x];}inline T operator[](const int& x)const{return A[x];}
		inline int deg()const{return A.size()-1;}inline int len()const{return A.size();}inline Poly Resize(int len){A.resize(len);return(*this);}
		inline typename std::vector<T>::iterator begin(){return A.begin();}inline typename std::vector<T>::iterator end(){return A.end();}inline T* data(){return A.data();}
		inline void Cover(typename std::vector<T>::iterator bg,typename std::vector<T>::iterator ed){A.assign(bg,ed);return;}inline void Cover(typename std::vector<T>::iterator bg,int len){A.assign(bg,bg+len);return;}
		inline Poly Slice(int n){return n<=0?Poly(0):(n<len()?Poly(begin(),begin()+n+1):Poly(*this).Resize(n+1));}inline void Clear(){std::vector<T>().swap(A);return;}
		inline void NTT(int lim,bool type){Resize(lim);_for(i,0,lim-1)if(i<rev[i])std::swap(A[i],A[rev[i]]);for(int mid=1,t=lim>>1;mid<lim;mid<<=1,t>>=1){for(int R=mid<<1,j=0;j<lim;j+=R){_for(k,0,mid-1){T x=A[j+k],y=mul(omega[type][t*k],A[j+mid+k]);A[j+k]=add(x,y),A[j+mid+k]=sub(x,y);}}}if(type==1){T inv_lim=FastPow(lim,POLY::P-2);_for(i,0,lim-1)A[i]=mul(A[i],inv_lim);}return;}
		friend inline Poly operator+(Poly F,Poly G){F.Resize(std::max(F.len(),G.len()));_for(i,0,G.deg())addi(F[i],G[i]);return F;}inline Poly&operator+=(Poly G){Resize(std::max(len(),G.len()));_for(i,0,G.deg())addi(A[i],G[i]);return(*this);}
		friend inline Poly operator+(Poly F,T x){addi(F[0],x);return F;}friend inline Poly operator+(T x,Poly F){addi(F[0],x);return F;}inline Poly&operator+=(T x){addi(A[0],x);return(*this);}
		friend inline Poly operator-(Poly F,Poly G){F.Resize(std::max(F.len(),G.len()));_for(i,0,G.deg())subi(F[i],G[i]);return F;}inline Poly&operator-=(Poly G){Resize(std::max(len(),G.len()));_for(i,0,G.deg())subi(A[i],G[i]);return(*this);}
		friend inline Poly operator-(Poly F,T x){subi(F[0],x);return F;}friend inline Poly operator-(T x,Poly F){subi(F[0],x);return F;}inline Poly&operator-=(T x){subi(A[0],x);return(*this);}
		friend inline Poly operator*(Poly F,Poly G){int lim=PreWork(F.deg()+G.deg());F.NTT(lim,0),G.NTT(lim,0);_for(i,0,lim-1)muli(F[i],G[i]);F.NTT(lim,1);return F;}inline Poly&operator*=(Poly G){int lim=PreWork(deg()+G.deg());NTT(lim,0),G.NTT(lim,0);_for(i,0,lim-1)muli(A[i],G[i]);NTT(lim,1);return(*this);}
		friend inline Poly operator*(Poly F,T x){_for(i,0,F.deg())muli(F[i],x);return F;}friend inline Poly operator*(T x,Poly F){_for(i,0,F.deg())muli(F[i],x);return F;}inline Poly&operator*=(T x){_for(i,0,deg())muli(A[i],x);return(*this);}
		friend inline Poly operator/(Poly F,T x){x=POLY::Inv(x);return F*x;}friend inline Poly operator/(T x,Poly F){x=POLY::Inv(x);return F*x;}inline Poly&operator/=(T x){x=POLY::Inv(x);(*this)*=x;return(*this);}
		friend inline Poly operator<<(Poly F,int x){F.Resize(F.len()+x),memmove(F.data()+x,F.data(),4*(F.len()-x)),memset(F.data(),0,4*x);return F;}inline Poly&operator<<=(int x){Resize(len()+x),memmove(data()+x,data(),4*(len()-x)),memset(data(),0,4*x);return(*this);}
		friend inline Poly operator>>(Poly F,int x){if(x>=F.len())F.Clear();else memmove(F.data(),F.data()+x,4*(F.len()-x)),F.Resize(F.len()-x);return F;}inline Poly& operator>>=(int x){return x>=len()?(Clear(),*this):(memmove(data(),data()+x,4*(len()-x)),Resize(len()-x),*this);}
		inline Poly Inv(){Poly G(1);if(A.empty())return G;G[0]=POLY::Inv(A[0]);Poly t[2];for(int l=2;l<(len()<<1);l<<=1){t[0].Cover(A.begin(),std::min(l,len()));t[1]=G,t[1].Resize(std::min(l,len()));int lim=PreWork(t[0].deg()+t[1].deg()+1);t[0].NTT(lim,0),t[1].NTT(lim,0),G.Resize(lim);_for(i,0,lim-1)G[i]=mul(sub(2,mul(t[0][i],t[1][i])),t[1][i]);G.NTT(lim,1),G.Resize(l);}G.Resize(len());return G;}
		inline Poly Sqrt(){Poly G(1);G[0]=Cipolla::Cipolla(A[0]),G[0]=std::min(G[0],POLY::P-G[0]);T inv2=POLY::Inv(2);Poly t[2];for(int l=2;l<(len()<<1);l<<=1){t[1].Cover(A.begin(),std::min(l,len()));G.Resize(l),t[0]=G.Inv()*t[1];_for(i,0,l-1)G[i]=mul(t[0][i]+G[i],inv2);}G.Resize(len());return G;}
		inline Poly Differential(){Poly G(len()-1);_for(i,0,deg()-1)G[i]=mul(A[i+1],i+1);return G;}inline void iDifferential(){_for(i,0,deg()-1)A[i]=mul(A[i+1],i+1);A.resize(len()-1);return;}
		inline Poly Integral(){Poly G(len());for_(i,deg(),1)G[i]=mul(A[i-1],POLY::Inv(i));return G;}inline void iIntegral(){A.resize(len());for_(i,deg(),1)A[i]=mul(A[i-1],POLY::Inv(i));A[0]=0;return;}
		inline Poly Ln(){Poly G=(Differential()*Inv()).Integral();G.Resize(len());return G;}
		inline Poly Exp(){Poly G(1),H;G[0]=1;T inv2=POLY::Inv(2);for(int l=2;l<(len()<<1);l<<=1)G.Resize(l),H.Cover(A.begin(),std::min(l,len())),H-=G.Ln(),++H[0],G*=H;G.Resize(len());return G;}
		inline Poly Power(int k){if(A[0]!=0)return((((*this)*FastPow(A[0],P-2)).Ln())*k).Exp()*FastPow(A[0],k);else _for(i,0,deg())if(A[i]!=0)return((*this)>>i).Power(k)<<(i*k);return Poly(len());}
		inline Poly Power(pii k){if(A[0]!=0)return((((*this)*FastPow(A[0],P-2)).Ln())*k.second).Exp()*FastPow(A[0],k.first);else _for(i,0,deg())if(A[i]!=0)return(1ll*i*k.first)>len()?Poly(len()):((*this)>>i).Power(k)<<(i*k.first);return Poly(len());};
	};
} using poly = POLY::Poly<int>;
namespace SOLVE {
	using namespace IO;
	ll a, b, ans;
	poly A, B, C;
	void In () {
		a = rnt (), b = rnt ();
		return;
	}
	void Solve () {
		a += 1000'000'000ll;
		b += 1000'000'000ll;
		a *= 10, b *= 10;
		A.Resize (11), B.Resize (11);
		_for (i, 0, 10) {
			A[i] = a % 10, a /= 10;
			B[i] = b % 10, b /= 10;
		}
		A = A.Exp (), B = B.Exp ();
		C = A * B;
		C = C.Ln ();
		ll t = 1;
		_for (i, 0, std::min (10, C.deg ()))
			ans = ans + t * C[i], t *= 10;
		ans /= 10;
		ans -= 2000'000'000ll;
		return;
	}
	void Out () {
		printf ("%lld\n", ans);
		return;
	}
}
int main () {
	SOLVE::In ();
	SOLVE::Solve ();
	SOLVE::Out ();
	return 0;
}
```
### 算法九十八、虚函数大法
```cpp
#include<memory>
#include<cstdio>
using namespace std;
class Addable{
public:
    virtual ~Addable()=default;
    virtual int getValue() const=0;
    virtual unique_ptr<Addable>add(const Addable* other) const=0;
};
class Integer:public Addable{
    int value;
public:
    Integer(int val):value(val) {}
    int getValue() const override{
        return value;
    }
    std::unique_ptr<Addable> add(const Addable* other) const override{
        return std::make_unique<Integer>(value+other->getValue());
	}
};
class Calculator{
public:
    static unique_ptr<Addable> add(const Addable* a,const Addable* b){
        return a->add(b);
    }
};
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    unique_ptr<Addable>numA=make_unique<Integer>(a);
    unique_ptr<Addable>numB=make_unique<Integer>(b);
    unique_ptr<Addable>result=Calculator::add(numA.get(),numB.get());
    printf("%d",result->getValue());
}
```

正在渲染内容...