BZOJ1483 [HNOI2009] 梦幻布丁

BZOJ

洛谷

链表+启发式合并

懒得写链表

std::set代替链表

首先算出初始状态答案

然后对于每个修改操作,启发式合并两种颜色。

启发式合并:在合并两个集合(或两棵树)时,暴力将较小集合的元素(或结点更少的树的所有节点)合并(或插入)到另一较大集合(或结点更多的树)中。

简单来说就是弱肉强食。

而且启发式合并的时间复杂度可以证明是O(logn)的

对于本题,枚举较小的集合的每个元素,处理答案并且加入较大的集合,同时更改颜色。

对于查询操作,由于每次修改同时都计算出答案,直接输出即可。

继续阅读BZOJ1483 [HNOI2009] 梦幻布丁

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

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

下面进入正题:

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

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

线段树题目

适合非递归线段树的题目:

Codeforces 612D The Union of k-Segments :  题解
题意:线段求交,给定一堆线段,按序输出被覆盖k次或以上的线段和点。
基础题,先操作,最后一次下推标记,然后输出,
维护两个线段树,一个线段覆盖,一个点覆盖。

Codeforces 35E Parade : 题解

题意:给定若干矩形,下端挨着地面,求最后的轮廓形成的折线,要求输出每一点的坐标。

思路:虽然是区间修改的线段树,但只需要在操作结束后一次下推标记,然后输出,所以适合非递归线段树。

URAL 1846 GCD2010 :  题解

题意:总共10万个操作,每次向集合中加入或删除一个数,求集合的最大公因数。(规定空集的最大公因数为1)

Codeforces 12D Ball :   题解

题意:

给N (N<=500000)个点,每个点有x,y,z ( 0<= x,y,z <=10^9 )

对于某点(x,y,z),若存在一点(x1,y1,z1)使得x1 > x && y1 > y && z1 > z 则点(x,y,z)是特殊点。

问N个点中,有多少个特殊点。

提示:排序+线段树

Codeforces 19D Points : 题解

 

题意:

给定最多20万个操作,共3种:

1.add x y         :加入(x,y)这个点

2.remove x y  :删除(x,y)这个点

3.find x y         :找到在(x,y)这点右上方的x最小的点,若x相同找y最小的点,输出这点坐标,若没有,则输出-1.

提示:排序,线段树套平衡树

Codeforces 633E Startup Funding : 题解

这题需要用到一点概率论,组合数学知识,和二分法。

非递归线段树在这题中主要解决RMQ问题(区间最大最小值问题),由于不带修改,这题用Sparse Table求解RMQ是标答。

因为RMQ询问是在二分法之内求的,而Sparse Table可以做到O(1)查询,所以用Sparse Table比较好,总复杂度O(n*log(n))。

不过非递归线段树也算比较快的了,虽然复杂度是O(n*log(n)*log(n)),还是勉强过了这题。

扫描线题目:

 

POJ 1177 Picture:给定若干矩形求合并之后的图形周长    题解
HDU 1255 覆盖的面积:给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.   题解
HDU 3642 Get The Treasury:给定若干空间立方体,求重叠了3次或以上的体积(这个是扫描面,每个面再扫描线)题解
POJ 2482 Stars in your window : 给定一些星星的位置和亮度,求用W*H的矩形能够框住的星星亮度之和最大为多少。  题解

递归线段树题目:

Codeforces 558E A Simple Task  题解给定一个长度不超过10^5的字符串(小写英文字母),和不超过5000个操作。

每个操作 L R K 表示给区间[L,R]的字符串排序,K=1为升序,K=0为降序。

最后输出最终的字符串。

Codeforces 527C Glass Carving  :  题解
给定一个矩形,不停地纵向或横向切割,问每次切割后,最大的矩形面积是多少。
URAL1989 Subpalindromes    题解
给定一个字符串(长度<=100000),有10万个操作。
操作有两种:
1:改变某个字符。
2:判断某个子串是否构成回文串。
HDU 4288 Coder :  题解
 题意:对一个集合进行插入与删除操作。要求询问某个时刻,集合中的元素从小到大排序之后,序号%5 ==3 的元素值之和。
这题其实不一定要用线段树去做的,不过线段树还是可以做的。
HDU 2795 BillBoard : 题解

题意:有一个板,h行,每行w长度的位置。每次往上面贴一张海报,长度为1*wi .

每次贴的时候,需要找到最上面的,可以容纳的空间,并且靠边贴。

Codeforces 374D Inna and Sequence :题解
题意:给定百万个数a[m],然后有百万个操作,每次给现有序列加一个字符(0或1),或者删掉已有序列中,第 a[0] 个,第a[1]个,...,第a[m]个。
Codeforces 482B Interesting Array:  题解

题意就是,给定n,m.

满足m个条件的n个数,或说明不存在。

每个条件的形式是,给定 Li,Ri,Qi ,要求   a[Li]&a[Li+1]&...&a[Ri] = Qi ;

Codeforces 474E Pillar (线段树+动态规划):  题解

题意就是,给定10^5 个数(范围10^15),求最长子序列使得相邻两个数的差大于等于 d。

POJ 2777  Count Color :   题解

给线段涂颜色,最多30种颜色,10万个操作。

每个操作给线段涂色,或问某一段线段有多少种颜色。

30种颜色用int的最低30位来存,然后线段树解决。

URAL 1019 Line Painting: 线段树的区间合并  题解

给一段线段进行黑白涂色,最后问最长的一段白色线段的长度。

Codeforces 633H Fibonacci-ish II  :题解

这题需要用到莫队算法(Mo's Algorithm)+线段树区间修改,不过是单边界的区间,写起来挺有趣。

另一种解法就是暴力,很巧妙的方法,高复杂度+低常数居然就这么给过了。

树套树题目:

ZOJ 2112 Dynamic Rankings 动态区间第k大  题解
做法:树状数组套主席树 或者 线段树套平衡树
Codeforces 605D Board Game :  题解
做法:广度优先搜索(BFS)  +  线段树套平衡树

Codeforces 19D Points : 题解

 

题意:

给定最多20万个操作,共3种:

1.add x y         :加入(x,y)这个点

2.remove x y  :删除(x,y)这个点

3.find x y         :找到在(x,y)这点右上方的x最小的点,若x相同找y最小的点,输出这点坐标,若没有,则输出-1.

提示:排序,线段树套平衡树

一步一步理解线段树

摘自http://www.cnblogs.com/TenosDoIt/p/3453089.html


一 概述

线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(logn)。

线段树的每个节点表示一个区间,子节点则分别表示父节点的左右半区间,例如父亲的区间是[a,b],那么(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b]。

二 从一个例子理解线段树

下面我们从一个经典的例子来了解线段树,问题描述如下:从数组arr[0...n-1]中查找某个数组某个区间内的最小值,其中数组大小固定,但是数组中的元素的值可以随时更新。

对这个问题一个简单的解法是:遍历数组区间找到最小值,时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大,而查询操作很频繁的时候,耗时可能会不满足需求。

另一种解法:使用一个二维数组来保存提前计算好的区间[i,j]内的最小值,那么预处理时间为O(n^2),查询耗时O(1), 但是需要额外的O(n^2)空间,当数据量很大时,这个空间消耗是庞大的,而且当改变了数组中的某一个值时,更新二维数组中的最小值也很麻烦。

我们可以用线段树来解决这个问题:预处理耗时O(n),查询、更新操作O(logn),需要额外的空间O(n)。根据这个问题我们构造如下的二叉树

叶子节点是原始组数arr中的元素
非叶子节点代表它的所有子孙叶子节点所在区间的最小值
例如对于数组[2, 5, 1, 4, 9, 3]可以构造如下的二叉树(背景为白色表示叶子节点,非叶子节点的值是其对应数组区间内的最小值,例如根节点表示数组区间arr[0...5]内的最小值是1): 本文地址

由于线段树的父节点区间是平均分割到左右子树,因此线段树是完全二叉树,对于包含n个叶子节点的完全二叉树,它一定有n-1个非叶节点,总共2n-1个节点,因此存储线段是需要的空间复杂度是O(n)。那么线段树的操作:创建线段树、查询、节点更新 是如何运作的呢(以下所有代码都是针对求区间最小值问题)?

2.1 创建线段树

对于线段树我们可以选择和普通二叉树一样的链式结构。由于线段树是完全二叉树,我们也可以用数组来存储,下面的讨论及代码都是数组来存储线段树,节点结构如下(注意到用数组存储时,有效空间为2n-1,实际空间确不止这么多,比如上面的线段树中叶子节点1、3虽然没有左右子树,但是的确占用了数组空间,实际空间是满二叉树的节点数目: , 是树的高度,但是这个空间复杂度也是O(n)的 )。

struct SegTreeNode{int val;};

定义包含n个节点的线段树 SegTreeNode segTree[n],segTree[0]表示根节点。那么对于节点segTree[i],它的左孩子是segTree[2i+1],右孩子是segTree[2i+2]。

我们可以从根节点开始,平分区间,递归的创建线段树,线段树的创建函数如下:

const int MAXNUM = 1000;
struct SegTreeNode
{
    int val;
}segTree[MAXNUM];//定义线段树

/*
功能:构建线段树
root:当前线段树的根节点下标
arr: 用来构造线段树的数组
istart:数组的起始位置
iend:数组的结束位置
*/
void build(int root, int arr[], int istart, int iend)
{
    if(istart == iend)//叶子节点
        segTree[root].val = arr[istart];
    else
    {
        int mid = (istart + iend) / 2;
        build(root*2+1, arr, istart, mid);//递归构造左子树
        build(root*2+2, arr, mid+1, iend);//递归构造右子树
        //根据左右子树根节点的值,更新当前根节点的值
        segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
    }
}

2.2 查询线段树

已经构建好了线段树,那么怎样在它上面超找某个区间的最小值呢?查询的思想是选出一些区间,使他们相连后恰好涵盖整个查询区间,因此线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题。代码如下,具体见代码解释

/*
功能:线段树的区间查询
root:当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
    //查询区间和当前节点区间没有交集
    if(qstart > nend || qend < nstart)
        return INFINITE;
    //当前节点区间包含在查询区间内
    if(qstart <= nstart && qend >= nend)
        return segTree[root].val;
    //分别从左右子树查询,返回两者查询结果的较小值
    int mid = (nstart + nend) / 2;
    return min(query(root*2+1, nstart, mid, qstart, qend),
               query(root*2+2, mid + 1, nend, qstart, qend));

}

举例说明(对照上面的二叉树):

1、当我们要查询区间[0,2]的最小值时,从根节点开始,要分别查询左右子树,查询左子树时节点区间[0,2]包含在查询区间[0,2]内,返回当前节点的值1,查询右子树时,节点区间[3,5]和查询区间[0,2]没有交集,返回正无穷INFINITE,查询结果取两子树查询结果的较小值1,因此结果是1.

2、查询区间[0,3]时,从根节点开始,查询左子树的节点区间[0,2]包含在区间[0,3]内,返回当前节点的值1;查询右子树时,继续递归查询右子树的左右子树,查询到非叶节点4时,又要继续递归查询:叶子节点4的节点区间[3,3]包含在查询区间[0,3]内,返回4,叶子节点9的节点区间[4,4]和[0,3]没有交集,返回INFINITE,因此非叶节点4返回的是min(4, INFINITE) = 4,叶子节点3的节点区间[5,5]和[0,3]没有交集,返回INFINITE,因此非叶节点3返回min(4, INFINITE) = 4, 因此根节点返回 min(1,4) = 1。

2.3单节点更新

单节点更新是指只更新线段树的某个叶子节点的值,但是更新叶子节点会对其父节点的值产生影响,因此更新子节点后,要回溯更新其父节点的值。

/*
功能:更新线段树中某个叶子节点的值
root:当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
index: 待更新节点在原始数组arr中的下标
addVal: 更新的值(原来的值加上addVal)
*/
void updateOne(int root, int nstart, int nend, int index, int addVal)
{
    if(nstart == nend)
    {
        if(index == nstart)//找到了相应的节点,更新之
            segTree[root].val += addVal;
        return;
    }
    int mid = (nstart + nend) / 2;
    if(index <= mid)//在左子树中更新
        updateOne(root*2+1, nstart, mid, index, addVal);
    else updateOne(root*2+2, mid+1, nend, index, addVal);//在右子树中更新
    //根据左右子树的值回溯更新当前节点的值
    segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}

比如我们要更新叶子节点4(addVal = 6),更新后值变为10,那么其父节点的值从4变为9,非叶结点3的值更新后不变,根节点更新后也不变。

2.4 区间更新

区间更新是指更新某个区间内的叶子节点的值,因为涉及到的叶子节点不止一个,而叶子节点会影响其相应的非叶父节点,那么回溯需要更新的非叶子节点也会有很多,如果一次性更新完,操作的时间复杂度肯定不是O(lgn),例如当我们要更新区间[0,3]内的叶子节点时,需要更新出了叶子节点3,9外的所有其他节点。为此引入了线段树中的延迟标记概念,这也是线段树的精华所在。

延迟标记:每个节点新增加一个标记,记录这个节点是否进行了某种修改(这种修改操作会影响其子节点),对于任意区间的修改,我们先按照区间查询的方式将其划分成线段树中的节点,然后修改这些节点的信息,并给这些节点标记上代表这种修改操作的标记。在修改和查询的时候,如果我们到了一个节点p,并且决定考虑其子节点,那么我们就要看节点p是否被标记,如果有,就要按照标记修改其子节点的信息,并且给子节点都标上相同的标记,同时消掉节点p的标记。

因此需要在线段树结构中加入延迟标记域,本文例子中我们加入标记与addMark,表示节点的子孙节点在原来的值的基础上加上addMark的值,同时还需要修改创建函数build 和 查询函数 query,修改的代码用红色字体表示,其中区间更新的函数为update,代码如下:

const int INFINITE = INT_MAX;
const int MAXNUM = 1000;
struct SegTreeNode
{
    int val;
    int addMark;//延迟标记
}segTree[MAXNUM];//定义线段树

/*
功能:构建线段树
root:当前线段树的根节点下标
arr: 用来构造线段树的数组
istart:数组的起始位置
iend:数组的结束位置
*/
void build(int root, int arr[], int istart, int iend)
{
    segTree[root].addMark = 0;//----设置标延迟记域
    if(istart == iend)//叶子节点
        segTree[root].val = arr[istart];
    else
    {
        int mid = (istart + iend) / 2;
        build(root*2+1, arr, istart, mid);//递归构造左子树
        build(root*2+2, arr, mid+1, iend);//递归构造右子树
        //根据左右子树根节点的值,更新当前根节点的值
        segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
    }
}

/*
功能:当前节点的标志域向孩子节点传递
root: 当前线段树的根节点下标
*/
void pushDown(int root)
{
    if(segTree[root].addMark != 0)
    {
        //设置左右孩子节点的标志域,因为孩子节点可能被多次延迟标记又没有向下传递
        //所以是 “+=”
        segTree[root*2+1].addMark += segTree[root].addMark;
        segTree[root*2+2].addMark += segTree[root].addMark;
        //根据标志域设置孩子节点的值。因为我们是求区间最小值,因此当区间内每个元
        //素加上一个值时,区间的最小值也加上这个值
        segTree[root*2+1].val += segTree[root].addMark;
        segTree[root*2+2].val += segTree[root].addMark;
        //传递后,当前节点标记域清空
        segTree[root].addMark = 0;
    }
}

/*
功能:线段树的区间查询
root:当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
    //查询区间和当前节点区间没有交集
    if(qstart > nend || qend < nstart)
        return INFINITE;
    //当前节点区间包含在查询区间内
    if(qstart <= nstart && qend >= nend)
        return segTree[root].val;
    //分别从左右子树查询,返回两者查询结果的较小值
    pushDown(root); //----延迟标志域向下传递
    int mid = (nstart + nend) / 2;
    return min(query(root*2+1, nstart, mid, qstart, qend),
               query(root*2+2, mid + 1, nend, qstart, qend));

}

/*
功能:更新线段树中某个区间内叶子节点的值
root:当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[ustart, uend]: 待更新的区间
addVal: 更新的值(原来的值加上addVal)
*/
void update(int root, int nstart, int nend, int ustart, int uend, int addVal)
{
    //更新区间和当前节点区间没有交集
    if(ustart > nend || uend < nstart)
        return ;
    //当前节点区间包含在更新区间内
    if(ustart <= nstart && uend >= nend)
    {
        segTree[root].addMark += addVal;
        segTree[root].val += addVal;
        return ;
    }
    pushDown(root); //延迟标记向下传递
    //更新左右孩子节点
    int mid = (nstart + nend) / 2;
    update(root*2+1, nstart, mid, ustart, uend, addVal);
    update(root*2+2, mid+1, nend, ustart, uend, addVal);
    //根据左右子树的值回溯更新当前节点的值
    segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}

区间更新举例说明:当我们要对区间[0,2]的叶子节点增加2,利用区间查询的方法从根节点开始找到了非叶子节点[0-2],把它的值设置为1+2 = 3,并且把它的延迟标记设置为2,更新完毕;当我们要查询区间[0,1]内的最小值时,查找到区间[0,2]时,发现它的标记不为0,并且还要向下搜索,因此要把标记向下传递,把节点[0-1]的值设置为2+2 = 4,标记设置为2,节点[2-2]的值设置为1+2 = 3,标记设置为2(其实叶子节点的标志是不起作用的,这里是为了操作的一致性),然后返回查询结果:[0-1]节点的值4;当我们再次更新区间[0,1](增加3)时,查询到节点[0-1],发现它的标记值为2,因此把它的标记值设置为2+3 = 5,节点的值设置为4+3 = 7;

其实当区间更新的区间左右值相等时([i,i]),就相当于单节点更新,单节点更新只是区间更新的特例。

三 线段树实战

求区间的最大值、区间求和等问题都是采用类似上面的延迟标记域。下面会通过acm的一些题目来运用一下线段树。

等待更新......

参考资料

GeeksforGeeks: http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

GeeksforGeeks: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

懂得博客[数据结构之线段树]:http://dongxicheng.org/structure/segment-tree/

MetaSeed[数据结构专题—线段树]: http://blog.csdn.net/metalseed/article/details/8039326

NotOnlySuccess[完全版 线段树]: http://www.notonlysuccess.com/index.php/segment-tree-complete/