Post 17

Veröffentlicht am | Edited on

不管前方的路有多苦，只要走的方向正确，不管多么崎岖不平，都比站在原地更接近幸福。

可持久化线段树

又名函数式线段树，是重要的数据结构之一。支持静态区间第k小。

主要思想就是能利用现有不变的节点就不开点，每次只会增加

个节点.

为了让BLOG看上去不是那么空，我们找几张图来理解一下

FotileTree

这张图应该很好懂每次插入。

主席树一个经典的运用是区间第k大问题。

显然它的内部结构是不变的，满足可减性。可以用差分来处理（减掉）左端点左边的。

又因为我们是把节点一个一个插进去的，因此对于每个前缀我们都能通过

访问，就可以询问右端点。

现在我们知道如何确定在这个区间查询，然后在这个区间内如何用线段树查询区间第k大呢？

很显然需要使用权值线段树，对于当前区间，我们记录每个值域节点有多少个数！假设查询到节点k，假如k的左节点的值大于k，就继续向左节点递归，否则递归右节点k-cnt。

和Treap是相似的。

还有一个奇怪的地方是离散化相同的值不能给相同的权排名，否则会WA

然后就可以上模板题了。

【模板】可持久化线段树 1（主席树）

题目背景

这是个非常经典的主席树入门题——静态区间第K小

数据已经过加强，请使用主席树。同时请注意常数优化

题目描述

如题，给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

输入输出格式

输入格式：

第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个正整数，表示这个序列各项的数字。

接下来M行每行包含三个整数l, r, kl,r,k , 表示查询区间[l, r][l,r]内的第k小值。

输出格式：

输出包含k行，每行1个正整数，依次表示每一次查询的结果

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

输出样例#1：

1
2
3
4
5
6405
15770
26287
25957
26287

说明

数据范围：

题解

分析同上。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <map>
#define maxn 200005
struct Node{
	int v , k;
	bool operator<(const Node& x)const{
		return v < x.v;
	}
}p[maxn];
int v[maxn] , n , m , ct , rev[maxn];
struct FortileTree
{
	int lc[maxn<<5] , rc[maxn<<5] , tot , rt[maxn] , val[maxn<<5];
	int insert(int now , int l , int r , int pos , int vk)
	{
		int p = ++tot;
		lc[p] = lc[now];
		rc[p] = rc[now];
		val[p] = val[now];
		if(l == r){
			val[p] += vk;
			return p;
		}
		int mid = l + r >> 1;
		if(pos <= mid) lc[p] = insert(lc[now] , l , mid , pos , vk);
		else rc[p] = insert(rc[now] , mid + 1 , r , pos , vk);
		val[p] = val[lc[p]] + val[rc[p]];
		return p;
	}
	void build(int &p , int l , int r)
	{
		p = ++tot;
		if(l == r) return;
		int mid = l + r >> 1;
		build(lc[p] , l , mid);
		build(rc[p] , mid + 1 , r);
		val[p] = val[lc[p]] + val[rc[p]];
	}
	int query(int p , int q , int l , int r , int k)
	{
		int mid = l + r >> 1 , cnt = val[lc[q]] - val[lc[p]];
		if(l == r) return l;
		if(k <= cnt) return query(lc[p] , lc[q] , l , mid , k);
		else return query(rc[p] , rc[q] , mid + 1 , r , k - cnt);
	}
}tr;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&p[i].v) , p[i].k = i;
	std::sort(p+1,p+n+1);

	for(int i = 1 ; i <= n ; ++i)
		v[p[i].k] = ++ct , rev[ct] = p[i].v;
	tr.build(tr.rt[0] , 1 , ct);
	for(int i = 1 ; i <= n ; ++i)
		tr.rt[i] = tr.insert(tr.rt[i-1] , 1 , ct , v[i] , 1);
	for(int i = 1 ; i <= m ; ++i)
	{
		int x , y , z;
		scanf("%d%d%d",&x,&y,&z);
		if(z > y - x + 1) {puts("0") ; continue;}
		printf("%d\n",rev[tr.query(tr.rt[x-1],tr.rt[y],1,ct,z)]);
	}
}

【模板】可持久化数组

题目背景

UPDATE : 最后一个点时间空间已经放大

标题即题意

有了可持久化数组，便可以实现很多衍生的可持久化功能（例如：可持久化并查集）

题目描述

如题，你需要维护这样的一个长度为 NN 的数组，支持如下几种操作

  1. 在某个历史版本上修改某一个位置上的值
  2. 访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91

输出样例#1：

1
2
3
4
5
6
59
87
41
87
88
46

说明

数据规模：

经测试，正常常数的可持久化数组可以通过，请各位放心

数据略微凶残，请注意常数不要过大

另，此题I/O量较大，如果实在TLE请注意I/O优化

询问生成的版本是指你访问的那个版本的复制

题解

显然这时候就不需要向区间静态第k大一样去建权值线段树了，每次操作我们都新生成一条链，加在主席树上

时间复杂度

，空间复杂度

不过对于此题还是能较轻松通过的。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1000005
inline int read()
{
    int x = 0 , f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1 ;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 3) + (x << 1) + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n , m , lc[maxn<<5] , rc[maxn<<5] , v[maxn<<5] , tot, root[maxn], p[maxn];
void build(int &node , int l , int r)
{
    node = ++tot;
    if(l == r)
    {
        v[node] = p[l];
        return;
    }
    int mid = l + r >> 1;
    build(lc[node] ,l ,mid);
    build(rc[node] ,mid + 1 , r);
}
int modify(int p , int l , int r , int node , int val)
{
    int np = ++tot;
    lc[np] = lc[node];
    rc[np] = rc[node];
    if(l == r){
        v[np] = val;
        return np;
    }
    int mid = l + r >> 1;
    if(p <= mid)
        lc[np] = modify(p , l , mid , lc[node] , val);
    else rc[np] = modify(p ,  mid + 1 , r , rc[node] , val);
    return np;
}
int query(int p , int l , int r , int pos)
{
    int mid = l + r >> 1;
    if(l == r)	return v[p];
    if(pos <= mid) return query(lc[p] , l , mid , pos);
    else return query(rc[p] , mid + 1 , r , pos);
}
int main()
{
    n = read() , m = read();
    for(int i = 1 ; i <= n ; ++i)
        p[i] = read();
    build(root[0],1,n);
    for(int i = 1 ; i <= m ; ++i)
    {
        int ver , ty, x , y;
        ver = read() , ty = read() , x = read();
        if(ty == 1){
            y = read();
            root[i] = modify(x , 1 , n , root[ver] , y);
        }
        else if(ty == 2){
            root[i] = root[ver];
            printf("%d\n",query(root[ver] , 1 , n , x));
        }
    }
}

【模板】可持久化并查集

题目描述

n个集合 m个操作

操作：

  • 1 a b 合并a,b所在集合
  • 2 k 回到第k次操作之后的状态(查询算作操作)
  • 3 a b 询问a,b是否属于同一集合，是则输出1否则输出0

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2

输出样例#1：

1
2
3
1
0
1

说明

题解

算是个比较重要的数据结构吧。

学习和调试的时间不短，加起来高达3个小时多，其中思考的问题与最后理清的思路就分享下吧。

首先要说一句基本的并查集按秩合并：当两颗树的高度一样的时候合并显然合并后的那个根节点的深度是原来+1，不妨自己画图看看。其他情况的话就是维持高度大的那个。

再一点，要把思路理清楚，显然几个函数的功能明确，共同完成维护可持久化不相交集合。

也就是说平常我们写的并查集只需要把每个点换成在函数式线段树上二分查找就可以了。

详细说说：

初始化建树

1
2
3
4
5
6
7
void build(int &rt,int l,int r)
{
    rt=++cnt;
    if(l==r){fa[rt]=l;return ;}
    build(lson);build(rson);
}
// 就是普通的可持久化数组构建法，不过维护的是Fa而已

trick：传址使得维护父子关系更加方便。

合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void merge(int las , int &now , int l , int r, int pos , int fa)
{
	now = ++ tot;
	lc[now] = lc[las];
	rc[now] = rc[las];
	if(l == r)
	{
		f[now] = fa;
		dep[now] = dep[las];
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid) merge(lc[las] , lc[now] , l , mid , pos , fa);
	else merge(rc[las] , rc[now] , mid + 1 , r , pos , fa);
}

pos和Fa我们会在主函数中用后面介绍的find函数找到，分别表示两个联通块的根节点。别忘了给dep赋值。

查询某一个值所在可持久化数组中的下标

1
2
3
4
5
6
7
8
int query(int node , int l , int r , int pos)
{
	if(l == r)
		return node;
	int mid = l + r >> 1;
	if(pos <= mid) return query(lc[node] , l , mid , pos);
	else return query(rc[node] , mid + 1 , r , pos);
}

相当于一个数组下标为pos的值，rt是功能需要（通过root进入主席树）。

查找祖先

1
2
3
4
5
6
int find(int x , int p)
{
	int now = query(x , 1 , n , p);
	if(f[now] == p) return now;
	return find(x , f[now]);
}

显然找到当前点在树上的节点然后访问其父亲，和并查集类似，除了访问元素需要二分查找。

这样一来我们就可以上最后跑的挺快的代码了。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 200005
int lc[maxn<<5] , rc[maxn<<5] , dep[maxn<<5] , f[maxn<<5] , n , m , tot , root[maxn];
void build(int &now , int l , int r)
{
    now = ++tot;
    if(l == r){
        f[now] = l;
        return;
    }
    int mid = l + r >> 1;
    build(lc[now] , l , mid);
    build(rc[now] , mid + 1 , r);
    return;
}
void merge(int las , int &now , int l , int r, int pos , int fa)
{
    now = ++ tot;
    lc[now] = lc[las];
    rc[now] = rc[las];
    if(l == r)
    {
        f[now] = fa;
        dep[now] = dep[las];
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) merge(lc[las] , lc[now] , l , mid , pos , fa);
    else merge(rc[las] , rc[now] , mid + 1 , r , pos , fa);
}
int query(int node , int l , int r , int pos)
{
    if(l == r)
        return node;
    int mid = l + r >> 1;
    if(pos <= mid) return query(lc[node] , l , mid , pos);
    else return query(rc[node] , mid + 1 , r , pos);
}
int find(int x , int p)
{
    int now = query(x , 1 , n , p);
    if(f[now] == p) return now;
    return find(x , f[now]);
}
int main()
{
    scanf("%d%d",&n,&m);
    build(root[0] , 1 , n);
    for(int i = 1 ; i <= m ; ++i)
    {
        int x , y , op;
        scanf("%d%d",&op,&x);
        if(op == 1)
        {
            root[i] = root[i-1];
            scanf("%d",&y);
            int fx = find(root[i] , x) , fy = find(root[i] , y);
            if(f[fx] != f[fy])
            {
                if(dep[fx] > dep[fy]) std::swap(fx , fy);
                merge(root[i-1] , root[i] , 1 , n , f[fx] , f[fy]);
                if(dep[fx] == dep[fy]) dep[fy] ++ ;
            }
        }
        else if(op == 2) root[i] = root[x];
        else
        {
            root[i] = root[i-1];
            scanf("%d",&y);
            int fx = find(root[i] , x) , fy = find(root[i] , y);
            if(f[fx] != f[fy]) puts("0");
            else puts("1");
        }
    }
}

可持久化Trie

一如既往的可持久化思想，和前面介绍的可持久化线段树很想。

原理简单来说就是对于当前节点u以及上次插入的同深度的节点v，如果它们有共同的边指向父亲（显然某个地方断开了后面也不能再连节点了，Trie定义。假设能连，那就同时让u,v到下一字符c子节点），u需要继承v的所有儿子，除了当前字符c依旧需要新建节点以外，其他点都用v即可。

显然和原来Trie的空间复杂度是一样的，时间复杂度同样都是线性关于插入字符串总长。

举道例题：

最大异或和

题目描述

给定一个非负整数序列\{a\}，初始长度为N。

有M个操作，有以下两种操作类型：

  1. A x：添加操作，表示在序列末尾添加一个数xx，序列的长度N+1。

  2. Q l r x：询问操作，你需要找到一个位置pp，满足

    ，使得：

    最大，输出最大是多少。

输入输出格式

输入格式：

第一行包含两个整数 N,M，含义如问题描述所示。
第二行包含 N个非负整数，表示初始的序列A 。
接下来 M行，每行描述一个操作，格式如题面所述。

输出格式：

假设询问操作有 T 个，则输出应该有 T行，每行一个整数表示询问的答案。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
5  5
2  6 4 3 6
A 1 
Q 3 5 4 
A 4
Q 5 7 0 
Q 3 6 6

输出样例#1：

1
2
3
4
5
6

说明

题解

一般看到连续的异或区间不难想到前缀异或。因为对于一个连续的区间异或和就是

然后我们相当于对询问快速给出

问题其实转换成给出一个数（24位无符号01串也行）

让你在数组一个范围内找到那个符合条件的数。

复习下用Trie如何贪心找一个数最大异或值：由于从高位开始，所以能反就反，因为后面就算所有位都能反，其和也小于当前一位。

我们能不能用普通的Trie插入然后打上结束标记呢？也不是不行，我们给每个Trie节点一个vector，然后把子节点的下标（读入顺序）合并到vector，然后查询的时候就可以看看和当前位异或的节点的vector里有没有在l~r中的。显然这个复杂度很爆炸，每次查找实际上是

的。

显然使用可持久化我们可以退回r-1那个版本，这样我们只需要找一个最大的了（因为肯定满足小于r），就像线段树一样向上合并最大值就可以了（因为要尽量找到大于等于l-1的与这位相反的数），假设有，那就选择这个节点，没有就走另一边。

显然正确性同上面所述。

这样我们就有了

的算法。

读入优化可通过本题。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 500005
int p , s[maxn] , tr[maxn<<5][2] , n , tot , root[maxn<<1] , m , mk[maxn<<5];
void insert(int node , int preNode , int k , int len)
{
    if(!~len){
        mk[node] = k;
        return;
    }
    int c = s[k] >> len & 1;
    if(preNode) tr[node][c ^ 1] = tr[preNode][c ^ 1];
    tr[node][c] = ++tot;
    insert(tr[node][c] , tr[preNode][c] , k , len - 1);
    mk[node] = std::max(mk[tr[node][c]] , mk[tr[node][c^1]]);
}
int query(int node , int val , int limit , int len)
{
    if(!~len)	return s[mk[node]] ^ val;//!~!~!~!~!~do not forget ! , !!!
    int c = val >> len & 1;
    if(mk[tr[node][c^1]] >= limit)
        return query(tr[node][c^1] , val , limit , len - 1);
    else return query(tr[node][c] , val , limit , len - 1);
}
int main()
{
    std::memset(mk,-1,sizeof(mk));
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&p) , s[i] = s[i-1] ^ p;
    root[0] = ++tot;
    insert(root[0] , 0 , 0 , 24);
    for(int i = 1 ; i <= n ; ++i)
        root[i] = ++tot , insert(root[i] , root[i-1] , i , 24);
    for(int i = 1 ; i <= m ; ++i)
    {
        char op;
        scanf("\n%c",&op);
        if(op == 'A')
        {
            int x;
            scanf("%d",&x);
            root[++n] = ++tot;
            s[n] = s[n-1] ^ x;
            insert(root[n] , root[n-1] , n , 24);
        }
        else{
            int x , y , z;
            scanf("%d%d%d",&x,&y,&z);
            z ^= s[n];
            printf("%d\n",query(root[y-1] , z , x-1 , 24));
        }
    }
}

小a和uim之大逃离.

题目背景

小a和uim来到雨林中探险。突然一阵北风吹来，一片乌云从北部天边急涌过来，还伴着一道道闪电，一阵阵雷声。刹那间，狂风大作，乌云布满了天空，紧接着豆大的雨点从天空中打落下来，只见前方出现了一个披头散发、青面獠牙的怪物，低沉着声音说：“呵呵，既然你们来到这，只能活下来一个！”。小a和他的小伙伴都惊呆了！

题目描述

瞬间，地面上出现了一个n*m的巨幅矩阵，矩阵的每个格子上有一坨0~k不等量的魔液。怪物各给了小a和uim一个魔瓶，说道，你们可以从矩阵的任一个格子开始，每次向右或向下走一步，从任一个格子结束。开始时小a用魔瓶吸收地面上的魔液，下一步由uim吸收，如此交替下去，并且要求最后一步必须由uim吸收。魔瓶只有k的容量，也就是说，如果装了k+1那么魔瓶会被清空成零，如果装了k+2就只剩下1，依次类推。怪物还说道，最后谁的魔瓶装的魔液多，谁就能活下来。小a和uim感情深厚，情同手足，怎能忍心让小伙伴离自己而去呢？沉默片刻，小a灵机一动，如果他俩的魔瓶中魔液一样多，不就都能活下来了吗？小a和他的小伙伴都笑呆了！

现在他想知道他们都能活下来有多少种方法。

输入输出格式

输入格式：

第一行，三个空格隔开的整数n，m，k

接下来n行，m列，表示矩阵每一个的魔液量。同一行的数字用空格隔开。

输出格式：

一个整数，表示方法数。由于可能很大，输出对1 000 000 007取余后的结果。

输入输出样例

输入样例#1：

1
2
3
2 2 3
1 1
1 1

输出样例#1：

1
4

说明

【题目来源】

lzn改编

【样例解释】

样例解释：四种方案是：(1,1)->(1,2),(1,1)->(2,1),(1,2)->(2,2),(2,1)->(2,2)。

【数据范围】

对于20%的数据，n,m<=10,k<=2

对于50%的数据，n,m<=100,k<=5

对于100%的数据，n,m<=800,1<=k<=15

题解

很显然的方案数dp

状态肯定是

表示到(i,j)剩余k，是谁取的方案数为多少。

转移就是上一步可能的两个位置，加法原理。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 805
#define maxk 20
#define mod 1000000007
int f[maxn][maxn][maxk][2] , n , m , k , p[maxn][maxn];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	++k;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j)
			scanf("%d",&p[i][j]) , f[i][j][p[i][j]%k][0] = 1;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j)
			for(int t = 0 ; t <= k ; ++t)
			{
				(f[i+1][j][(t+p[i+1][j])%k][0] += f[i][j][t][1]) %= mod;
				(f[i][j+1][(t+p[i][j+1])%k][0] += f[i][j][t][1]) %= mod;
				(f[i+1][j][(t-p[i+1][j]+k)%k][1] += f[i][j][t][0]) %= mod;
				(f[i][j+1][(t-p[i][j+1]+k)%k][1] += f[i][j][t][0]) %= mod;
			}
	int ans = 0;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j)
			(ans += f[i][j][0][1]) %= mod;
	printf("%d",ans);

}

学习一下Splay吧。。。

虽然不会证复杂度不算学会Splay。。等下次回家看看Splay的复杂度证明。

学习源来自zyf学姐的blog！可能边学边copy过来了。。。

步入正题。

欢迎去学姐blog里学习。

https://blog.csdn.net/clove_unique/article/details/50630280

已经移动到LCT与均摊分析里。
区间树明天再学(上面的Treap不都能干嘛。。)