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

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

下面进入正题:

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

初步的想法是对于一次修改就重新搞一棵树出来,但是这在空间上是极度不允许的。我们能够联想到,对于一次修改,复杂度是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小的数