2019 Multi-University Training Contests

My input method doesn’t work again. I’ll write this article in English.

Contest 1 Prob A. Blank

Consider record the last appeared position of each number. The order doesn’t matter. Use a simple dp to calculate the answer.

Complexity: O(n^4)

Code:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 111;

void Ad(int &x, int y) { if ((x += y) >= MOD) x -= MOD; }

int l[N], r[N], x[N], pos[N], id[N];

bool cmp(int x, int y)
{
    return r[x] == r[y] ? l[x] < l[y] : r[x] < r[y];
}

int dp[2][N][N][N];

int main()
{
    int T;
    int n = 100, m;
    for (scanf("%d", &T); T--; )
    {
        memset(dp, 0, sizeof dp);
        dp[0][0][0][0] = 1;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) scanf("%d%d%d", l + i, r + i, x + i), id[i] = i;

        sort(id + 1, id + m + 1, cmp);
        for (int i = 1, p = 1, q = 1; i <= n; i++, p ^= 1)
        {
            for (int j = 0; j <= i; j++)
                for (int k = 0; k <= j; k++)
                    for (int t = 0; t <= k; t++)
                        dp[p][j][k][t] = 0;


            for (int j = 0; j < i; j++)
                for (int k = 0; k <= j; k++)
                    for (int t = 0; t <= k; t++)
                    {
                        Ad(dp[p][j][k][t], dp[p ^ 1][j][k][t]);
                        Ad(dp[p][i - 1][j][k], dp[p ^ 1][j][k][t]);
                        Ad(dp[p][i - 1][j][t], dp[p ^ 1][j][k][t]);
                        Ad(dp[p][i - 1][k][t], dp[p ^ 1][j][k][t]);
                    }


            for (; q <= m && r[id[q]] == i; q++)
            {
                for (int j = 0; j < i; j++)
                    for (int k = 0; k <= j; k++)
                        for (int t = 0; t <= k; t++)
                            if ((j >= l[id[q]]) + (k >= l[id[q]]) + (t >= l[id[q]]) + 1 != x[id[q]])
                                dp[p][j][k][t] = 0;
            }
        }

        int ans = 0;
        for (int j = 0; j < n; j++)
            for (int k = 0; k <= j; k++)
                for (int t = 0; t <= k; t++)
                    Ad(ans, dp[n & 1][j][k][t]);
        printf("%d\n", ans);
    }

    return 0;
}

Contest 1 Prob B Operation

This problem shows my ignorance to Linear Base XD.

Build Linear Bases for each prefix of the array. When a new element is append to LB, put its contribution to the highest “1” in binary.
Hmmm, I can’t explain it well. To Be Updated.

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 500100;

int vec[N][32], pos[N][32];

void append(int p, int x)
{
    memcpy(pos[p], pos[p - 1], 32 * sizeof(int));
    memcpy(vec[p], vec[p - 1], 32 * sizeof(int));
    int curp = p;
    for (int i = 30; i >= 0; i--) if (x >> i)
    {
        if (!vec[p][i])
        {
            vec[p][i] = x, pos[p][i] = curp;
            break;
        }
        if (curp > pos[p][i])
        {
            swap(vec[p][i], x);
            swap(pos[p][i], curp);
        }
        x ^= vec[p][i];
    }
}

int main()
{
    int T;
    for (scanf("%d", &T); T--; )
    {
        int ans = 0;
        int n, m;
        scanf("%d%d", &n, &m);
        int x, opt, l, r;
        for (int i = 1; i <= n; i++) scanf("%d", &x), append(i, x);
        for (int i = 1; i <= m; i++)
        {
            scanf("%d", &opt);
            if (opt == 1)
            {
                scanf("%d", &x);
                append(++n, x ^ ans);
            }
            else
            {
                scanf("%d%d", &l, &r);
                l = (l ^ ans) % n + 1, r = (r ^ ans) % n + 1;
                if (l > r) swap(l, r);
                ans = 0;
                for (int i = 30; i >= 0; i--)
                {
                    if (pos[r][i] >= l && (ans ^ vec[r][i]) > ans)
                        ans ^= vec[r][i];
                }
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

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的转化,待填。

Codeforces 671D Roads in Yusland

题目链接

题意:给出一棵以1为根的有n个点的树与m条权值为ci的链,满足在链的两个端点的lca是他们中的一个(即这些链都是竖直的),所有节点至少被一条链覆盖,问最少选出权值和为多少的链满足方案,无解则输出-1。

 

题解:网上的做法大多是按照dfn把链离线之后用线段树维护,比较难写(大概)。然而我在某课件中看到了一种新颖的做法:应用对偶原理,将原问题转化为一个简单(?)的贪心问题,然后就要调很久了简单了很多。

 

先说对偶原理:对于一个线性规划问题,把它写成标准形式之后,大概是一个系数矩阵与未知数向量的积满足一个约束,最大化(或最小化)一个与未知数向量有关的线性表达式。然后对偶原理大概就是把系数矩阵转置,对于每一个约束建立一个变量。可能有点说不清,大概是比较抽象的缘故吧QAQ。(自行Google对偶原理其实也挺好的)

再看这道题,很快地便可以想到一个线性规划的形式,然后对偶一下:

(哇好丑啊)

然后就变成了问给每一条边赋权值,每条链上边权值之和不得大于ci,问总权值的最大值。

然后就用set的启发式合并就好了

代码: https://pastebin.ubuntu.com/p/cmjQ5x4Dv4/

写得很丑,表介意qwq

51Nod 1380 夹克老爷的逢三抽一

题目:51Nod 1380


题意概述:

3k 个数排成一个圆,每次取出一个数,答案加上它的值,并删去左右两边的数,问答案的最大值

思路:

这个题嘛。。。是在贪心专题里边的啦,那自然是贪心无疑了。然而一开始太naive,想了一个看两眼就会觉得是错误的贪心,就不放出来了qwq。实际上正解大概也算是一个带反悔的贪心(应该算是比较常见的操作了吧)。

先考虑另外一个问题:有一个环上有3k个数,要选出k个不相邻的数,使得他们的和最大。
考虑带反悔的贪心:我们贪心地选取最大的值,当我们选出一个点后,删除其左右的点,并在它的位置上加入一个权值为 a_{left} + a_{right} – a_{now} 的船新节点,选取这个节点的意义为:不选取 now 这个节点,而选择 left right 。重复这个过程 k 遍之后遍得到了答案。这个贪心显然是正确的。

然后我们来证明这个问题和原问题是等价的:
由于我们从 3k 个点中选处了 k 个点,并且两两不相邻。所以肯定可以保证存在一个节点使得它的一侧至少有一个与之相邻的空位(不选取的点),另侧至少有两个与之相邻空位。我们删除这个点及其两边的节点,就转化为从 3 (k – 1) 个点中选出 k – 1 个点,并且两两不相邻的问题。在边界条件 k = 1 时取法是存在的,所以根据数学归纳法,总是可以找到一种方案,使得在原问题中可以取出转化后问题的那些选取的点。证明完毕。

代码:

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<LL, int> P;
const int N = 1e5 + 10;
set<P> S;

int l[N], r[N];
LL a[N];

void del(int pos)
{
    l[r[pos]] = l[pos];
    r[l[pos]] = r[pos];
}

int main()
{
    LL ans = 0;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", a + i);
        l[i] = i == 1 ? n : i - 1;
        r[i] = i == n ? 1 : i + 1;
        S.insert(P(a[i], i));
    }
    for (int i = 1; i <= n / 3; i++)
    {
        int now = S.rbegin()->se;
        ans += a[now];
        S.erase(P(a[now], now));
        a[now] = a[l[now]] + a[r[now]] - a[now];
        S.insert(P(a[now], now));
        S.erase(P(a[l[now]], l[now]));
        S.erase(P(a[r[now]], r[now]));
        del(l[now]), del(r[now]);
    }
    printf("%lld\n", ans);
    return 0;
}

UOJ #213 圣杯战争

既然是圣杯战争,那主题图片就放一张fate的图咯

pid:70587790_p0

题目:UOJ #213


题意概述:

给你一个序列,定义一个连续子序列的贡献为这个序列中的最大值,分别求对于每种长度的所有连续子序列的贡献,输出异或和。

思路:

看到这道题,大概就能想到对于每一个节点计算贡献。考虑维护每一个端点所统治的区间,进行一番分类讨论:

p r_i – i + 1 i – l_i + 1 中较小的一个, q 为较大的一个。
对于 [1, p) 中的所有长度,加上 a_i \times i
对于 [p, q) 中的所有长度,加上 a_i \times p
对于 [q, p + q) 中的所有长度, 加上 (p + q – i) \times a_i
(只要画张图冷静分析一下就好了)

然后看到区间加的操作,大概想到可以差分,但是这里会加入的是 x \times i ,所以可以考虑维护另一个差分数组,将其前缀和乘上 i 加入答案即可。

hint:

有一个小提示我不得不说……就是 l r 中有一个是 \geq 另一个是<,不然会重复计算贡献,不要搞错了(瞪眼瞪了一万年

代码:

这个LL滥用是因为一开始爆int了,懒得一个一个改了233
还有这个 lr ,我的求法可能和大家不是很一样,其他人基本上写得是单调队列,我写的是类似kmp里面fail数组的求法

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 998244353, N = 1e6 + 100;

LL ori[N], a[N], l[N], r[N], d1[N], d2[N];

int main()
{
    LL n, ans = 0;
    scanf("%lld", &n);
    for (LL i = 1; i <= n; i++) scanf("%lld", a + i);
    for (LL i = 1; i <= n; i++)
        for (l[i] = i; l[i] - 1 >= 1 && a[l[i] - 1] <= a[i]; l[i] = l[l[i] - 1]);
    for (LL i = n; i >= 1; i--)
        for (r[i] = i; r[i] + 1 <= n && a[r[i] + 1] < a[i]; r[i] = r[r[i] + 1]);
    for (LL i = 1; i <= n; i++)
    {
        LL p = i - l[i] + 1, q = r[i] - i + 1; if (p > q) swap(p, q);
        d1[1] += a[i], (d1[p] += MOD - a[i]) %= MOD;
        d2[p] += p * a[i], (d2[q] += MOD - p * a[i] % MOD) %= MOD;
        (d1[q] += MOD - a[i]) %= MOD, d1[p + q] += a[i],
        d2[q] += (p + q) * a[i], (d2[p + q] += MOD - (LL)(p + q) * a[i] % MOD) %= MOD;
    }
    for (LL i = 1; i <= n; i++)
    {
        (d1[i] += d1[i - 1]) %= MOD, (d2[i] += d2[i - 1]) %= MOD;
        ans ^= (d1[i] * i + d2[i] + MOD) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

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;
    }
}

NOI同步赛小结

Day1:

本来想和同学py的,结果临时来了个老师帮我们“监考”,就233了,自己打吧。。

开场先看了一遍题,A没看懂,就看B。B我只发现冒泡排序的交换次数是逆序对对数。。。一看数据感觉不是很正确啊。。就去看C。C长得一副SAM的样子,昨天才听了思路,完全不会写,就又回去看A。

仔细理了一下思路,题面里离线的提示似乎是很明显的,然后套路把询问排序,排序好之后就变成用并查集维护联通块了,复杂度十分稳健,就去写了。看部分分的时候还发现有10分好打得很,就写了个7(大)5(众)分。

这里面还有一个树,我当时想得是求一条链上最深的大于某个值的边,就以为是树剖,遂不写。谁知还有naive的倍增啊。。。菜掉了。

 

T2一看一幅结论题的样子,感觉可以dp,但不是很会推转移,打完暴力就完了。

T3连暴力都没写。

 

最后成绩出来之后发现T1忘记清数组了。。。gg

白少了70分

本来预期75+12+0,变成了12分,,,惨啊

 

Day2:

待更

莫比乌斯反演

本来还打算写容斥的,结果不知不觉就过(颓)了好几个月,发现原来容斥如此高妙啊QAQ,那就讲讲比较套路的反演吧。。。

莫比乌斯反演。。。听起来很高明,实际上不算太难吧(逃

首先说他是莫比乌斯反演,总要有个缘由吧。个人感觉就是因为莫比乌斯函数,μ,是他的精髓所在。

先说说μ的定义

  • n为无平方因子数且n的标准分解中有偶数个质数,μ(n) = 1;
  • n为无平方因子数且n的标准分解中有奇数个质数,μ(n) = -1;
  • n为有平方因子数时,μ(n) = 0。

 

  • μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
  • μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
  • μ(n) = 0 if n has a squared prime factor.

source: Wikipedia(En)

看到这个定义,大家想必会非常奇怪——这种sb的定义是谁想出来的,一点也不优美!

但是,大家且和我看看别处:

狄利克雷卷积

(不得不吐槽,wordpress真的好菜菜啊,不能用LaTeX,只能靠截图,不然这篇博客好打多了)

又是定义

TIM截图20180712174346.png

其中,fg为数论函数(定义域为R,值域为C的函数),* 代表的就是狄利克雷卷积。

不难看出,在狄利克雷卷积的意义下,单位元为函数:TIM截图20180712175524.png

另参见:Dirichlet convolution

看到单位元,很自然的便想到逆元。在乘法意义下,最特殊的数莫过于是1了,它的乘法逆元就是它本身。那我们合不考虑在狄利克雷卷积的意义下 1 函数(函数值恒为1)的逆元呢?

不难猜出发现这个函数就是莫比乌斯函数

证明过程(太懒了,不想打公式了233)

那这个性质就可以写成一个求和(卷积)的形式

TIM截图20180713193453

这个性质在推式子的时候非常有用。

 

有了以上知识,莫比乌斯反演就呼之欲出了。

 

莫比乌斯反演

和大多数反演(反演好多啊。。。以后应该还会专门写这样的博客吧好一个flag)一样,莫比乌斯反演就是在一种卷积的意义下通过已知量关于未知量的表达式来求得未知量的方法。

考虑以下问题:

已知 ,且 f * 1 = g ,

我们可以先回忆一下当这种卷积是各个情况时,我们会怎么做:

  1. 加法,如 x+3=5 我们通常在等式两边同时减去3
  2. 乘法,如 3×x=6 我们通常在等式两边同时除以3
  3. 模意义乘法,如 3×x=1(mod 2) 我们通常在等式两边同时乘以1
  4. ……

看到这儿,大概也就有了眉目:在一种卷积意义下,只要在等式的两边同时卷上该卷积意义下与x做卷积的数的逆元,就可以得到答案辣!

那么,我们是不是只要在等式两边同时卷上μ就稳了啊?

TIM截图20180713204316.png

这就是传说中的莫比乌斯反演了啊。。。是不是很好理解啊233

 

那么这篇博客就先到这里了啊,还有一些技巧一类的东西就以后在写题目题解的时候写吧!

 

顺便,之后更新的时候会把自己之前做给同学上课用的ppt发上来啊,敬请期待吧

(感慨一句,一万年之后终于写了博客了啊啊啊)

non-rotating Treap op.1

之前只学过Treap,然后还没写完就不知道去干啥了,昨天刚好有机会,就请了机房数据结构大佬——xtr教了教我,感觉还不是很难啊。数据结构真有趣

首先假装大家都会了二叉搜索树,并且知道了为什么它会变得不平衡。

然后呢,就可以像随机化快排一样的思路,把读入ramdom shuffle一下,是不是期望上就是平衡了呀?

不过由于输入与查询是有先后次序的,所以我们只能在每个节点上动手脚。

所以我们引入一个随机的priority值,作为每个节点的属性之一,然后要求:每个节点的priority都必须严格满足比父节点的大(或小),再以此建立一棵二叉搜索树,就成了“treap”(tree+heap)了呀!

可以证明,只要priority值与每个节点的键值确定,整棵树的形态就会确定了。

一般的treap对于priority满足靠旋转操作,想必大家都知道,这里就不再赘述。但是,有旋转的treap有几点不足:

  1. 不能进行“可持久化”;
  2. 不能快速地提取出一段区间;
  3. 不能实现区间反转;
  4. 想必还有很多啊……

所以,某位大佬突发奇想,就想出了一种新型的treap,它维持平衡的方式与treap相同,但是维护堆性质采取了不同的方法——分裂与合并。

首先说分裂:

分裂分为两种:按排名分裂与按键值分裂,我们可以分别命名为split_kth与split_key,他们的作用就是将一棵子树分裂为两颗,且左边的一棵排名/键值都小于等于k,右边大于k。

那么,可以怎么实现呢?

来看图:

一张图读懂split(逃

split

可以看出,split是一个递归的过程,边界条件是该子树为空

然后呢……详情见代码,不过还是推荐大家自己思考一下

[code language = cpp]

void split_key(node* rt, node* &x, node* &y, int k)
{
if (rt == NULL)
{
x = y = NULL;
return;
}
if (key_of(rt) > k) y = rt, split_key(rt->ch[0], x, rt->ch[0], k);
else x = rt, split_key(rt->ch[1], rt->ch[1], y, k);
update(rt);
}

void split_kth(node* rt, node* &x, node* &y, int k)
{
if (rt == NULL)
{
x = y = NULL;
return;
}
if (size_of(rt->ch[0]) + 1 ch[1], rt->ch[1], y, k – size_of(rt->ch[0]) – 1);
else y = rt, split_kth(rt->ch[0], x, rt->ch[0], k);
update(rt);
}

[/code]
然后是merge:

这就没split那么烦了,还要分成两个段,还要传参。只要几个简简单单的if语句就能够实现(不过当然是递归的啦)。

要注意的是,merge操作只能合并两端原本就绝对有序的子树——分别满足二叉搜索树的条件且左子树的节点键值全部小于右子树的。

一张图读懂merge(逃

merge

又是代码……我好懒啊

[code language = cpp]

node* merge(node* x, node* y)
{
if (x == NULL) return y;
if (y == NULL) return x;
if (x->p > y->p)
{
y->ch[0] = merge(x, y->ch[0]), update(y);
return y;
}
x->ch[1] = merge(x->ch[1], y), update(x);
return x;
}

[/code]

以上就是treap的基本操作,然后就可以利用这两个字操作来实现其他的一切啦!

首先是最基本的插入:

可以按照键值k分裂成两颗子树,再把新增的节点当做一颗子树一一合并即可。详见代码

[code language = cpp]

inline void insert(int k)
{
node *x, *y;
split_key(root, x, y, k);
root = merge(x, newnode(k));
root = merge(root, y);
}

[/code]

还有删除:

删除也分为按键值删除与按排名删除

方法是:先找到权值或排名为k的一棵子树或一个节点,之后根据要删除单个节点或是所有节点删除一棵子树或将两个子节点合并到原来节点的位置上。

代码:

[code language = cpp]

inline void del_subtree(node* &rt)
{
if (rt->ch[0] != NULL) del_subtree(rt->ch[0]);
if (rt->ch[1] != NULL) del_subtree(rt->ch[1]);
delete rt;
}

inline void del_node(node* &rt)
{
node* o = rt;
rt = merge(rt->ch[0], rt->ch[1]);
delete o;
}

bool delete_key(int k, bool op) //op == 0 delete one, op == 1 delete all
{
int flag = 1;
node *x, *y, *o;
split_key(root, x, y, k – 1);
split_key(y, o, y, k);
if (o == NULL) flag = 0;
if (op) del_subtree(o);
else del_node(o);
y = merge(o, y);
root = merge(x, y);
return flag;
}

bool delete_kth(int k)
{
bool flag = 1;
node *x, *y, *o;
split_kth(root, x, y, k – 1);
split_kth(y, o, y, 1);
if (o == NULL) flag = 0;
del_node(o);
y = merge(x, y);
root = merge(o, y);
return flag;
}

[/code]

还有排名、前驱、后继、第k小数等等我就不多说了,直接上代码(并不能掩饰我的懒)

[code language = cpp]

namespace nrtreap
{
struct node
{
int p, v, size;
node *ch[2];
} *root;

static inline int size_of(node* o)
{
if (o == NULL) return 0;
return o->size;
}

static inline int key_of(node* o)
{
if (o == NULL) return 0;
return o->v;
}

node* newnode(int x)
{
node *o = new node;
o->p = rand() % 100000 + 1, o->v = x, o->size = 1;
o->ch[0] = o->ch[1] = NULL;
return o;
}

inline void update(node* o)
{
o->size = size_of(o->ch[0]) + size_of(o->ch[1]) + 1;
}

node* merge(node* x, node* y)
{
if (x == NULL) return y;
if (y == NULL) return x;
if (x->p > y->p)
{
y->ch[0] = merge(x, y->ch[0]), update(y);
return y;
}
x->ch[1] = merge(x->ch[1], y), update(x);
return x;
}

void split_key(node* rt, node* &x, node* &y, int k)
{
if (rt == NULL)
{
x = y = NULL;
return;
}
if (key_of(rt) > k) y = rt, split_key(rt->ch[0], x, rt->ch[0], k);
else x = rt, split_key(rt->ch[1], rt->ch[1], y, k);
update(rt);
}

void split_kth(node* rt, node* &x, node* &y, int k)
{
if (rt == NULL)
{
x = y = NULL;
return;
}
if (size_of(rt->ch[0]) + 1 ch[1], rt->ch[1], y, k – size_of(rt->ch[0]) – 1);
else y = rt, split_kth(rt->ch[0], x, rt->ch[0], k);
update(rt);
}

inline void insert(int k)
{
node *x, *y;
split_key(root, x, y, k);
root = merge(x, newnode(k));
root = merge(root, y);
}

inline void del_subtree(node* &rt)
{
if (rt->ch[0] != NULL) del_subtree(rt->ch[0]);
if (rt->ch[1] != NULL) del_subtree(rt->ch[1]);
delete rt;
}

inline void del_node(node* &rt)
{
node* o = rt;
rt = merge(rt->ch[0], rt->ch[1]);
delete o;
}

bool delete_key(int k, bool op) //op == 0 delete one, op == 1 delete all
{
int flag = 1;
node *x, *y, *o;
split_key(root, x, y, k – 1);
split_key(y, o, y, k);
if (o == NULL) flag = 0;
if (op) del_subtree(o);
else del_node(o);
y = merge(o, y);
root = merge(x, y);
return flag;
}

bool delete_kth(int k)
{
bool flag = 1;
node *x, *y, *o;
split_kth(root, x, y, k – 1);
split_kth(y, o, y, 1);
if (o == NULL) flag = 0;
del_node(o);
y = merge(x, y);
root = merge(o, y);
return flag;
}

int rank(int k)
{
node *x, *y;
split_key(root, x, y, k – 1);
int ret = size_of(x) + 1;
root = merge(x, y);
return ret;
}

int prev(int k)
{
node *x, *y, *o;
split_key(root, x, y, k – 1);
split_kth(x, x, o, size_of(x) – 1);
int ret = key_of(o);
x = merge(x, o);
root = merge(x, y);
return ret;
}

int succ(int k)
{
node *x, *y, *o;
split_key(root, x, y, k);
split_kth(y, o, y, 1);
int ret = key_of(o);
y = merge(o, y);
root = merge(x, y);
return ret;
}

int findkth(int k)
{
node *x, *y, *o;
split_kth(root, x, y, k – 1);
split_kth(y, o, y, 1);
int ret = key_of(o);
y = merge(o, y);
root = merge(x, y);
return ret;
}
}

[/code]

至于其他操作(比如翻转,标记)就下次再说吧。
有问题可以在下面评论或者联系我

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