标签:树套树

【题解】 动态kth – 树套树log^2 -boshi

动态区间第k大的一种$O(nlog^2n)$的树套树解法

题意:

​ 给定一个序列,有“将一个数修改为另一个”的操作,和询问“[l,r]区间内的第k小值是几”的询问。要求在1s内对一个[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment

【题解】 二逼平衡树 树套树(线段树套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