分类：高级数据结构

【可持久化数据结构初步】

先来一波可持久化线段树，又名主席树。在可持久化数据结构中，能够支持查询历史版本的数据。是对原数据结构的进一步加深与理解，代码和原理也只能算是锦上添花。借用某大犇的话讲就是，“主席树难不是在于它自身，而是难在于如何把一道题跟它扯上关系”

下面进入正题：

在某些题目中，我们可能需要不断地对线段树修改，并且有可能需要查询的是某一次修改前的事情，而在线段树中，修改即意味着是数据丢失，是难以查询到从前的东西。而可持久化的基本理念就是不将其修改，而是扩建。

初步的想法是对于一次修改就重新搞一棵树出来，但是这在空间上是极度不允许的。我们能够联想到，对于一次修改，复杂度是log（n）级别的，这说明了一次修改所涉及到的区间只有log（n）个，故我们没有必要每次完整地建一棵线段树，只需要新建log（n）个被修改的区间，其他的未被操刀过的区间借用前者的区间即可。每一次修改扩建log（n）个，这是能够勉强接受的。

在此顺便注一句：一定要计算好空间！！！不要像我一样空间算错了开太小然后查了一小时错都没查出来！！！！！！！！后来跟标程一字一字进行了一场“代码优先性逐行逐字比较型工程”才发现标程空间比我多了一点点......

 

【代码环节】

例题：洛谷P3834

这是我阅览了十多份代码中，风格最为人性化的一种



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
#include<cstdio>

#include<algorithm>

#include<iostream>

#define mid (l+r)/2

#define N 200005

using namespace std;



struct node

{

    int val,id;

};



struct chariman

{

    int l,r;

    int sum;    

}tree[N*20];



bool cmp(node aa,node bb)

{

    return aa.val<bb.val;

}



int n,q,a[N],root[N],cnt;

node b[N];



void updata(int &st,int l,int r,int p)

{

    tree[++cnt]=tree[st];

    st=cnt;

    tree[st].sum++;

    if (l==r) return;

    if (p<=mid) updata(tree[st].l,l,mid,p);

        else updata(tree[st].r,mid+1,r,p);

    return;

}



int query(int i,int j,int k,int l,int r)

{

    if (l==r) return l;

    int ltot=tree[tree[j].l].sum-tree[tree[i].l].sum;

    if (k<=ltot) return query(tree[i].l,tree[j].l,k,l,mid);

            else return query(tree[i].r,tree[j].r,k-ltot,mid+1,r);

}



int main()

{

    scanf("%d %d",&n,&q);

    for (int i=1; i<=n; i++)

    {

        scanf("%d",&b[i].val);b[i].id=i;

    }

    sort(b+1,b+1+n,cmp);

    for (int i=1; i<=n; i++) a[b[i].id]=i;

    for (int i=1; i<=n; i++)

    {

        root[i]=root[i-1];

        updata(root[i],1,n,a[i]);

    }

    int x,y,k;

    while (q--)

    {

        scanf("%d %d %d",&x,&y,&k);

        printf("%d\n",b[query(root[x-1],root[y],k,1,n)].val);

    }

    return 0;

}

【PAUSE】

Day7

【最长上升子序列】
题意：对一个序列进行操作，可以在序列最后加上一个数，可以回到k时的序列，求每次操作后序列的最长上升子序列长度。
【LIS求法】：通常求最长上升子序列都是n^2动规，当n较大时便要考虑nlogn的算法。
设f[k]表示长度为k的LIS最末尾的元素，易知f是单调递增的，对于新加入的x，如果f[k] < x， 意味着最长上升子序列的长度可以加1。如果f[k] > x，那么 对于f[i] > x > f[i - 1]考虑f第i位的值哪个更优？显然要取x。求i可以用二分优化，LIS便能在nlongn的时间内求出。
这题需要回到第k时的序列，由上述算法可知，对于操作j、j - 1，f数组的变化只有一个数，于是用可持久化线段树来维护这个数组，使修改和查询的时间变成logn， 时间复杂度是O(nlog^2n)。
由于时间复杂度和空间复杂度与题目要求十分相近，要考虑常数与每个结点的线段树子节点数量。
正解对于每个回到k序列的操作建一棵树，直接在这棵树上跑LIS，时间复杂度O(nlogn)。
【图的X匹配】
题意：对于一个多边形，使取出的边没有交点（即没有相邻的边）的方案数。
打表可以发现答案的规律类似斐波那契数列， 由于没有取模， 需要用高精度完成加法操作， n的值最大为10000， 最好用滚动数组。
证明：
【努力】
题意：使n个点形成一棵树的连边方法。
由prufer数列可得n个点的无向图有n^(n-2)种， n个点的树有n-1条边，答案便是n^(n-2)*(n-1)!。

代码如下：

继续阅读Day7

Day5

【匹配】
简单的模拟题，这里略过。

【矩形】
题意：给出n条直线，求组成的矩形个数。
60%的做法，先枚举两条平行的直线，再枚举垂直于前两条直线且有交点的线，用排列组合求出答案。这个做法是O(n^3)。
由数据范围可知O(n^3)的时间复杂度刚好超时，考虑优化上面的算法，用bitset记录每两条直线是否相交，那么，求垂直于两条直线且相交就变成了求两条直线bitset的和（&）。由于直线分为两种，垂直于x轴与平行于x轴，可以枚举直线少的来进行&操作。时间复杂的为O(n^3/128)。
正解为树状数组（线段树）来维护两条平行直线间共有的相交直线数。时间复杂度O(n^2longn)。

【历史】
题意：每次连一条边，询问两个点是否在t之前不联通，在当前时刻联通，强制在线。
由于强制在线的是连接的边，对于询问并没有要求强制在线，那么，先将询问存下来，对于t之前的状态可在t时记录，t的状态可直接得到。
正解是可持久化并查集， 用可持久化线段树维护可持久化数组，由于修改的只能是一个数，所以合并并查集时不能用路径压缩，需要用启发式合并，那么，对于每个询问只需查找当前数组和前t的数组即可。

代码如下（可持久化并查集代码明天补充）

继续阅读Day5

主席树

主席树又称函数式线段树，就是通过函数来实现的线段树，可以处理一些神奇的问题。

【例题】K-th Number

  • 很明显，这题的数据是不允许对于每一个询问进行一次排序的。那么，考虑一种解法，建你n棵线段树，第i棵线段树维护的是1~i中，大小属于[1,m]的数的数量（1 <= m <= max)。对于每次询问的L,R区间中的第k小数，便可以通过log(n)的时间来完成。
  • 显然我们不能直接全部建出来， 这样时空复杂度都不允许。我们发现相邻的两棵线段树的差别只是i比i-1多了a[i]这个数， 而在权值线段树中多出这样一个值， 第 i 棵树
    与第 i -1棵树的差别实际上只有log 个节点。 也就是我们可以看做在第 i -1
    棵权值线段树中插入权值a[i] 得到第 i 棵权值线段树， 而单点插入过程中只会遇到以及修改根到那个叶子路径上的log(n)个节点。
  • 假设我们已经得到了第 i -1棵权值线段树， 现在要在第i -1棵的基础上加入权值
    a[i]来得到第i 棵树。 首先我们新建一个节点来表示第i 棵树的根节点， 接着我们从第i -1棵以及第i棵树的根节点开始考虑。 对于当前节点， 若当前插入的值a[i] 在当前权值区间中的左半部分，说明a[i] 它要影响第 i 棵树当前节点的左子树的值， 则我们新建一个左儿子， 作为第 i 棵树对应的当前节点左儿子； 而第i 棵树对应的当前节点右儿子（ 子树） ， 它（ 们） 并不受新插入的值的影响， 因此它与第 i -1棵树的当前节点的右儿子（ 子树） 的信息一模一样， 所以我们考虑直接将第 i 棵树对应的当前节点右儿子设为第i -1棵树的当前节点的右儿子。 反之亦然。
    插入的代码如下：

    

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void add(int &cnt, int last, int l, int r, int v)  {
    
    cnt = ++tot;
    
    tr[cnt] = tr[last];
    
    tr[cnt].sum++;
    
    if (l < r)  {
    
        if (v <= (l + r) / 2) add(tr[cnt].ls, tr[last].ls, l, (l + r) / 2, v);
    
        else add(tr[cnt].rs, tr[last].rs, (l + r) / 2 + 1, r, v);
    
    }
    
}

那么对于每一个询问，代码就显而易见了：



1
2
3
4
5
6
7
int que(int pas, int now, int l, int r, int k)  {

    if (l == r) return l;

    int s = tr[tr[now].ls].sum - tr[tr[pas].ls].sum;

    if (k <= s) return que(tr[pas].ls, tr[now].ls, l, (l + r) / 2, k);

    return que(tr[pas].rs, tr[now].rs, (l + r) / 2 + 1, r, k - s);



}

具体代码如下：

继续阅读主席树

[BZOJ 1901] Dynamic Rankings

树状数组套主席树。

考虑无修改求区间第 K 大的情况：因为主席树之间支持相加减，故可以维护一些包含 1~i 的线段树，计算它们的树前缀和，从而快速得到区间 [l, r] 中的第 K 大数。

考虑对于数的静态区间和与动态区间和的关系——前缀和与树状数组。

类似地，我们可以维护一个树状数组，但线段树记录的不再是前缀和，而是树状数组的辅助数组的值。

这样就能做到带修改的区间第 K 大值查询了。

Reference:

http://blog.csdn.net/u014664226/article/details/47839973

代码如下：

继续阅读[BZOJ 1901] Dynamic Rankings

BZOJ2588 Spoj 10628. Count on a tree

BZOJ2588

求树上路径上节点权值k小。

可以发现树上两点u，v之间的第k小点权等价于(root <-> u) + (root <-> v) - (root <-> lca(u, v)) - (root <-> father[lca(u, v)])上的第k小点权，其中root为根节点，lca(u, v)为u和v的最近公共祖先，father[lca(u, v)]为lca(u, v)的父节点。

那么可以维护root到所有节点的权值，显然root到某个点x的权值和root到x父节点的权值只有点x这个点权的差别，那么可以用主席树维护这个东西了。

继续阅读BZOJ2588 Spoj 10628. Count on a tree

[FJOI2016]神秘数

神秘数。同BZOJ4299。

10%：枚举每个数字作为神秘数，搜索判断

30%：显然可以发现一个性质：假设当前神秘数为ans，那么可以被表示的区间为[1, ans - 1]。若加入一个数x，且x满足1xans + 1，则神秘数变为ans + x。初始的神秘数为0。那么对于每个询问，将区间内的数排序，依次判断即可。

60%：迷之写法，或者是写丑的100%。

100%：30%的方法不容易维护，考虑对于一个数x，若x不可被表示，条件为区间内所有小于x的数的和小于x，这个东西可以用树套树或者主席树维护。（看神犇们的代码好像可以不用离散化，时间少一个log

继续阅读[FJOI2016]神秘数

第K小的数

第K小的数

维护不带修改的区间第k小，分块，划分树都可以做。

然而最常用的是以下做法：主席树或可持久化线段树（我也不知道二者有什么差别。

对于每个区间[1,i]建立一棵权值线段树，显然它与[1,i-1]的差别只有一条链，那么只要建立那条链上的节点就可以了。

继续阅读第K小的数