081017模拟 杂题

081017模拟

T1 Blue 这道题结论性非常强,考试的时候想到一种可行的贪心策略是每次选择最远的石头跳,但是没去仔细想就去搞后面了,结果最后打了个暴力查找,50分。正解可以使用多种数据结构来找下一个位置,将O(n)变成O(logn),比如用set然后每次删除,或者是二分右端点+线段树(单点修改+区间最小值查询)···
051017模拟 string&&big 杂题

051017模拟 string&&big

这套题又是画风不太正常的那种= =,到现在还差第二道没改过去,还没想明白。   string(T1) 这道题和HEOI2016那道排序有点相似,都是在字符集较小的情况下,通过线段树统计区间内各个字符出现次数,然后直接区间修改做到排序,思路非常简单,代码实现也不难。但是,分析一下复杂度,应该···
BZOJ3064 Tyvj 1518 CPU监控 线段树 数据结构

BZOJ3064 Tyvj 1518 CPU监控 线段树

前天考试被线段树虐了之后,为了加深对线段树打标记的理解,又来入了这个坑,结果到最后看了题解,和zyf商量了半天才算是理解了。   首先,确定题意就是要支持区间set、add,查询区间当前的最大值和历史最大值。考虑如何维护这个信息。对于既有set又有add的线段树,在任何时刻,同一个节点上必···
BZOJ2752 [HAOI2012]高速公路(road) 线段树 数据结构

BZOJ2752 [HAOI2012]高速公路(road) 线段树

问题可以简化成[l,r-1]的问题,期望是骗人的,实际上就是算一个比较复杂的区间和然后再除C(len,2)。 我们来观察这个区间和,发现直接做貌似不太好搞,于是想到了考虑每个数对区间答案的贡献,之后可以写出O(n)修改、查询的暴力的式子: $$\sum_{i=l}^{r} s[i]*(i-l+1)*···
BZOJ2090 [Poi2010]Monotonicity2 线段树+DP 动态规划 数据结构

BZOJ2090 [Poi2010]Monotonicity2 线段树+DP

线段树优化DP,这题可以类比最长上升子序列的做法。设f[i]为前i位选上第i位后的最优解,则f[i]=max{f[j]}+1。j是满足要求的转移点。因为计算出f值后,序列中最后一个关系符号已经确定,所以可以分情况搞。开两颗权值线段树,每颗树上的元素表示序列中权值为a[i]的数对应的最大f值,对大于号···
BZOJ4552 [Tjoi2016&Heoi2016]排序 二分答案+线段树 数据结构

BZOJ4552 [Tjoi2016&Heoi2016]排序 二分答案+线段树

因为只有最后的一次查询,所以可以二分答案。 二分最终答案M,将序列中大于等于M的数用1替代,其余为0,构建线段树,这样,对一段区间排序时,可以直接统计区间内有多少个1,然后将区间修改为0、1两部分,即可完成排序工作。最后,如果q位置为1,说明答案大于等于q,移动左区间即可。
TYVJ1730 二逼平衡树 线段树+Treap 数据结构

TYVJ1730 二逼平衡树 线段树+Treap

树套树第一题!一共搞了仨小时= = 先调好一个正常的Treap,可以封装一下,再去搞嵌套,这样会很好调试。 对[1,n]建立线段树,每个节点对应一颗Treap,初始时,在线段树中,将区间中的每个点都插入对应的Treap 查询区间排名:线段树分解,查询区间中比该数小的有多少。 查询区间K小:二分答案,···
线段树:旅馆安排 未分类

线段树:旅馆安排

实质上就是最大动态连续和。 嗯,这个代码比较渣,线段树打的很垃圾,所以常数很大,但是勉强没有超时。 大致思路就是维护三个信息:ml[o]:o节点对应区间内最长前缀所对应下标,mr[o]:o节点对应区间内最长后缀对应下标,mp[o]:o节点对应区间内最长连续区间的长度。 维护前后缀只需判断是否能跨越区···