标签:线段树

【题解】 Stars 树状数组/线段树/treap POJ – 2352

原题戳我

坡机裸提

题目描述:
Description

Astronomers often examine star maps where stars are represented by po[......]

[继续阅读= ̄ω ̄=]

Read MoreView 6 Comments

【题解】 [Zjoi2013]K大数查询 整体二分+线段树 BZOJ – 3110

1. 题目

BZOJ - 3110:传送门= ̄ω ̄=

LUOGU - 3332:传送门= ̄ω ̄=

2. 题解

哈哈哈终于完美AC这题惹!

整体二分就是吼哇QvQ!

有先决科技点:整体二分解[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 二逼平衡树 树套树(线段树套splay) BZOJ – 3196

1. 题目

传送门= ̄ω ̄=

2. 题解

感觉就是Dynamic Rankings那题的加强版。

还是老样子搞个线段树套splay就行了,具体解法见我写的那个Dynamic Rankings的[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 [Zjoi2013]K大数查询 树套树(线段树套线段树) BZOJ – 3110

1. 题目

传送门= ̄ω ̄=

2. 题解

mmp好久没碰到这么恶心的题目惹!

因为不会整体二分&CDQ分治,所以就写惹树套树。

怎么说呢=。=

  • 此题树套树卡常
  • 还卡空间,线段树需[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 Dynamic Rankings 动态区间第k小问题 二分答案+树套树(线段树套splay) BZOJ – 1901

1. 题目

传送门= ̄ω ̄=

更新:突然发现LUOGU上有这题(LUOGU - 2617),可以木有权限号刷~传送门= ̄ω ̄=

题目大意:

给你一个序列,要求资磁两个操作:

  • 将某一个位置的[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 A Simple Task 线段树 CodeForces – 558E

1. 题目

传送门= ̄ω ̄=

大意:给你一个长度为N的字符串($N\leq 10^5$),给你M个操作($M\leq 50000$),每次操作给定l,r,要求将字符串的区间[l,r]按字典序升序或[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【考试总结】线段树使我爆炸 ——litble

考试策略

这个里面的花,我看了一下,啊,T2和T3是比较简单的原题啊,匆匆写完过了对拍,看了一下T4,T4有思路但是这个离散太恶心了有点思考不清楚,怕写错就打了暴力。T1完全没思路就打了暴力。

T[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】 扫描线求矩形面积并 —— by 蒟蒻XZY

1. 序言

求矩形面积并指的是给你n个矩形的顶点坐标(矩形的边必然平行于坐标轴),求它们所覆盖的总面积(重叠覆盖的面积只算一次覆盖)。
暴力枚举矩形的话如果n较大显然会超时。这时候我们就需要一种新算[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 Atlantis 扫描线 线段树 离散化 HDU – 1542

1. 题目

传送门= ̄ω ̄=
题目大意:给出n个矩形(矩形顶点左边可能为小数)1<=n<=100,求这些矩形覆盖的面积大小(多次覆盖同一个地方只算一次覆盖),即求这些矩形的面积并。含多组[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 LANE航线规划 (并查集+倍增LCA+时间倒流+线段树+DFS序) -boshi

收回我以前对某些题的评论--这一道tmd才是最恶心的。

苟活者在淡红的WA中会依稀看见微茫的希望,真正的傻B会更奋然而AC。--某树人

耗时4.5个小时,手写180行代码,套用5种模板,定义1[......]

[继续阅读= ̄ω ̄=]

Read MoreComment