矩阵

矩乘(现在正确, 20191021)

const LL MOD = 1e9 + 7;
struct Matrix
{
    int row, col;
    LL val[33][33];
    void init0()
    {
        memset(val, 0, sizeof val);
    }
    void init1()
    {
        memset(val, 0, sizeof val);
        for (int i = 0; i < row; ++ i) val[i][i] = 1;
    }
    Matrix () {}
    Matrix (int _row, int _col)
    {
        row = _row; col = _col;
        memset(val, 0, sizeof val);
    }
    Matrix operator * (const Matrix B) const
    {
        Matrix C (row, B.col);
        for (int i = 0; i < row; ++ i)
        for (int j = 0; j < B.col; ++ j)
            for (int k = 0; k < col; ++ k)
            (C.val[i][j] += val[i][k] * B.val[k][j] % MOD) %= MOD/*, printf("%d%d += %lld * %lld\n", i, j, val[i][k], val[k][j])*/;
        return C;
    }
    void print()
    {
        for (int i = 0; i < row; ++ i, puts(""))
        for (int j = 0; j < col; ++ j) printf("%lld ", val[i][j]);
    }
} F, T; 
Matrix fpow(Matrix A, LL b)
{
    Matrix ret (A.row, A.col); ret.init1();
    while (b)
    {
    if (b & 1) b ^= 1, ret = ret * A;
    else b >>= 1, A = A * A;
    }
    return ret;
}

高斯消元

void Gauss(int n) 
{
    int r = 1, c = 1, maxr = 0;
    for (; r <= n && c <= n; ++ r, ++ c)
    {
        maxr = r;
        for (int i = r + 1; i <= n; ++ i) 
            if (fabs(a[i][c]) - fabs(a[maxr][c]) > EPS) maxr = i;
        if (maxr != r) 
            for (int i = 1; i <= n + 1; ++ i) // n + 1 !!!
                swap(a[r][i], a[maxr][i]);
        if (fabs(a[r][c]) < EPS) { -- r; continue; }
        for (int i = r + 1; i <= n; ++ i)
        {
            double k = a[i][c] / a[r][c];
            for (int j = c; j <= n + 1; ++ j) 
                a[i][j] = a[i][j] - k * a[r][j];
        }
    }
    -- r, -- c;
    for (int i = n; i >= 1; -- i)
    {
        int all0 = 1;
        for (int j = i; j <= n; ++ j) all0 &= (fabs(a[i][j]) < EPS);
        if (all0)
        {
            if (fabs(a[i][n + 1]) > EPS) nosol = true;
            else mulsol = true;
        }
        else 
        {
            for (int j = i + 1; j <= n; ++ j)
                a[i][n + 1] -= ansx[j] * a[i][j];
            ansx[i] = a[i][n + 1] / a[i][i];
        }
    }
} 

int main()
{
    n = in();
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n + 1; ++ j) 
            a[i][j] = in();
    Gauss(n);
    if (nosol) return puts("-1"), 0;
    if (mulsol) return puts("0"), 0;
    for (int i = 1; i <= n; ++ i) printf("x%d=%.2f\n", i, ansx[i]);
    return 0;
}

建图

int head[MAXN], nume;
struct Adj { int nex, to, w; } adj[MAXM << 1];
void addedge(int from, int to, int w)
{
    adj[++ nume] = (Adj) { head[from], to, w };
    head[from] = nume;
}
void link(int u, int v, int w) 
{ 
    addedge(u, v, w); addedge(v, u, w); 
} 

Tarjan 边双缩点

int dfn[MAXN], low[MAXN], idx;
bool cut[MAXM << 1];
void Tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++ idx;
    for (int i = head[u]; i != -1; i = adj[i].nex)
    {
    int v = adj[i].to;
    if ((i ^ 1) == fa) continue;
    if (dfn[v])
    {
        low[u] = min(low[u], dfn[v]);
    }
    else 
    {
        Tarjan(v, i);
        low[u] = min(low[u], low[v]);
    }
    }
    if (fa != -1 && low[u] > dfn[adj[fa ^ 1].to]) cut[fa] = cut[fa ^ 1] = true;
}

int bel[MAXN], cnt;
void DFS(int u, int fa)
{
    bel[u] = cnt;
    for (int i = head[u]; i != -1; i = adj[i].nex)
    {
    if ((i ^ 1) == fa || cut[i]) continue;
    int v = adj[i].to;
    if (bel[v]) continue;
    DFS(v, i);
    }
}

void traverse()
{
    for (int i = 1; i <= n; ++ i)
    if (!dfn[i])
        Tarjan(i, -1);
    for (int i = 1; i <= n; ++ i)
    if (!bel[i])
    {
        ++ cnt;
        DFS(i, -1);
    }
}

int dgr[MAXN];

int main()
{
    n = in();
    m = in();
    memset(head, -1, sizeof head);
    for (int i = 1; i <= m; ++ i)
    {
    int u = in(), v = in();
    link(u, v);
    }
    traverse();
    for (int u = 1; u <= n; ++ u)
    {
    for (int i = head[u]; i != -1; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (bel[u] == bel[v]) continue;
        ++ dgr[bel[u]], ++ dgr[bel[v]];
    }
    }
    int ans = 0;
    for (int i = 1; i <= cnt; ++ i)
    if (dgr[i] == 2) ++ ans;
    printf("%d\n", (ans + 1) / 2);
    return 0;
}

Tarjan 点双缩点

int idx, low[MAXN], dfn[MAXN];
bool cut[MAXN], nocut;
void Tarjan(int u, int fa)
{
    low[u] = dfn[u] = ++ idx;
    int ch = 0;
    for (int i = head[u]; i != -1; i = adj[i].nex)
    {
    if ((fa ^ 1) == i) continue;
    int v = adj[i].to;
    if (!dfn[v])
    {
        Tarjan(v, i);
        low[u] = min(low[u], low[v]);
        if (fa == -1) ++ ch;
        if ((fa != -1 && low[v] >= dfn[u]) || (fa == -1 && ch > 1))
        cut[u] = true, nocut = false;
    }
    else low[u] = min(low[u], dfn[v]);
    }
}

int top, stk[MAXN];
void DFS(int u, int fa)
{
    stk[++ top] = u;
    dfn[u] = 1; 
    if (cut[u]) return; 
    for (int i = head[u]; i != -1; i = adj[i].nex)
    {
    int v = adj[i].to;
    if ((fa ^ 1) == i || dfn[v]) continue;
//  printf("%d --> %d\n", u ,v);
    DFS(v, i);
    }
}

void init()
{
    nume = 0; 
    memset(head, -1, sizeof head);
    n = 0;
    ans1 = 0; ans2 = 1;
    idx = 0;
    memset(low, 0, sizeof low);
    memset(dfn, 0, sizeof dfn);
    memset(cut, false, sizeof cut);
    nocut = true;
}

int main()
{
    int t = 0;
    while (true)
    {
    m = in();
    if (!m) break;
    init();
    printf("Case %d: ", ++ t);
    for (int i = 1; i <= m; ++ i)
    {
        int u = in(), v = in();
        n = max(n, max(u, v));
        link(u, v);
    }
    for (int i = 1; i <= n; ++ i)
        if (!dfn[i]) Tarjan(i, -1);
    memset(dfn, 0, sizeof dfn);
    for (int i = 1; i <= n; ++ i)
        if (!cut[i] && !dfn[i])
        {
        int numcut = 0; top = 0;
        DFS(i, -1);
        for (int j = 1; j <= top; ++ j) if (cut[stk[j]]) ++ numcut, dfn[stk[j]] = 0;
        if (numcut == 1) ++ ans1, ans2 *= 1LL * (top - 1);

        }
    if (nocut) printf("2 %lld\n", 1LL * n * (n - 1) / 2);
    else printf("%lld %lld\n", ans1, ans2);
    }
    return 0;
}

Tarjan 强连通缩点

int dfn[MAXN], mn[MAXN], ind;
int stk[MAXN], top, belong[MAXN], cnt;
bool instk[MAXN];
void Tarjan(int u)
{
    dfn[u] = mn[u] = ++ ind;
    stk[++ top] = u; instk[u] = true;
    for (int i = g1.head[u]; i != -1; i = g1.adj[i].nex)
    {
        int v = g1. adj[i].to;
        if (dfn[v])
        {
            if (instk[v])
                mn[u] = min(mn[u], dfn[v]);
        }
        else 
        {
            Tarjan(v);
            mn[u] = min(mn[u], mn[v]);
        }
    }
    if (dfn[u] == mn[u])
    {
        ++ cnt;
        while (true)
        {
            belong[stk[top]] = u;
            instk[stk[top]] = false;
            -- top;
            if (stk[top + 1] == u) break;
        }
    }
}

01BFS

只有 01 两种边
如果边权为 1 , 则加入队尾, 否则队首

deque <int> q;
q.push_front(); q.push_back();
q.front(); q.pop_front();

二分图匹配匈牙利

bool DFS(int u)
{
    for (int i = head[u]; i; i = adj[i].nex)
    {
    int v = adj[i].to;
    if (vis[v]) continue;
    vis[v] = true;
    if (!maty[v] || (maty[v] && DFS(maty[v])))
    {
        matx[maty[v] = u] = v;
        return true;
    }
    }
    return false;
}
void Maxmatch()
{
    for (int i = 1; i <= n; ++ i)
    {
    if (matx[i]) continue;
    memset(vis, false, sizeof vis);
    DFS(i); 
    }
}

Dinic最大流

int lev[MAXN];
queue <int> Q;
bool BFS(int s, int t)
{
    while (!Q.empty()) Q.pop();
    memset(lev, 0, sizeof lev);
    lev[s] = 1;
    Q.push(s);
    while (!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for (int i = head[u]; i != -1; i = adj[i].nex)
        {
            int v = adj[i].to;
            if (!lev[v] && adj[i].w > 0)
            {
                lev[v] = lev[u] + 1;
                Q.push(v);
            }
        }
    }
    return lev[t] != 0;
}
LL DFS(int u, int t, LL flow)
{
    if (u == t) return flow;
    LL sum = 0;
    for (int &i = cur[u]; i != -1; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (lev[v] == lev[u] + 1 && adj[i].w)
        {
            LL f = DFS(v, t, min(flow, adj[i].w));
            adj[i].w -= f;
            adj[i ^ 1].w += f;
            sum += f;
            flow -= f;
        }
    }
    return sum;
}
LL Dinic()
{
    LL ret = 0;
    while ( BFS(s, t) )
    {
        copy(head, head + n + 1, cur);
        ret += DFS(s, t, INF);
    }
    return ret;
}

int main()
{
    nume = -1;
    memset(head, -1, sizeof head);
    n = in(), m = in(); s = in(), t = in();
    for (int i = 1; i <= m; i ++)
    {
        int u = in(), v = in();
        LL w = in();
        addedge(u, v, w);
        addedge(v, u, 0);
    }
    printf("%lld\n", Dinic());
    return 0;
}

费用流

LL flow[MAXN], dis[MAXN];
int pre[MAXN], pree[MAXN];
bool vis[MAXN];
queue <int> Q;
bool SPFA(int s, int t)
{
    memset(flow, 0x3f3f3f, sizeof flow);
    memset(dis , 0x3f3f3f, sizeof  dis);
    memset(vis,  0, sizeof vis);
    memset(pre, -1, sizeof pre);
    Q.push(s); vis[s] = true; dis[s] = 0; 
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop(); vis[u] = false;
        for (int i = head[u]; i != -1; i = adj[i].nex)
        {
            int v = adj[i].to;
            if (adj[i].w > 0 && dis[v] > dis[u] + adj[i].c)
            {
                dis[v] = dis[u] + adj[i].c;
                pre[v] = u; pree[v] = i;
                flow[v] = min(flow[u], adj[i].w);
                if (!vis[v])
                {
                    vis[v] = true;
                    Q.push(v);
                }
            }
        }
    }
    return pre[t] != -1;
}
void MCMF(int s, int t)
{
    while ( SPFA(s, t) )
    {
        maxflow += flow[t];
        mincost += flow[t] * dis[t];
        int now = t;
        while (now != s)
        {
            adj[pree[now]].w -= flow[t];
            adj[pree[now] ^ 1].w += flow[t];
            now = pre[now];
        }
    }
}

int main()
{
    memset(head, -1, sizeof head);
    nume = -1;
    n = in(), m = in(), s = in(), t = in();
    for (int i = 1; i <= m; i ++)
    {
        int u = in(), v = in();
        LL  w = in(), c = in();
        add_di(u, v, w, c);
        add_di(v, u, 0, -c);
    }
    MCMF(s, t);
    printf("%lld %lld\n", maxflow, mincost);
    return 0;
}

数据结构

线段树

注意: MAXT大小, 懒标记优先关系, 下传/更新

线段树(最值, 极差(后大-前小))

namespace Segt
{
#define ls (now << 1)
#define rs (now << 1 | 1)
#define mid ((l + r) >> 1)
    const int MAXT = MAXN << 2, INF = 1e7;
    int tag[MAXT];
    int mn[MAXT], mx[MAXT], del[MAXT];
    void pushup(int now)
    {
    mn[now] = min(mn[ls], mn[rs]);
    mx[now] = max(mx[ls], mx[rs]);
    del[now] = max(max(del[ls], del[rs]), mx[rs] - mn[ls]);
    }
    void addtag(int now, int c)
    {
    mn[now] += c; mx[now] += c;
    tag[now] += c;
    }
    void pushdown(int now)
    {
    if (tag[now] != 0) addtag(ls, tag[now]), addtag(rs, tag[now]);
    tag[now] = 0;
    }
    void build(int now, int l, int r)
    {
    tag[now] = 0;
    if (l == r)
    {
        addtag(now, pre[l]);
        return;
    }
    build(ls, l, mid); build(rs, mid + 1, r);
    pushup(now);
    }
    void modify(int now, int l, int r, int x, int y, int c)
    {
    if (x > r || y < l) return ;
    if (x <= l && r <= y) { addtag(now, c); return ; }
    pushdown(now);
    modify(ls, l, mid, x, y, c); modify(rs, mid + 1, r, x, y, c);
    pushup(now);
    }
    Ans query(int now, int l, int r, int x, int y)
    {
    if (x > r || y < l) return (Ans){ -INF, INF, -2 * INF };
    if (x <= l && r <= y) return (Ans){ mx[now], mn[now], del[now] };
    pushdown(now);
    Ans ql = query(ls, l, mid, x, y), qr = query(rs, mid + 1, r, x, y);
    return (Ans){ max(ql.mx, qr.mx), min(ql.mn, qr.mn), max(max(ql.del, qr.del), qr.mx - ql.mn) };
    }
    void modify(int x, int y, int c) { modify(1, 0, n, x, y, c); }
    Ans query(int x, int y) { return query(1, 0, n, x, y); }
#undef ls
#undef rs
#undef mid
}
using namespace Segt;

树链剖分(预处理)

int siz[MAXN], dep[MAXN];
int idx, dfn[MAXN], fa[MAXN], top[MAXN], hson[MAXN];
void DFS(int u, int ma)
{
    siz[u] = 1; fa[u] = ma;
    dep[u] = dep[ma] + 1;
    for (int i = head[u]; i; i = adj[i].nex)
    {
    int v = adj[i].to;
    if (v == ma) continue;
    DFS(v, u);
    siz[u] += siz[v];
    if (!hson[u] || siz[v] > siz[hson[u]]) hson[u] = v;
    }
}
void DFS2(int u, int t)
{
    dfn[u] = ++ idx;
    top[u] = t;
    if (hson[u]) DFS2(hson[u], t);
    for (int i = head[u]; i; i = adj[i].nex)
    {
    int v = adj[i].to;
    if (v == hson[u] || v == fa[u]) continue;
    DFS2(v, v);
    }
}

树链剖分(路径求和)

void modify(int x, int y, int v)
{
    while (top[x] != top[y])
    {
    if (dep[top[x]] > dep[top[y]]) swap(x, y);
    Segt::modify(1, 1, n, dfn[top[y]], dfn[y], v);
    y = fa[top[y]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    Segt::modify(1, 1, n, dfn[x], dfn[y], v);
}
LL query(int x, int y)
{
    LL ret = 0;
    while (top[x] != top[y])
    {
    if (dep[top[x]] > dep[top[y]]) swap(x, y);
    (ret += Segt::query(1, 1, n, dfn[top[y]], dfn[y])) %= MOD;
    y = fa[top[y]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    (ret += Segt::query(1, 1, n, dfn[x], dfn[y])) %= MOD;
    return ret;
}

主席树

BZOJ3653 [湖南集训]谈笑风生 < DFS序 + 权值主席树>

int dep[MAXN], siz[MAXN], dfn[MAXN], adfn[MAXN], odfn[MAXN], idx;
void DFS(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    siz[u] = 1;
    adfn[dfn[u] = ++ idx] = u;
    for (int i = head[u]; i; i = adj[i].nex)
    {
    int v=  adj[i].to;
    if (v == fa) continue;
    DFS(v, u);
    siz[u] += siz[v];
    }
    odfn[u] = idx;
}

namespace SEG
{
    const int MAXT = MAXN * 20; // 2 ^ 19 = 5e5;
    int root[MAXN], tot;
    int ch[MAXT][2], cnt[MAXT]; LL sum[MAXT];
#define mid ((l + r) >> 1)
#define ls (ch[now][0])
#define rs (ch[now][1])
    void update(int & now, int pre, int l, int r, int x, int v)
    {
    if (!now) now = ++ tot;
    cnt[now] = cnt[pre] + v;
    sum[now] = sum[pre] + 1ll * v * x;  
    if (l == r) ls = ch[pre][0], rs = ch[pre][1];
    else if (x <= mid)
    {
        rs = ch[pre][1];
        update(ls, ch[pre][0], l, mid, x, v);
    }
    else
    {
        ls = ch[pre][0];
        update(rs, ch[pre][1], mid + 1, r, x, v);
    }
    }
    void build(int n)
    {
    root[0] = 0;
    for (int i = 1; i <= n; ++ i)
        update(root[i], root[i - 1], 1, n, dep[adfn[i]], 1);
    }
    struct Info { int cnt; LL sum; } ;
    Info query(int now, int pre, int l, int r, int x, int y)
    {
    if (x > y || x > r || y < l) return (Info) { 0, 0 };
    if (x <= l && r <= y) return (Info) { cnt[now] - cnt[pre], sum[now] - sum[pre] } ;
    Info ql = query(ls, ch[pre][0], l, mid, x, y), qr = query(rs, ch[pre][1], mid + 1, r, x, y), ret;
    ret.cnt = ql.cnt + qr.cnt, ret.sum = ql.sum + qr.sum;
    return ret;
    }
#undef mid
#undef ls
#undef rs
}

FHQ-Treap

注意: 函数嵌套传参有顺序问题, 稳健为好

动态插点的LIS

const int MAXN = 1e5 + 10;

namespace Treap
{
    const int INF = 1e6;
    const int MAXT = MAXN; // note
    int root, tot;
    int ch[MAXT][2], pri[MAXN], siz[MAXN], val[MAXN], mx[MAXN];
#define ls (ch[now][0])
#define rs (ch[now][1])
    void pushup(int now)
    {
    siz[now] = 1;
    mx[now] = val[now];
    if (ls) siz[now] += siz[ls], mx[now] = max(mx[now], mx[ls]);
    if (rs) siz[now] += siz[rs], mx[now] = max(mx[now], mx[rs]);
    }
    int merge(int x, int y)
    {
//  printf("m %d %d\n", x, y);
    if (!x || !y) return x + y;
    if (pri[x] < pri[y])
    {
        ch[x][1] = merge(ch[x][1], y);
        pushup(x);
        return x;
    }
    else
    {
        ch[y][0] = merge(x, ch[y][0]);
        pushup(y);
        return y;
    }
    }
    void split_s(int now, int & x, int & y, int k)
    {
//  printf("split %d %d %d %d\n", now, x, y, k);
    if (!now) { x = 0, y = 0; return ; }
    if (siz[ls] >= k)
    {
        y = now;
        split_s(ls, x, ch[y][0], k);
    }
    else 
    {
        x = now;
        split_s(rs, ch[x][1], y, k - siz[ls] - 1);
    }
    pushup(now);
    }
    int newnode(int v)
    {
    int now = ++ tot;
    siz[now] = 1;
    mx[now] = val[now] = v;
    pri[now] = rand() % 19260817;
    ch[now][0] = ch[now][1] = 0;
    return now;
    }
    void init()
    {
    int x = newnode(1), y = newnode(1);
    root = merge(x, y);
    }
    int getmax(int pos)
    {
    int x = -2, y = -2;
    split_s(root, x, y, pos);
    int ret = mx[x];
    root = merge(x, y);
    return ret;
    }
    void insert(int pos, int v)
    {
    int x = -1, y = -1;
    split_s(root, x, y, pos);
    int now = newnode(v);
//  printf("ins %d %d %d\n", x, now,y);
    root = merge(x, merge(now, y));
    }
    int place(int pos)
    {
    int v = getmax(pos) + 1;
    insert(pos, v);
    return mx[root];
    }
    void print(int now) 
    {
    printf("%d : %d %d %d %d [%d, %d]\n" ,now, pri[now], siz[now], val[now], mx[now], ls, rs);
    }
    void check()
    {
    printf("### %d %d\n", root, tot);
    for (int i = 1; i <= tot; ++ i) print(i);
    puts("");
    }
#undef ls
#undef rs
}

分治

CDQ分治

BZOJ3295 动态逆序对

对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删

除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数

\(N<=100000 M<=50000\)

Sol;

正序删除就等以倒叙插入

在每个点上记录位置比他前的点和他产生的逆序对数量

对于一个新插入的节点\(A\):

• 如果一个以存在的点\(B\), \(A.pos<B.pos ~\&\&~A.val>B.val\),那么\(A\)对\(B\)产生贡献
• 如果\(A.pos > B.pos~\&\&~A.val < B.val\), 那么\(B\)对\(A\)产生贡献

所以把\((Time, pos, val)\)做三维偏序, 注意左边和右边有双向的贡献

int n, m;

struct Fenwick
{
    int val[MAXN];
    void upd(int x, int v)
        {
            for (int i = x; i <= 100000; i += (i & (-i))) val[i] += v;
        }
    int qry(int x)
        {
            int ret = 0;
            for (int i = x; i > 0; i &= (i - 1)) ret += val[i];
            return ret;
        }
} T, T2;

LL ans, an[MAXN];
int pos[MAXN], ask[MAXN];
struct Node
{
    int t, p, v, id;
    bool operator < (const Node & b) const
        {
            return t < b.t;
        }
} a[MAXN], b[MAXN];

int mark[MAXN];
void merge(int l, int mid, int r)
{
    int i = l, j = mid + 1, k = l;
    while (k <= r)
    {
        if (j > r || (i <= mid && a[i].p <= a[j].p))
        {
            mark[k] = 0;
            b[k ++] = a[i ++];
        }
        else
        {
            mark[k] = 1;
            b[k ++] = a[j ++];
        }
    }
    for (int i = l; i <= r; i ++)
    {
        if (mark[i] == 0) T.upd(b[i].v, 1);
        else an[b[i].id] += T.qry(100000) - T.qry(b[i].v);
    }
    for (int i = l; i <= r; i ++) if (mark[i] == 0) T.upd(b[i].v, -1);
    for (int i = r; i >= l; i --)
    {
        if (mark[i] == 0) T.upd(b[i].v, 1);
        else an[b[i].id] += T.qry(b[i].v);
    }
    for (int i = l; i <= r; i ++) if (mark[i] == 0) T.upd(b[i].v, -1);
    for (int i = l; i <= r; i ++) a[i] = b[i];
}
void CDQ(int l, int r)
{
    if (l >= r) return ;
    int mid = (l + r) >> 1;
    CDQ(l, mid);
    CDQ(mid + 1, r);
    merge(l, mid, r);
}

整体二分

POJ - 2104 K-th Number

\(1 <= n <= 100 000, 1 <= m <= 5 000\), 给出数组\(a[1..n](\leq1e9)\)

将数组数值和询问一起放入操作序列\(a[]\)中

\(solve(x, y, l, r)\)代表操作编号在\([x,y]\)间的询问的答案在\([l,r]\)之间, 并且当前\([x,y]\)间的询问只能由\([x,y]\)之间的数值贡献​

int n, m, tot;

struct Fenwick
{
    int val[MAXN];
    void upd(int x, int v)
        {
            for (int i = x; i <= 100000; i += (i & (-i))) val[i] += v;
        }
    int qry(int x)
        {
            int ret = 0;
            for (int i = x; i > 0; i &= (i - 1)) ret += val[i];
            return ret;
        }
} T;

struct Node
{
    int v, l, r, p, typ, id;
} a[MAXN << 1], al[MAXN << 1], ar[MAXN << 1];
int an[MAXN];
void solve(int x, int y, int l, int r)
{
    if (l > r || x >= y) return ;
    if (l == r)
    {
        for (int i = x; i <= y; i ++)
            if (a[i].typ == 1) an[a[i].id] = l;
        return;
    }
    int mid = (l + r) >> 1;
    int cntl = 0, cntr = 0;
    for (int i = x; i <= y; i ++)
    {
        if (a[i].typ == 0)
        {
            if (a[i].v <= mid) al[++cntl] = a[i], T.upd(a[i].id, 1);
            else ar[++cntr] = a[i];
        }
        else
        {
            int val = T.qry(a[i].r) - T.qry(a[i].l - 1);
            if (a[i].p <= val) al[++cntl] = a[i];
            else a[i].p -= val, ar[++cntr] = a[i];
        }
    }
    for (int i = x; i <= y; i ++)
        if (a[i].typ == 0 && a[i].v <= mid) T.upd(a[i].id, -1);
    for (int i = 1; i <= cntl; i ++) a[x + i - 1] = al[i];
    for (int i = 1; i <= cntr; i ++) a[x + cntl + i - 1] = ar[i];
    solve(x, x + cntl - 1, l, mid);
    solve(y - cntr + 1, y, mid + 1, r);
}

int main()
{
    n = in(); m = in();
    for (int i = 1; i <= n; i ++)
    {
        a[++ tot].v = in();
        a[tot].typ = 0;
        a[tot].id = i;
    }
    for (int i = 1; i <= m; i ++)
    {
        a[++ tot] = (Node) {0, in(), in(), in(), 1, i };
    }
    solve(1, tot, -INF, INF);
    for (int i = 1; i <= m; i ++) printf("%d\n", an[i]);
    return 0;
}

点分治

BZOJ4568: [Scoi2016]幸运数字

题意:

给一颗\(\le 20000\)的树, 有点权, 有\(\le 200000\)的询问, 求两点之间路径上的最大异或和(任选一些数)

Sol:

线性基的部分就略过了

离线询问, 在每个节点上vector存询问(对面的点, 询问编号), 每次处理经过淀粉中心(即LCA为淀粉中心)的询问

注意每个点会被扫到\(\lg\)次, 询问也同理, 而非\(n\)次

所以这样就可以\(O(n \log n \cdot 60 + q \log n + q \cdot 60 ^ 2)\)

注意被扫到\(lg\)次, 但每个询问只有一次有效的处理, 其他只是扫扫而已

int n, m;
LL a[MAXN];

struct Linb
{
    LL p[62];
    Linb () { memset(p, 0, sizeof p); }
    void clear() { memset(p, 0, sizeof p); }
    bool ins(LL x)
    {
        for (int i = 60; i >= 0; -- i)
        {
        if (!(x & (1LL << i))) continue;
        if (p[i]) x ^= p[i];
        else 
        {
            p[i] = x;
            return true;
        }
        }
        return false;
    }
    LL getmax()
    {
        LL ret = 0;
        for (int i = 60; i >= 0; -- i)
        if ((ret ^ p[i]) > ret) ret ^= p[i];
        return ret;
    }
} ;
Linb unite(Linb a, Linb b)
{
    Linb c = a;
    for (int i = 60; i >= 0; -- i)
    if (b.p[i]) c.ins(b.p[i]);
    return c;
}

int head[MAXN], nume;
struct Adj { int nex, to; } adj[MAXN << 1];
void addedge(int from, int to)
{
    adj[++ nume] = (Adj) { head[from], to };
    head[from] = nume;
}
void link(int u, int v)
{
    addedge(u, v);
    addedge(v, u);
}

LL ans[MAXM];

struct Node { int to, id; } ;
vector <Node> qry[MAXN];

bool vis[MAXN];
int cen, siz[MAXN], col[MAXN];
Linb lb[MAXN];
void getcen(int u, int fa, int tot)
{
    siz[u] = 1; int mx = 0;
    for (int i = head[u]; i; i = adj[i].nex)
    {
    int v = adj[i].to;
    if (v == fa || vis[v]) continue;
    getcen(v, u, tot);
    mx = max(mx, siz[v]);
    siz[u] += siz[v];
    }
    mx = max(mx, tot - siz[u]);
    if (mx <= tot / 2) cen = u;
}
void calc(int u, int fa)
{
    siz[u] = 1; 
    lb[u] = lb[fa]; lb[u].ins(a[u]);
    for (int i = 0; i < (int)qry[u].size(); ++ i)
    {
    int to = qry[u][i].to;
//  printf("(%d %d(%d))\n", u, to, col[to]);
    if (col[to] == cen) 
        ans[qry[u][i].id] = max(ans[qry[u][i].id], unite(lb[to], lb[u]).getmax());
    }
    for (int i = head[u]; i; i = adj[i].nex)
    {
    int v = adj[i].to;
    if (v == fa || vis[v]) continue;
    calc(v, u);
    siz[u] += siz[v];
    }
}
void mark(int u, int fa)
{
    col[u] = cen;
    for (int i = head[u]; i; i = adj[i].nex)
    {
    int v = adj[i].to;
    if (v == fa || vis[v]) continue;
    mark(v, u);
    }
}
void DFS(int u, int tot)
{
    getcen(u, 0, tot);
    vis[cen] = true; 
    col[cen] = cen;
    lb[cen].clear(); lb[cen].ins(a[cen]);
    for (int i = head[cen]; i; i = adj[i].nex)
    {
    int v = adj[i].to;
    if (vis[v]) continue;
    calc(v, cen);
    mark(v, cen);
    }
    for (int i = head[cen]; i; i = adj[i].nex)
    {
    int v = adj[i].to;
    if (vis[v]) continue;
    DFS(v, siz[v]);
    }
}

int main()
{
    n = in(); m = in();
    for (int i = 1; i <= n; ++ i) a[i] = in();
    for (int i = 1; i < n; ++ i) link(in(), in());
    for (int i = 1; i <= m; ++ i) 
    {
    int u = in(), v = in();
    qry[u].push_back((Node) {v, i});
    qry[v].push_back((Node) {u, i});
    if (u == v) ans[i] = a[u];
    }
    DFS(1, n);
    for (int i = 1; i <= m; ++ i) printf("%lld\n", ans[i]);
    return 0;
}

博弈论

SG

SG函数

• 定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。
• 定义 \(SG(now) = mex(SG(nex))\),即对后继状态的SG函数值的集合进行mex运算。
• 若看成有向无环图, 那么没有出边的终状态\(SG\)值为\(0\)

SG定理

游戏和的SG函数等于各个游戏SG函数的Nim和(XOR和)

数论

线性筛质数

bool flag[MAXN];
int prm[MAXN], tot;
void filter()
{
    for (int i = 2; i <= 1000; ++ i)
    {
    if (!flag[i]) prm[++ tot] = i;
    for (int j = 1; i * prm[j] <= 1000 && j <= tot; ++ j)
    {       
        flag[i * prm[j]] = true;
        if (i % prm[j] == 0) break;
    } 
    }
}

欧几里得

LL exgcd(LL a, LL b, LL & x, LL & y)
{
    if (!b) { x = 1, y = 0; return a; }
    LL d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

\(ax+by=m\)
若\(m \mod \gcd(a, b) \ne 0\)则无解
否则设\(k\cdot \gcd(a, b) = m\)

得到特解\(x_0, y_0\), 显然等式两边同乘\(k\)即可
设这样得到的一组解为\(x_1=x_0\cdot k, y_1=y_0\cdot k\)

同理
得到最小\(x\)整数解, \(x = ((x_1 \mod \frac{b}{\gcd(a,b)})+\frac{b}{\gcd(a,b)}) \mod \frac{b} {\gcd(a,b)}\)
得到最小\(y\)整数解, \(y = ((y_1 \mod \frac{a}{\gcd(a,b)})+\frac{a}{\gcd(a,b)}) \mod \frac{a} {\gcd(a,b)}\)

中国剩余定理

\(m\)不互质

\[\begin{cases} x \equiv a_1(\mod m_1) \\ x \equiv a_2(\mod m_2) \\ \end{cases}\]

得

\[\begin{cases} x = a_1 + k_1\cdot m_1 \\ x = a_2 + k_2\cdot m_2 \\ \end{cases}\]

设\(x_0\)是第一个方程的解, 则通解为\(x=x_0+t\cdot m_1\)
则
\[\begin{aligned} & x_0+t\cdot m_1=a_2+k_2\cdot m_2 \\ & t\cdot m_1 + k_2 \cdot m_2 = a_2 - x_0 \\ & t\cdot m_1 \equiv a_2 - x_0 (\mod m_2)\\ \end{aligned}\]

• 注意这里\(a_2 - x_0\)不能取模\(m_1\), 因为这样会导致\(t\)不准确(因该是根本没意义), 取模\(m_2\)一方面是\(k\)的取值不关键, 另一方面是为了取正数以及方便扩欧

用exgcd()求解\(t, k_2\), 则两个方程的解为\(x=x_0 + t \cdot m_1\) 完成了合并

LL mul(LL a, LL b, LL p)
{
    LL ret = 0;
    while (b)
    {
    if (b & 1) b ^= 1, (ret += a) %= p;
    else b >>= 1, (a += a) %= p;
    }
    return ret;
}
LL exGCD(LL a, LL b, LL & x, LL & y)
{
    if (!b) 
    {
    x = 1, y = 0;
    return a;
    }
    LL d = exGCD(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
LL exCRT()
{
    LL Mo = mo[1], X = a[1];
    for (int i = 2; i <= n; ++ i)
    {
    LL k1, k2, g = exGCD(Mo, mo[i], k1, k2), newM = Mo / g * mo[i];
    LL c = ((a[i] - X % mo[i]) % mo[i] + mo[i]) % mo[i];
    if (c % g) return -1;
    k1 = mul(k1, c / g, mo[i] / g);
    k1 = (k1 % (mo[i] / g) + mo[i] / g) % (mo[i] / g);
    k2 = (c - k1 * Mo) / mo[i];
    (X += mul(k1, Mo, newM)) %= newM;
    Mo = newM;
    }
    return X;
}

int main()
{
    n = in();
    for (int i = 1; i <= n; ++ i) mo[i] = in(), a[i] = in();
    printf("%lld", exCRT());
    return 0;
}

BSGS及extendBSGS算法

解高次同余方程\(a^x\equiv b(\mod c)\)

考虑\(a^x\)的循环节:

• 若\(\gcd(a,c)=1\), 根据费马小定理得\(a^{c-1}\equiv 1(\mod c)\), 又因为\(a^0\equiv 1(\mod c)\), 所以循环节\(<c\)
• 若不等于\(1\), 等下再说

BSGS

前提: \(\gcd(a,c)=1\)

根据前面分析的循环节取值, 考虑用根号和\(map\)来优化\([0,c)\)的暴力

设\(m=\lceil \sqrt{c}\rceil, x=i*m-j\), 当\(i\in [1,m], j\in [0,m]\)时\(x\)可以取遍\([0,c]\)
\[ a^{im}\equiv ba^j(\mod c) \]
预先把右边取模后的值, 该值下\(j\)的取值(最大)存进\(map\)

然后暴力左边, 查询\(map\),可以证明越早查到解越小

复杂度\(O(\sqrt{c}*map)\)

map <LL, int> rec;
LL qpow(LL a, LL b, LL mod)
{
    LL ret = 1;
    while (b)
    {
        if (b & 1) (ret *= a) %= mod, b ^= 1;
        else (a *= a) %= mod, b >>= 1;
    }
    return ret;
}
int BSGS(LL a, LL b, LL c)
{
    LL m = ceil(sqrt(c));
    LL sum = b, ap = qpow(a, m, c);
    for (int i = 0; i <= m; ++ i, (sum *= a) %= c) rec[sum] = i;
    sum = ap;
    for (int i = 1; i <= m; ++ i, (sum *= ap) %= c)
        if (rec.count(sum)) return i * m - rec[sum];
    return -1;
}

exBSGS

若\(d=\gcd(a,c)!=1\)

观察\(a^x=b+kc\)这个等式, 如果\(b\mod d\ne 0\), 那就无解

在有解的情况下, 等式两边可以同除以\(d\)
\[ \frac{a}{d}*a^{x-1}=\frac{b}{d}+k*\frac{c}{d} \]
不断除以\(d=\gcd(a, \frac{c}{d})\), 直到互质
\[ \frac{a^t}{\prod d}*a^{x-t}=\frac{b}{\prod d}+k*\frac{c}{\prod d}\\ \frac{a^t}{\prod d}*a^{x-t}\equiv\frac{b}{\prod d}(\mod \frac{c}{\prod d})\\ \]
然后就相当于一个带系数的BSGS了, 求解后要加一个\(t\)

而由于求出来的解\(>t\), 所以要暴力求一遍\([0,t]\), 这个\(t\)是辗转相处级别的, 前面提到过, 即\(O(\lg)\)

map <int, int> rec;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
LL qpow(LL a, LL b, LL mod)
{
    LL ret = 1;
    while (b)
    {
        if (b & 1) (ret *= a) %= mod, b ^= 1;
        else (a *= a) %= mod, b >>= 1;
    }
    return ret;
}
int exBSGS(LL a, LL b, LL c)
{
    LL d, k = 1;  int cnt = 0;
    for (d = gcd(a, c); d != 1; d = gcd(a, c))
    {
        if (b % d) return -1;
        (k *= a / d) %= c, ++ cnt;
        c /= d; b /= d;
        if (k == b) return cnt;
    }
    LL m = ceil(sqrt(c));
    LL sum = b, ap = qpow(a, m, c);
    for (int i = 0; i <= m; ++ i, (sum *= a) %= c) rec[sum] = i;
    sum = ap * k % c;
    for (int i = 1; i <= m; ++ i, (sum *= ap) %= c)
        if (rec.count(sum)) return i * m - rec[sum] + cnt;
    return -1;
}

字符串

KMP

        for (int i = 2, j = 0; i <= n; ++ i)
        {
            while (a[i] != a[j + 1] && j != 0) j = fail[j];
            if (a[i] == a[j + 1] && j + 1 <= n) ++ j;
            fail[i] = j;
            //printf("fail[%d] = %d\n", i, fail[i]);
        }
        for (int i = 1, j = 0; i <= m;  ++ i)
        {
            while (b[i] != a[j + 1] && j != 0) j = fail[j];
            if (b[i] == a[j + 1] && j + 1 <= n) ++ j;
            if (j == n) ans ++, j = fail[j];
        }
        printf("%d\n", ans);
        //aabaabaa

SAM

int size, last;
int len[MAXN], link[MAXN], ch[MAXN][30], cnt[MAXN], id[MAXN]; // MAXN = 2 * length(S)
void extend(int c)
{
    int cur = ++ size, p = last;
    len[cur] = len[last] + 1;
    for (; p != -1 && !ch[p][c]; p = link[p]) ch[p][c] = cur;
    if (p == -1) link[cur] = 0;
    else 
    {
        int q = ch[p][c];
        if (len[q] == len[p] + 1) link[cur] = q;
        else 
        {
            int clone = ++ size;
            len[clone] = len[p] + 1;
            link[clone] = link[q];
            memcpy(ch[clone], ch[q], sizeof ch[q]);
            for (; p != -1 && ch[p][c] == q; p = link[p]) ch[p][c] = clone;
            link[q] = link[cur] = clone;
        }
    }
    last = cur;
}
void topo()
{
    for (int i = 0; i <= size; ++ i) ++cnt[len[i]];
    for (int i = 1; i <= size; ++ i) cnt[i] += cnt[i - 1];
    for (int i = 0; i <= size; ++ i) id[-- cnt[len[i]]] = i;
}
void build()
{
    link[0] = -1;
    for (int i = 1; i <= n; ++ i) extend(a[i] - 'a');
    topo();
}

注意

• 有依赖的变量之间注意运算先后关系
• 函数嵌套传参有顺序问题, 稳健为好
• MAXT大小, 懒标记优先关系, 下传/更新
• 位运算注意优先级, 尽量加括号
• 结束前检查编译, 文件名, 留 10 分钟