分类 线段树 下的文章

BZOJ 1818: [Cqoi2010]内部白点

Solution网上的做法大多是扫描线 + 树状数组,我的做法也差不多,只不过写的是线段树(没他们的短)。首先可以证明的是不存在永不终止的情况,所以输出 -1 是没分的(垃圾出题人),进一步考虑下可以发现最多变色一次就会把所有点染完色了,如果我们把两个同一行或同一列的两个点看成一个线段,那么染色的点一定就是行列两条线端的交点。我们只要求线段交点个数就可以了,我们可以用线段树来完成这个问题,遇到横向的边就区间更新 +1,遇到纵向的边就单点查询。看起来有点问题是吧?由于纵向的边是一个线段,我们只能要一定纵坐标范围内的横向边,线段树是无法直接维护这个东西的,所以我们离线所有纵向的- 阅读剩余部分 -

BZOJ 3038: 上帝造题的七分钟2

Solution由于区间开根号没有可以快速合并的性质,所以如果区间更新必须一直更新到线段树叶节点,显然这样做是每次 $O(n)$ ,肯定 T 了,但是我们可以发现一个数 1e12 只需要开几次根号就会变成 1 或 0,然后他们的根号就是自己本身了,所以在线段树记录一下区间是否都是 0 和 1,如果是就不更新。DescriptionXLk觉得《上帝造题的七分钟》不太过瘾,于是有了第二部。"第一分钟,X说,要有数列,于是便给定了一个正整数数列。第二分钟,L说,要能修改,于是便有了对一段数中每个数都开平方(下取整)的操作。第三分钟,k说,要能查询,于是便有了求一段数的和的操作。第- 阅读剩余部分 -

BZOJ 1901: Zju2112 Dynamic Rankings

Description给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。Input第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令每行的格式是下面两种格式中的一种。 Q i j k 或者 C- 阅读剩余部分 -

BZOJ 1828: [Usaco2010 Mar]balloc 农场分配

DescriptionInput第1行:两个用空格隔开的整数:N和M 第2行到N+1行:第i+1行表示一个整数C_i 第N+2到N+M+1行: 第i+N+1行表示2个整数 A_i和B_iOutput第一行: 一个整数表示最多能够被满足的要求数Sample Input5 4 1 3 2 1 3 1 3 2 5 2 3 4 5Sample Output3Solution按照右端点排序,然后以此能放则放,用线段树维护一下区间最小值。Code#include <queue> #include <cmath> #include <cstdio>- 阅读剩余部分 -

BZOJ 594: [Usaco2008 Jan]猜数游戏

Description为了提高自己低得可怜的智商,奶牛们设计了一个新的猜数游戏,来锻炼她们的逻辑推理能力。 游戏开始前,一头指定的奶牛会在牛棚后面摆N(1 <= N<= 1,000,000)堆干草,每堆有若干捆,并且没有哪两堆中的草一样多。所有草堆排成一条直线,从左到右依次按1..N编号,每堆中草的捆数在1..1,000,000,000之间。 然后,游戏开始。另一头参与游戏的奶牛会问那头摆干草的奶牛 Q(1 <= Q <= 25,000)个问题,问题的格式如下: 编号为Ql..Qh(1 <= Ql <= Qh <= N)的草堆中,最- 阅读剩余部分 -

BZOJ 1593: [Usaco2008 Feb]Hotel 旅馆

Description奶牛们最近的旅游计划,是到苏必利尔湖畔,享受那里的湖光山色,以及明媚的阳光。作为整个旅游的策划者和负责人,贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50,000)间客房,它们在同一层楼中顺次一字排开,在任何一个房间里,只需要拉开窗帘,就能见到波光粼粼的湖面。 贝茜一行,以及其他慕名而来的旅游者,都是一批批地来到旅馆的服务台,希望能订到D_i (1 <= D_i <= N)间连续的房间。服务台的接待工作也很简单:如果存在r满足编号为r..r+D_i-1的房间均空着,他就将这一批顾客安排到这些- 阅读剩余部分 -

BZOJ 1645: [Usaco2007 Open]City Horizon 城市地平线

DescriptionFarmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings. The entire horizon is represented by a number line with N (1 <= N <= 40,000) buildings. Build- 阅读剩余部分 -

BZOJ 1230: [Usaco2008 Nov]lites 开关灯

DescriptionFarmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 <= M <= 100,000)条指令, 每个指令都是两个整数中的一个(0 <= 指令号 <= 1). 第1种指令(用0表示)包含两个数字S_i和E_i (1 <= S- 阅读剩余部分 -

BZOJ 3083: 遥远的国度

题目描述zcwwzdjn在追杀十分sb的zhx,而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时,守护神RapiD阻拦了zcwwzdjn的去路,他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。问题是这样的:遥远的国度有n个城市,这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都,我们可以把这个首都看做整棵树的根,但遥远的国度比较奇怪,首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值,有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候,如果把首都看- 阅读剩余部分 -

BZOJ 3626: [LNOI2014]LCA

题目描述给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。有q次询问,每次询问给出l r z,求sigma_{l<=i<=r}dep[LCA(i,z)]。(即,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和)输入第一行2个整数n q。接下来n-1行,分别表示点1到点n-1的父节点编号。接下来q行,每行3个整数l r z。输出输出q行,每行表示一个询问的答案。每个答案对201314取模输出样例输入5 200111 4 31 4 2- 阅读剩余部分 -

BZOJ 4196: [Noi2015]软件包管理器

题目描述Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其它软件包),完成所有的配置。Debian/Ubuntu使用的apt-get,Fedora/CentOS使用的yum,以及OSX下可用的homebrew都是优秀的软件包管理器。你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依赖问题。如果软件包A依赖软件包B,那么安装软件包A以前,必须先安装软件包B。同时,如果想要卸载软件包B,则必须卸载软件包- 阅读剩余部分 -

BZOJ 1798: [Ahoi2009]Seq 维护序列seq

题目描述老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为N的数列,不妨设为a1,a2,…,aN 。有如下三种操作形式: (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模P的值。输入第一行两个整数N和P(1≤P≤1000000000)。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M,表示操作总数。从第四行开始每行描述一个操作,输入的操作有以下三种形式: 操作1:“1 t g c”(- 阅读剩余部分 -

BZOJ 4034: [HAOI2015]树上操作

题目描述有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:操作 1 :把某个节点 x 的点权增加 a 。操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 :询问某个节点 x 到根的路径中所有点的点权和。输入第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数,表示树中节点的初始权值。接下来 N-1 行每行三个正整数 fr, to , 表示该树中存在一条边 (fr, to) 。再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x- 阅读剩余部分 -