虽然这一题被划在主席树下面,但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。 树链剖分后我们考虑对每一 …
lp3168 CQOI2015 任务查询系统
观察题面,我们发现这是一道变态题:区间加点,单点查询第k大,强制在线——这tm不是变态题么!别的不说,权值怎么 …
lp3302 SDOI2013 森林
我们发现,树上的链上第k大是可以使用主席树来维护的。对于每一个节点,我们从它的父亲复制一个版本,然后每一次求出 …
lp2146 NOI2015 软件包管理器
简化题意: 存在一棵树,其上所有点的初始值为0。 存在两种操作,分别是,将一个点的所有父亲节点改为1,或者将一 …
lp2486 SDOI2011 染色
考虑这一题在链上的情况。 显然,可以建一棵线段树,修改是打标记下传,查询是左右相加特判左右相邻处颜色是否相同。 …
lp2590 ZJOI2008 树的统计
树剖套线段树裸题。
lp3676 小清新数据结构题
仔细考虑这道题,我们可以将问题转化为「修改」和「换根」两个操作。 对于修改操作,我们知道,每个点的权值对且仅对 …
CF487E Tourists
众所周知,圆方树是用来处理图上点双相关问题的。 同时,点双又是一个和简单路径密切相关的东西。故而这一题我们可以 …
lp2468 SDOI2010 粟粟的书架
简化题意。 有一个n*m的矩阵,q个询问,求问,在每个矩阵中最少取多少个数,使得和至少为h。 观察数据范围,我 …
lp1110 ZJOI2007 报表统计
事实上对于第一类询问和第二类询问我们可以分别处理。 第二类询问的处理方法是非常显然的。由于只有插入而没有删除操 …
lp1486 NOI2004 郁闷的出纳员
(似乎很少看见权值线段树的做法的样子。但是权值线段树如果动态开点、大胆卡常的话,是可以跑得飞快的。) 首先看一 …
lp2572 SCOI2010 序列操作
操作要求: 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 …
lp1471 方差
大力上一个线段树。 将方差展开为由区间平方的和与区间和两项构成的多项式,然后维护区间平方的和与区间和。 具体来 …