Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom12月前

07/14
09:08
线段树

[bzoj 4636] 蒟蒻的数列

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

蒟蒻DCrusher不仅喜欢玩扑克,还喜欢研究数列
DCrusher有一个数列,初始值均为0,他进行N次操作,每次将数列[a,b)这个区间中所有比k小的数改为k,他想知道N次操作后数列中所有元素的和。他还要玩其他游戏,所以这个问题留给你解决。

Read More →

[bzoj 4636] 蒟蒻的数列

@krydom12月前

07/1
16:38
线段树

[bzoj 4631] 踩气球

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

六一儿童节到了, SHUXK 被迫陪着M个熊孩子玩一个无聊的游戏:有N个盒子从左到右排成一排,第i个盒子里装着Ai个气球。
SHUXK 要进行Q次操作,每次从某一个盒子里拿出一个没被踩爆的气球,然后熊孩子们就会立刻把它踩爆。
这M个熊孩子每个人都指定了一个盒子区间[Li, Ri]。 如果某一个时刻,一个熊孩子发现自己选定的盒子区间[Li, Ri]中的所
有气球都已经被踩爆了,他就会非常高兴(显然之后他一直会很高兴)。
为了不辜负将自己的任务强行塞给 SHUXK 的那个人的期望, SHUXK 想向你询问:
他每次操作过后会有多少个熊孩子很高兴。

Read More →

[bzoj 4631] 踩气球

@krydom1年前

06/15
15:51
线段树

[bzoj 1230] [Usaco2008 Nov]lites 开关灯

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Farmer 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_i <= E_i <= N), 它们表示起始开关和终止开关. 奶牛们只需要把从S_i到E_i之间的按钮都按一次, 就可以完成这个指令. 第2种指令(用1表示)同样包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 不过这种指令是询问从S_i到E_i之间的灯有多少是亮着的. 帮助FJ确保他的奶牛们可以得到正确的答案.

Read More →

[bzoj 1230] [Usaco2008 Nov]lites 开关灯

@krydom1年前

06/13
14:14
并查集 线段树

[bzoj 2733] HNOI2012 永无乡

 ♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 永无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b,则称岛 a 和岛 b 是连 通的。现在有两种操作:B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛,即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座,请你输出那个岛的编号。

Read More →

[bzoj 2733] HNOI2012 永无乡

@krydom1年前

06/13
13:07
树链剖分 线段树

[bzoj 3626] [LNOI2014]LCA

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

给出一个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的最近公共祖先的深度之和)

Read More →

[bzoj 3626] [LNOI2014]LCA

@krydom1年前

06/12
22:07
左偏树 并查集 线段树

[bzoj 2333] [SCOI2011]棘手的操作

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:

U x y: 加一条边,连接第x个节点和第y个节点

A1 x v: 将第x个节点的权值增加v

A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v

A3 v: 将所有节点的权值都增加v

F1 x: 输出第x个节点当前的权值

F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值

F3: 输出所有节点中,权值最大的节点的权值

Read More →

[bzoj 2333] [SCOI2011]棘手的操作

@krydom1年前

06/3
15:46
线段树

[bzoj 4392] [Usaco2015 dec]Counting Haybales

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Farmer John is trying to hire contractors to help rearrange his farm, but so far all of them have quit when they saw the complicated sequence of instructions FJ wanted them to follow. Left to complete the project by himself, he realizes that indeed, he has made the project perhaps more complicated than necessary. Please help him follow his instructions to complete the farm upgrade.
FJ's farm consists of NN fields in a row, conveniently numbered 1…N1…N. In each field there can be any number of haybales. Farmer John's instructions contain three types of entries:
1) Given a contiguous interval of fields, add a new haybale to each field.
2) Given a contiguous interval of fields, determine the minimum number of haybales in a field within that interval.
3) Given a contiguous interval of fields, count the total number of haybales inside that interval.

农夫约翰打算重修他的农场。他有 N 块土地,连续排列成一行,标号为 1…N。在每块土地上有任意数量的草堆。他可以发出三种指令:
1) 对一个连续区间的土地,每块土地增加相同数量的草堆。
2) 对一个连续区间的土地,输出其中最少的草堆数量。
3) 对一个连续区间的土地,输出草堆数量总数。

Read More →

[bzoj 4392] [Usaco2015 dec]Counting Haybales

@krydom1年前

05/31
20:52
线段树

[bzoj 4399] 魔法少女LJJ

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 在森林中见过会动的树,在沙漠中见过会动的仙人掌过后,魔法少女LJJ已经觉得自己见过世界上的所有稀奇古怪的事情了
LJJ感叹道“这里真是个迷人的绿色世界,空气清新、淡雅,到处散发着醉人的奶浆味;小猴在枝头悠来荡去,好不自在;各式各样的鲜花争相开放,各种树枝的枝头挂满沉甸甸的野果;鸟儿的歌声婉转动听,小河里飘着落下的花瓣真是人间仙境”
SHY觉得LJJ还是太naive,一天,SHY带着自己心爱的图找到LJJ,对LJJ说:“既然你已经见识过动态树,动态仙人掌了,那么今天就来见识一下动态图吧”
LJJ:“要支持什么操作?”
SHY:“
1.新建一个节点,权值为x。
2.连接两个节点。
3.将一个节点a所属于的联通快内权值小于x的所有节点权值变成x。
4.将一个节点a所属于的联通快内权值大于x的所有节点权值变成x。
5.询问一个节点a所属于的联通块内的第k小的权值是多少。
6.询问一个节点a所属联通快内所有节点权值之积与另一个节点b所属联通快内所有节点权值之积的大小。
7.询问a所在联通快内节点的数量
8.若两个节点a,b直接相连,将这条边断开。
9.若节点a存在,将这个点删去。

LJJ:“我可以离线吗?”
SHY:“可以,每次操作是不加密的,”
LJJ:“我可以暴力吗?”
SHY:“自重”
LJJ很郁闷,你能帮帮他吗

Read More →

[bzoj 4399] 魔法少女LJJ

@krydom1年前

05/28
10:22
zkw线段树 线段树

[bzoj 3685] 普通van Emde Boas树

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 设计数据结构支持:
1 x  若x不存在,插入x
2 x  若x存在,删除x
3    输出当前最小值,若不存在输出-1
4    输出当前最大值,若不存在输出-1
5 x  输出x的前驱,若不存在输出-1
6 x  输出x的后继,若不存在输出-1
7 x  若x存在,输出1,否则输出-1

Read More →

[bzoj 3685] 普通van Emde Boas树

@krydom1年前

05/12
09:56
线段树

[bzoj 4551] Tjoi2016&Heoi2016 树

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

在2016年,佳媛姐姐刚刚学习了树,非常开心。现在他想解决这样一个问题:给定一颗有根树(根为1),有以下两种操作:1. 标记操作:对某个结点打上标记(在最开始,只有结点1有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)2. 询问操作:询问某个结点最近的一个打了标记的祖先(这个结点本身也算自己的祖先)你能帮帮他吗?

Read More →

[bzoj 4551] Tjoi2016&Heoi2016 树