Min-Max容斥

Min-Max容斥,也叫最值反演(脑子不够,套路来凑),可以处理一些计数问题。

形式(公式挂光了,救救孩子):

Max(S) = \sum_{T \subseteq S} (-1)^(|T| + 1) Min(T)

Min(S) = \sum_{T \subseteq S} (-1)^(|T| + 1) Max(T)

 

本质上是容斥TAT,用反演的角度来看,就是只有当T的size为1且是最大值时才会被计入贡献(等式咕了

这里的Min与Max并一定要是最大值和最小值,只要是在某一种偏序下的两个极端就好了。

基本上的套路大概就是随机选一段子集染色,问期望多久把全集染满——这是Max,就可以转化成对于每一个子集,期望第一次被染色的时间的值——这是Min。

 

好像还有GCD和LCM的转化,待填。

Kruskal重构树

前两天打了noi2018网上同步赛,看标算重构树以为是什么高明的dark数据结构,一看还是挺小清新的。

先考虑在做Kruskal的过程中,每次会选取一条当前最优的边并加入生成树。在这个过程中,我们可以加入一个虚节点表示当前的这条边,点权值即为边权。由于一条边只能有两个端点,所以这棵树必然是一棵二叉树,就可以妙妙地维护了啊!

然后这个树有一些很棒的性质,比如说一条边到根的路径上的点权是单调的,两点在图中的最长边的最小值即为两点在重构树上的LCA等等(自己想啦~逃

裸题:bzoj3732

打法自己想想吧233

实在不行可以参考我的代码:

void Krus ()
{
    sort(e + 1, e + m + 1, cmp);
    for (int i = 1; i <= n; ++i) ch[i][0] = ch[i][1] = 0;
    for (int i = 1; i <= m; i++)
    {
        int fu = gf(e[i].u), fv = gf(e[i].v);
        if (fu == fv) continue;
        val[++ver] = e[i].a;
        ch[ver][0] = anc[fu], ch[ver][1] = anc[fv];
        //maintain something here
        fa[fu] = fv, anc[fv] = ver;
    }
}

LCA算法合集

这两天看了看“最近公共祖先”(lowest common ancestors, LCA)
先说什么是LCA
好吧,顾名思义,就是,两个节点的深度最大的公共祖先
比如,上图中 4,7 的 LCA就是 2 , 3,6 的则是 3;
那么怎么做呢?

1.朴素算法(在线)
由较深的节点一直向上走,直到与另一个节点到达同一深度,接着两个节点一起向根走,直到达到统一节点,这个节点就是他们的LCA。
复杂度(对于每次询问):最坏 O(n),平均 O(log n)
代码:

[code language=”cpp”]
//这就不贴了吧
[/code]


2.Tarjan(离线)
首先把所有询问读入并存储,每次DFS都把儿子们所在的集合连接到当前节点上,再大力查询一波,如果与前节点与有查询关系的节点已经访问,那么他们的LCA既是当前节点的祖先(讲得不清楚,意会一下)
复杂度(处理+查询):O(n + q)
代码:

[code]
function TarjanOLCA(u)
MakeSet(u);
u.ancestor := u;
for each v in u.children do
TarjanOLCA(v);
Union(u,v);
Find(u).ancestor := u;
u.color := black;
for each v such that {u,v} in P do
if< v.color == black
print "Tarjan's Lowest Common Ancestor of " + u +
" and " + v + " is " + Find(v).ancestor + ".";
[/code]

由于上述代码使用了 “set” 这个集合操作,而我们绝对没有必要用STL的std::set(又慢又“过于强大”)。所以我们要使用并查集。
下面是我自己的(虽然拖进提交框就能跑,但还是别按Ctrl-C了吧)

[code language=”cpp”]
#include
#include
using namespace std;
const int N = 500010, M = 1000010;
int top[N], cnt = 0, fa[N], ans[N], E = 0, succ[M], nxt[M], con[M], to[M], fst[N], num[M];
bool vis[N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}</static inline void add(int u, int v)
{
    to[++E] = v;
    nxt[E] = fst[u];
    fst[u] = E;
}
static inline void addquery(int u, int v, int i)
{
    num[++cnt] = i;
    con[cnt] = v;
    succ[cnt] = top[u];
    top[u] = cnt;
}
void Tarjan(int now)
{
    vis[now] = true;
    for(int i = fst[now]; i !=-1; i = nxt[i])
    {
        int aim = to[i];
        if(vis[aim])continue;
        Tarjan(aim);
        fa[find(aim)] = find(now);
    }
    int temp;
    for(int i = top[now]; i !=-1; i = succ[i])
    {
        int v = con[i];
        temp = num[i];
        if(vis[v]) ans[temp] =find(v);
    }
}
int main()
{
    int n, m, s, u, v;
    scanf("%d%d%d", &n, &m, &s);
    memset(fst, -1, sizeof(fst));
    memset(top, -1, sizeof(top));
    memset(vis, 0, sizeof(vis));
    for(int i =1; i <= n; i++) fa[i] = i;
    for(int i =1; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    for(int i =1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        addquery(u, v, i), addquery(v, u, i);
    }
    Tarjan(s);
    for(int i =1; i <= m; i++)printf("%d\n", ans[i]);
    return0;
}
[/code]


3.欧拉序+RMQ

4.倍增(在线)
考虑对朴素算法进行优化:向上“跳跃”由单步改为 2i 步,不断由大到小地调整,便可以得到正解。
复杂度: O(n) – O(q log n)
代码:

[code language=”cpp”]
#include
#include
#include
#include
#define log2(i) ((int)((double)log(i) / (double)log(2)))
const int N = 5e5 + 10;
using namespace std;

int n, p[N][28], fst[N], nxt[2 * N], to[2 * N], deep[N], E = 0;

inline void add(int b, int e) {to[++E] = e; nxt[E] = fst[b]; fst[b] = E;}

int lca(int a, int b)
{
if (deep[a] > deep[b]) swap(a, b);
int dh = deep[b] – deep[a];
for (int i = 0; (1 << i) <= dh; i++) if (1 <= 0; i–) if (p[a][i] != p[b][i]) a = p[a][i], b = p[b][i];
a = p[a][0];
}
return a;
}

void dfs(int now)
{
for (int i = fst[now]; i != -1; i = nxt[i]) if (to[i] != p[now][0])
{
deep[to[i]] = deep[now] + 1;
p[to[i]][0] = now;
dfs(to[i]);
}
}

int main()
{
int m, s, u, v;
scanf(“%d%d%d”, &n, &m, &s);
memset(fst, -1, sizeof(fst));
for (int i = 1; i < n; i++)
{
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
deep[s] = 0;
dfs(s);
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i <= n; i++)
p[i][j] = p[p[i][j – 1]][j – 1];
int x, y;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &x, &y);
printf("%d\n", lca(x, y));
}
return 0;
}
[/code]


5.树链剖分(在线)

不会啊QAQ

关于BIT。。。

二叉索引树(Binary Indexed Tree 或 Fenwick Tree, BIT),俗称树状数组,是一种十分精妙的数据结构。
先上图:
无标题.png
*就是它*
至于它的含义,就是:每个点代表一段区间所包含的信息(sum, min, max, etc.),这段区间的长度取决于当前节点编号的lowbit,也就是二进制下最低的不为零的一位。因为数字再计算机中用补码存储,所以可以很方便的求出lowbit(i) : i & -i。
若要求一段区间*的信息怎么办?
由这段区间的最后一个节点开始,每次向前“跳”lowbit个位置,直到1。
更新?
由这段区间的第一个节点开始每次向后“跳”lowbit个位置,直到n。
*注:此处的区间指的是[1, x]
所谓“单点修改,区间查询”
那么“区间修改,单点查询”呢?
加上差分乱搞一番就好了
重点来了
如果我想要实现“区间修改,区间查询”怎么办?
线段树? 太难写(对于我这种蒟蒻),常数大,空间大。
所以可以糊一个公式。
首先,由一个差分的数组(序列)di
原数组中的an即为
1 (2) (1).png
然后呢,原数组的前缀和即可以表示为
1.gif
(推导过程自己看)
所以,我们只需要两个BIT,一个存,另一个存1 (1),再带入上述公式…稳了!
PS:jxc大佬(%%%)说,用BIT是无法代替线段树的。所以还是要用又长又烦的线段树辣。