通用求众数离线做法：离散化之后，开线段树维护数出现的频率的最大值，带单点修改，然后再用莫队，移动区间时就跑一个单点修改，复杂度是$O(n\sqrt{n}\log n)$。

当只需要找频数超过一半的区间众数的时候，可以这样考虑：众数频数如果超过区间长度的一半，那么任意划分区间为两段，它必然要么在左半边超过一半，要么在右边超过一半。然后就可以用线段树维护了。具体来说，每个结点维护当前区间的众数及其频数。当合并时，找左儿子和右儿子的众数。如果众数频数超过一半，那么众数一定是二者之一。离散化后对每个数开一个pos数组维护出现位置，在这个数组中二分得到这两者（左右儿子的众数）在当前区间中出现的频数，取最大者即可。这样维护出来不一定是真区间众数，但是如果众数超过区间长度一半，那他一定维护这个众数。这个复杂度是每次查询$O(\log^2n)$的。上面的论述中“一半”大概也可以改为其他比例，这带来的问题是满足其他比例的众数可能有多个，而这个比例超过一半时可以保证这样的众数唯一。

还有一种做法是随机化，在待查询区间里找30个数作为候选众数，对每个数检查它是否满足频数超过区间长度一半，用上段的方法可以做到$O(\log n)$查询。如果一个数频数超过区间长度一半，那么在区间内任取30个数（带放回）找不到该众数的概率不超过$2^{-30}$。这个做法完全可以扩展到其他比例，比例变小时只需提高30这个常数，例如要求众数频数超过$1/5$时可以取100个候选众数，即可做到$({4\over 5})^{100}\approx2\times10^{-10}$概率。这是选不到真众数的概率，因为超过1/5的众数可能有多个，似乎有点迷惑（选不到假众数的概率也是一样的，他们互不影响）。但是没关系，由于候选众数中几乎必有真众数，即使找到了假众数，还需要和真众数比频数，所以这种算法几乎必然找到真众数。

CF716Div2 D AC代码：

#include <bits/stdc++.h>
#define N 300000
using namespace std;
typedef pair<int, int> pii;
int n, m, maxn, a[N + 5];
struct node {
    int l, r, mx, aa;
};
node xds[4 * N+5];
vector<int> pos[N+5];

int cnt(int x, int l, int r) {
    int ret = upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l);
    return ret;
}

void build(int id, int l, int r) {
    if(l == r) {
        xds[id].l = xds[id].r = l;
        xds[id].mx = 1;
        xds[id].aa = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    xds[id].l = l; xds[id].r = r;
    if (cnt(xds[id * 2].aa, l, r) > cnt(xds[id * 2 + 1].aa, l, r)) {
        xds[id].mx = cnt(xds[id * 2].aa, l, r);
        xds[id].aa=  xds[id * 2].aa;
    } else {
        xds[id].mx = cnt(xds[id * 2 + 1].aa, l, r);
        xds[id].aa=  xds[id * 2 + 1].aa;
    }
}

pii get(int id, int l, int r) {
    // (frequency, value)
    pii ret, ret2;
    int f1 = 0, f2 = 0;
    if (l <= xds[id].l && xds[id].r <= r) {
        return pii(xds[id].mx, xds[id].aa);
    }
    int mid = (xds[id].l + xds[id].r) >> 1, rl = max(l, xds[id].l), rr = min(r, xds[id].r);
    if (l <= mid) {
        ret = get(id * 2, l, r);
        f1 = cnt(ret.second, rl, rr);
    }
    if (r > mid) {
        ret2 =  get(id * 2 + 1, l, r);
        f2 = cnt(ret2.second, rl, rr);
    }
    if (f1 > f2) {
        return pii(f1, ret.second);
    } else {
        return pii(f2, ret2.second);
    }
}

int main() {
    int l, r;
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        pos[i].push_back(n + 1);
    }
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        cin >> l >> r;
        pii most = get(1, l, r);
        cout << max(1, 2 * most.first - (r - l + 1)) << '\n';
    }
    return 0;
}

这可能是本学期学习数据结构与算法课的最大收获，就是知道了还有线性建堆的方法。线性建堆可能也是有应用场景的，比如用$O(n)$的空间及时间复杂度，取出前$n/\log n$大的所有数。（？

Read More

话说线上赛有啥游记好写的…但是作为惯例还是写一个。

Read More

在做小学期Day5C题（在线维护中位数）时，由于我没有做过，也没有想到正解（对顶堆），卡了很久，最后用一个奇怪的方法做出来了。发现这个奇怪的做法复杂度稍高，但是可以扩展。对顶堆只能维护中位数或固定k的第k大数，而奇怪做法可以（伪？）在线查找第k大数，k可变，代价是$O(\log^2 n)$的，$n$为数列长度。

Read More

题意

正权无向图$G$，有$n$个点与$m$条边。你要回答$q$次询问，每次询问$u,v$两点，回答对于$u,v$两点，这张图上有多少条边在它们任意一条最短路上出现。

Read More

小学期题用了这个函数，觉得十分高级，学习一个。

这个函数用来数二进制数中1的个数。正常的操作是：看unsigned int二进制表示下最右端是不是1；若是1，则计数器+1，再右移；重复32次。这样的操作需要进行32次int运算，效率不够高。这个问题可以二分解决。

Read More

将每个独立集$V$考虑为原图中被染色的一些顶点，而在原图中加边后$E'$可以得到一个子图$G'$，这个子图如果满足一些条件，$V$就是$E'$生成的子图$G'$中的一个独立集。这些条件为：

1. 一条边的两端不同时被染色（或$V$中任意两点间没有边）
2. 没有孤立顶点被染色（$V$中的每个点都应当与$E'$中的一条边相连）

Read More

由于一条路径可以包含一条边多次，所以如果$a$能经历$k$条边到达$b$，那就可以经过$k+2n$条边到达$b$，只需要在路径中随便找一条边不停折返即可。于是考虑对树黑白染色，（注意结论，即树是二分图，从而可以dfs染成黑白两色，方便考虑）。

Read More

本文讲解Dinic算法的思路，算法本身与证明。

关于残余网络和增广路等概念的说明，请看Ford-Fulkerson算法这篇文章。这里只致力于改进Ford-Fulkerson算法，得到一个与$F$无关的算法。

问题

当$F$较大时，影响Ford-Folkerson算法效率的主要因素在于：每次dfs可能可以找到许多条路径，但是该算法中每次dfs只进行一次增广，这就导致增广次数与$F$（可能）相关。一种想法是一次dfs多次增广，但这样做能否成功是取决于dfs顺序的，于是考虑，dfs顺序如何时，效率较高呢？

思路

Dinic算法的核心是每次寻找最短的增广路，并进行增广。这样做的理由（既是依据，也是好处）是，每次沿最短增广路增广后，最短增广路的长度一定不会减少，稍后会给出证明。假如有了这一结论，每次找到最短增广路的长度时，将该长度的增广路[全部增广]，然后重新寻找最短增广路，其长度至少增1，而增广路长度不会超过$|V|$（因为增广路是简单路径），从而增广次数上界$O(|V|)$。

证明

下面证明，每次沿最短增广路增广后，最短增广路的长度一定不会减少。在原图上，为寻找最短增广路，从$s$出发bfs，设第一次到达点$v$的边为$\langle u,v\rangle$，为点$v$编号$n_v=n_u+1$。由bfs的特性，每条边增量（指该边终点与起点编号差，可为负值，后均同）不超过1。特别地，$n_s=0,s$为源点。称这个图为分层图。

此时有结论：若$n_t$被更新，那么最短增广路的长度为$n_t$。为了证明，可以寻找为$n_t$标号的边的出发点$i$，再寻找为$i$标号的边的出发点$j$，…，最终会回到$s$，并且沿每条边标号增1。由于每条边增量不超过1，每条边都增1是从0到$n_t$最快的方法，从而我们找到了（一条）最短增广路$l_{min}$，并且每个最短增广路中的每条边$\langle u,v\rangle$都满足$n_v=n_u+1$。

下面使用数学归纳法。

（1）在分层图上沿最短增广路增广1次后，新图中可能出现一些新的反向边。若新图中有增广路$l'$，其中的边的来源有两种可能：

【1边】原分层图中的边（bfs时经历过的边）$\langle u,v\rangle$，满足$n_v\leq n_u+1$；

【2边】增广时出现的反向边$\langle v,u\rangle$，记原边为$\langle u,v\rangle$，那么由于原边在最短增广路中，一定满足$n_v=n_u+1$。

那么沿该路径中任何一条边编号增加不超过1，为了从$0$到达$n_t$仍然至少需要$n_t$条边，长度没有变短，所以最短增广路长度没有减少，并且所有边都仍满足$n_v\leq n_u+1$。

（2）假设沿最短增广路增广n次后，最短增广路长度不减少。当增广$(n+1)$次后，若图中无增广路，结论成立。若图中仍有增广路，其中的边可能是：

【1边】增广n次后的图中的边$\langle u,v\rangle$，满足$n_v\leq n_u+1$；

【2边】第$(n+1)$次增广时出现的反向边$\langle v,u\rangle$，记原边为$\langle u,v\rangle$，那么由于原边在最短增广路中，一定满足$n_v=n_u+1$。

类似于上面，可以证明沿最短增广路增广$(n+1)$次后，最短增广路长度仍不减少，并且所有边都仍满足$n_v\leq n_u+1$。

综上，沿最短增广路增广后，最短增广路长度不会减少。

优化

首先，在证明中我们知道：最短增广路中的每条边$\langle u,v\rangle$都满足$n_v=n_u+1$，从而我们只考虑递增的边不会出现错误。实际上，每次分层完后，只要找到增广路就可以增广，不必局限在最短增广路中增广，这是自缚手脚。只考虑递增的边的情况下，情况立刻不同了：图成为了DAG！从而，边$\langle u,v\rangle$能否使用只与$v$可达的点（记符合条件的点集为$V$，那么$\forall g \in V$，$n_g>n_v$）的情况有关，而与$s$如何到达$u$无关，从而，如果某一时刻发现一条边不能使用，那么在重新bfs（即重新标号）之前，无论其他地方如何增广，其后的边流量只会减少不会增加，这条边都仍然不能用来增广。于是可以记录这些边使之只遍历一次，每次分层至多访问它们$O(|E|)$次。

算法描述

下面的算法只是大致的描述，没有伪代码那么明确，重在讲清楚过程，希望我做到了。

（Dinic算法）输入：网络$G(V,E)$ 输出：最大流$max\_flow$

步骤0. [准备]建立数组$iter[V]$，定义$max\_flow\gets0$，用邻接表$G[V]$存储网络；

步骤1. [建立分层图]bfs(s,0)，当bfs(u,n)时，若$n_u$已定义，返回；否则记$n_u=n$，并对$G[u]$中的所有元素$v$进行bfs(v, n+1)。清零$iter[]$数组。

步骤2. [有增广路吗？]若$n_t$未定义，退出算法，返回$max\_flow$。

步骤3. [寻找增广路]在$G$上DFS，寻找从$s$到$t$的简单路径，要求该路径上每条边$e\langle u,v\rangle$可用权值$(w_e-f_e)$大于0，并且$n_v>n_u$。若找到，记该路径上的权值最小的边权值为$f$，否则$f\gets0$。DFS(u)时按顺序遍历$G[u]$，若$G[u][i]$不可用，$iter[u]\gets iter[u]+1$。

步骤4. [找到了，更新残余网络]如果$f>0$，置$max\_flow\gets max\_flow+f$。对路径上的每条边$e$，置$f_e\gets f_e+f$。记其反向边为$e'$，置$w_{e'}\gets w_{e'}+f$。返回步骤3。

步骤5. [没有找到]如果$f=0$，返回步骤1。

复杂度

由于每次dfs都至少使一条边满流（从而使之无法使用），dfs次数上界为$O(|E|)$。在当前弧优化后，每次dfs经过的边有两种可能性：（1）是无用边（2）在增广路里，其中（1）无用边在一次分层内总共访问$O(|E|)$次，而（2）成功增广的情况中，增广路长度不超过$|V|$，每次分层中情况（2）的总复杂度上界为$O(|E||V|)$，从而每次分层的复杂度上界为$O(|E||V|+|E|)=O(|E||V|)$，从而Dinic算法总的时间复杂度为$O(|E||V|^2)$。

模板

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define V 5005 //V为顶点最大个数<span class="bd-box"><h-char class="bd bd-beg"><h-inner>，</h-inner></h-char></span>视数据范围而定
#define INF 0x7fffffffffffffff

using namespace std;
typedef long long ll;
struct edge{
    ll to, w, rev;
};
vector<edge> G[V];
int num[V], iter[V];
int s, t;//源点和汇点<span class="bd-box"><h-char class="bd bd-beg"><h-inner>，</h-inner></h-char></span>是全局变量

ll max_flow();
ll dfs(ll u, ll f);
void bfs();
void add_edge(ll from, ll to, ll w);

ll max_flow() {
    ll f = 0, flow = 0;
    while(true) {
        memset(iter, 0, sizeof(iter));
        bfs();
        if(num[t] == -1) return flow;
        while(f = dfs(s, INF)) {
            flow += f;
        }
    }
}
ll dfs(ll u, ll f) {
    if(u == t) return f;
    ll flow;
    for(int &i = iter[u]; i < G[u].size(); i++) {
        edge &e = G[u][i];//注意是引用<span class="bd-box"><h-char class="bd bd-beg"><h-inner>，</h-inner></h-char></span>需要直接修改原图
        if(e.w > 0 && num[u] < num[e.to]) {
            if(flow = dfs(e.to, (f > e.w ? e.w : f))) {
                //min函数有些编译器不给过<span class="bd-box"><h-char class="bd bd-beg"><h-inner>，</h-inner></h-char></span>所以用三目
                e.w -= flow;
                //直接修改容量而非同时记录f和w<span class="bd-box"><h-char class="bd bd-beg"><h-inner>，</h-inner></h-char></span>只是为了方便
                G[e.to][e.rev].w += flow;
                return flow;
            }
        }
    }
    return 0;
}
void bfs() {
    memset(num, -1, sizeof(num));
    queue<int> que;
    que.push(s);
    num[s] = 0;
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = 0; i < G[u].size(); i++){
            edge &e = G[u][i];
            if(e.w > 0 && num[e.to] < 0) {
                num[e.to] = num[u] + 1;
                que.push(e.to);
            }
        }
    }
}
void add_edge(ll from, ll to, ll w) {
    G[from].push_back(edge{to, w, G[to].size()});
    G[to].push_back(edge{from, 0, G[from].size() - 1});
}

如有发现模板的错误请联系我指正，我将不胜感激。

最大流问题

举个例子，互联网上有几台计算机，某些计算机之间建立了一定带宽的有向连接。目标是将数据从某台指定的计算机$s$（称为源点）传输到$t$（称为汇点），求单位时间内最多能传输多少数据。

有许多类似的问题，都可以抽象成类似的网络流问题，上面的问题是一个（单源单汇）最大流问题。形式化地描述，即为：

对无重边与自环的有向图$G(V,E)$，若每条边$e\in E$有一个权值$w_e$（称作该边的容量），且$s\in V,t\in V$，称该图为一个网络。若一个有向图$G'(V,E)$满足：$G'$与$G$完全相同，除去每条边$e\in E$有另一个权值$f_e$（称作该边的流量）以外；并且对$\forall u\in V,u\ne s,u\ne t$满足$\sum\limits_{e=\langle u,v\rangle}{f_e}=\sum\limits_{e=\langle v,u\rangle}{f_e}$（即流入每个顶点的流量等于流出的流量），那么称该有向图$G'$为网络$G$上的一个流，该流的流量$f$定义为$\sum\limits_{e=\langle s,u\rangle}{f_e}$。一个网络的最大流是指该网络的所有流中流量最大的那个。

通常在不引起歧义的情况下，并不区分最大流和最大流的流量。

对上面的抽象模型，解决最大流问题的算法有两类：增广路算法和预流推进算法。最常用的是增广路算法中的 Ford-Fulkerson 算法和​ Dinic​ 算法。这里将常见的算法罗列如下：