Tag-线段树

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-03-12 17:13:37 |  0 Comments  |  线段树 扫描线

hdu 1542 Atlantis 扫描线:矩形面积并


题目大意

给出矩形的左下端点和右上端点的坐标,求所有的矩形的面积的并。


题解

求矩形面积并是扫描线的基础经典问题。这篇blog是借助这个来介绍初步入门扫描线。

扫描线,顾名思义,就是一条上下扫描或者左右扫描的虚拟的自主创造的线。

在扫描线扫描到一条线段的时候,就进行操作。而这种操作常常是利用线段树这种数据结构来进行存储的。

在矩形面积的并这一个问题中,我们可以这样去把要计算的总的面积分为这样几个部分来看:

(图来自于别人的博客,实在是不想自己画图了QAQ)

我们可以看到,这个图就是按照扫描线来分区计算面积的。

我们每一次找到一条扫描线,就要维护当前在这条扫描线上(当然这里扫描线是向上扫的)所有的线段的覆盖总长(覆盖部分不再重复计算)。

然后我们用两条扫描线的高度差去乘前一条扫面先上的所有线段的覆盖总长,就是这两条扫描线与矩形围成的面积并。

对于扫描线的顺序,只需要把矩形的上下边去离散化排序以下就可以了。

于是我们剩下的任务就是维护当前扫描线上的线段覆盖总长。

由于x坐标可能会很大,我们一样要对x进行离散化,并且记录离散化后的元素对应的离散化前的元素。

然后我们可以类比前缀和的方式:

对于每一个矩形的下边,我们设这里的标记为+1,对于每一个矩形的上边,我们设这里的标记为-1

这里的标记就可以使用线段树来维护了(但是这里的标记并不需要下放,也不需要向上更新,这里的标记是用于记录这段区间线段是否被覆盖的)。

于是我们在线段树中维护两个变量,一个表示这段区间表示的线段是否被完全覆盖,另一个表示这段区间被覆盖的线段的总长。

在求被覆盖线段总长时,要分两种情况进行讨论:

1.当前区间表示的线段被完全覆盖:区间被覆盖的线段总长即为这段区间表示的线段总长。

2.当前区间表示的线段未被完全覆盖:当前区间被覆盖的线段的总长=其左区间被覆盖的线段的总长+其右区间被覆盖的线段的总长。

我们是一边更新一边统计答案,统计答案只需要每次答案加上总区间被覆盖的线段总长×两条扫描线之间的高度差。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct node
{
    double x1, x2, y1, y2; int id;
    node(double X1 = 0, double Y1 = 0, double X2 = 0, do
 2018-12-26 11:18:55 |  0 Comments  |  线段树

Codeforces Round#528 div2 F. Rock-Paper-Scissors Champion

Codeforces Round#528 div2

F. Rock-Paper-Scissors Champion

time limit:per test 2 seconds
memory limit:per test 256 megabytes
input:standard input
output:standard output

n players are going to play a rock-paper-scissors tournament. As you probably know, in a one-on-one match of rock-paper-scissors, two players choose their shapes independently. The outcome is then determined depending on the chosen shapes: "paper" beats "rock", "rock" beats "scissors", "scissors" beat "paper", and two equal shapes result in a draw.

At the start of the tournament all players will stand in a row, with their numbers increasing from 1 for the leftmost player, to n for the rightmost player. Each player has a pre-chosen shape that they will use in every game throughout the tournament. Here's how the tournament is conducted:

1.If there is only one player left, he is declared the champion.
2.Otherwise, two adjacent players in the row are chosen arbitrarily, and they play the next match. The losing player is eliminated fr

 2017-04-06 00:00:14 |  0 Comments  |  splay 线段树 树套树

BZOJ 3196 二逼平衡树

引言

好久没写题解了,正好不怎么想写代码,还是来发波题解吧。

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数,表示有序序列
下面有m行,opt表示操作标号
若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围:n,m<=50000
2.序列中每个数的数据范围:[0,1e8]
3.虽然原题没有,但事实上5操作的k可能为负数

题解

这是一道线段树套平衡树(就是每个线段树节点里面都存着一颗平衡树)的裸题。。。
用线段树维护下标区间,然后把平衡树节点套到线段树节点里面,注意此处的平衡树节点维护的是权值的大小。 修改操作可以转化成为找到当前这个数对应的区间,在splay里面删掉这个数,然后插入修改成的那个数就OK。
然后就是注意排名的话是比当前小的数的个数+1。
要求区间内排名为k的数的时候,我们就得注意了。因为我们是线段树套平衡树,所以说查询区间的时候,查询区间会分布在很多个线段树节点上。所以这样的话,这个操作就只能是二分答案,然后去看答案的排名是不是在这个查询区间中排k。(注意因为有重复的数,所以要求最大排名和最小排名,看k是不是在这个范围内)。
最后要注意的就是……为了保证空间,一律用内存池写。(可能我的代码里面的指针对某些读者不太友善。。。)

代码

#includ
 2017-01-15 14:31:30 |  0 Comments  |  整体二分 线段树

[Zjoi2013]K大数查询

Description

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

Input

第一行N,M 接下来M行,每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3

Sample Output

1 2 1

HINT

【样例说明】第一个操作 后位置 1 的数只有 1 , 位置 2 的数也只有 1 。 第二个操作 后位置 1的数有 1 、 2 ,位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3大的数是 1 。
N,M<=50000,N,M<=50000a<=b<=N1 操作中abs(c)<=N2操作中c<=Maxlongint

题解

二分:当遇到的操作是询问操作时,查询线段树里的当前区间,并将当前区间所包含的数的个数as与查询的第k大相比较,如果小于k,那么把当前询问分到左边去,并统计影响k-=as,反之,将它分到右边;当遇到的操作是加入操作时,把要加入的数和mid比较,如果大于mid,那么就把当前操作统计进去,而且当前操作会对右边产生影响,所以要分到右边去,虽然对左边也有影响,但在处理询问时已经处理,就不用考虑了。
数的统计:线段树维护,记录每个区间当前有多少个大于mid的数,“加入”操作里的“统计进去”即是更新当前区间的数的个数(注:不要把线段树的区间和上面把操作分到左右区间混淆,这是不相干的概念,上面分到左右只是为了维护整体二分的序列的有序性)
每次操作完,都要以区间序号为关键字重新排序。
细节:线段树维护时,要考虑线段树每一次二分时,之前的标记等都是不能再使用的,所以要重置,但因为数组过大,如果每一次memset,必然TLE。所以设一个标记数组,每次pushdown前,都要判断当前点的标记是否是1,若是1,把当前点置0,并把当前点的左右儿子重置。这样,每次二分重置时,只用重置根节点即可。
数据范围过大,可能超int。

代码

#include <iostream>
#includ
 2017-01-08 09:23:48 |  0 Comments  |  splay 线段树

【ZJOI2007】【BZOJ1058】报表统计splay+线段树

题目描述

小Q的妈妈是一个出纳,经常需要做一些统计报表的工作。今天是妈妈的生日,小Q希望可以帮妈妈分担一些工作,作为她的生日礼物之一。经过仔细观察,小Q发现统计一张报表实际上是维护一个可能为负数的整数数列,并且进行一些查询操作。在最开始的时候,有一个长度为N的整数序列,并且有以下三种操作: INSERT i k 在原数列的第i个元素后面添加一个新元素k; 如果原数列的第i个元素已经添加了若干元素,则添加在这些元素的最后(见下面的例子) MIN_GAP 查询相邻两个元素的之间差值(绝对值)的最小值 MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值(绝对值) 例如一开始的序列为 5 3 1 执行操作INSERT 2 9将得到: 5 3 9 1 此时MIN_GAP为2,MIN_SORT_GAP为2。 再执行操作INSERT 2 6将得到: 5 3 9 6 1 注意这个时候原序列的第2个元素后面已经添加了一个9,此时添加的6应加在9的后面。这个时候MIN_GAP为2,MIN_SORT_GAP为1。于是小Q写了一个程序,使得程序可以自动完成这些操作,但是他发现对于一些大的报表他的程序运行得很慢,你能帮助他改进程序么?

输入格式

第一行包含两个整数N,M,分别表示原数列的长度以及操作的次数。第二行为N个整数,为初始序列。接下来的M行每行一个操作,即“INSERT i k”,“MIN_GAP”,“MIN_SORT_GAP”中的一种(无多余空格或者空行)。

输出格式

对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令,输出一行答案即可。

样例输入

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

样例输出

2
2
1

数据范围及提示

N , M ≤500000 对于所有的数据,序列内的整数不超过5*108


题解

于是这道题有点坑啊。
初学splay,拿几道题目练练手,结果没想到刚开始推荐的这个就这么坑。
观察题目中的信息,我们发现,其实是可以用2个splay做的,一个splay维护MIN_GAP,另一个维护MIN_SORT_GAP,每次添加的时候只要注意:
1.由于满足单调性MIN_SORT_GAP只需要先求出排在当前要添加的数的前面和后面的两个数,用这两个数和当前要添加的数的差值的绝对值更新MIN_SORT_GAP,然后

Title - Artist
0:00