51nod1766 树上的最远点对
51nod分析考虑建立一棵线段树，每个节点维护编号在 $[l,r]$ 内的节点中选两点距离的最大值。考虑合并，容易发现只会有六种可能的情况即四个端点两两组合。查询时求出每个区间对应的两个端点，四种情况取 $\max$ 即可。如果常数大的话写树剖容易被卡。代码// =================================== // author: M_sea // websi...
标签 线段树 下的文章
- 首页
- 线段树
CF115E Linear Kingdom Races
CodeforcesLuogu分析考虑 DP。设 $dp_i$ 表示前 $i$ 条道路的最大收益，不难得到转移这里的 $c(i,j)$ 表示修建 $i$ 到 $j$ 的道路的花费，$w(i,j)$ 表示修建 $i$ 到 $j$ 的道路获得的收益。考虑用线段树优化，即要求扫到 $i$ 时每个叶结点的值 $j$ 为 $dp_j-c(j+1,i)+w(j+1,i)$。对于一个新的 $i$，将 $[...
洛谷4041 [AHOI2014/JSOI2014]奇怪的计算器
Luogu分析我们把输入的值从小到大排序，构成序列 $a$。那么可以发现在操作后 $a$ 序列仍为不降序列。也就是说，每做完一个操作后，$<L$ 的数一定是一个前缀，$>R$ 的数一定是一个后缀，而这个前后缀可以直接在线段树上二分得到。那么我们只需要写一棵支持区间加、区间减、区间乘、区间加上 $k\times c_i$，区间赋值的线段树就好了。关于线段树有一个奇妙的写法：令一次修...
CF903G Yet Another Maxflow Problem
CodeforcesLuogu分析容易发现，至多只会割掉一条 A 边和一条 B 边。我们加边 $(A_0,A_1,0)$ 和 $(B_n,B_{n+1},0)$，然后求 $A_0$ 到 $B_{n+1}$ 的最大流，就可以转化成恰好割掉一条 A 边和一条 B 边的情况了。设割掉了 $A_i\to A_{i+1}$ 和 $B_j\to B_{j+1}$，则此时的最大流为显然对于每个 $i$，后...
AtCoder Grand Contest 001 简要题解
比赛地址BBQ Easy排序后相邻的两个放一组即可。正确性显然。Mysterious Light可以发现每次反射之后问题都变为一个子问题，于是直接递归做下去即可。可以发现边界为 $n\bmod x=0$。Shorten Diameter当 $k$ 为偶数时，枚举一个根，然后删掉所有到根距离 $>\frac{k}{2}$ 的点。在所有这样算出来的答案中取 $\min$ 即可。当 $k$ ...
洛谷4062 [Code+#1]Yazid 的新生舞会
LuoguLOJ分析显然每个数作为众数的情况是相互独立的，因此我们考虑枚举众数 $k$，然后计算有多少个区间中 $k$ 的出现次数超过一半。不妨把等于 $k$ 的数看做 $1$，不等于 $k$ 的数看做 $-1$，那么我们相当于要求有多少个区间的和大于 $0$。这个东西等价于前缀和的逆序对数。但是直接做的话当 $A_i$ 的数量比较多时显然会 TLE，所以我们需要一些优化。考虑到 $A_i$...
洛谷1505 [国家集训队]旅游
Luogu分析把边权放到点上，树剖之后就只需要写一个支持单点赋值、区间取相反数、区间求和、区间求最小值、区间求最大值的线段树了。这个东西还比较好维护。一个技巧是将三个要维护的东西封装到一个 struct 里然后重载 +，可以有效减少代码量。关键代码大概是这样子：int invv[N<<2]; // 取相反数的标记 struct node { int sumv,minv,maxv;...
洛谷1600 天天爱跑步
LuoguLOJ分析脑子不够，数据结构来凑我们把每个人的路径拆成上行（$s\to lca$）和下行（$lca\to t$）两部分。先考虑上行部分，如果一个人能被 $i$ 点的观察员观察到则有 $dep_s-dep_i=w_i$，移项得到 $dep_s=w_i+dep_i$。再考虑下行部分，如果一个人能被 $i$ 点的观察员观察到则有 $dis(s,t)-dep_t+dep_i=w_i$，移项...
洛谷2680 运输计划
Luogu分析显然可以二分答案。那么我们只需要判断是否存在一条边，满足它被所有长度 $>mid$ 的运输计划覆盖，而且这些运输计划长度减掉它的长度后 $\leq mid$。显然我们会选所有满足「被所有长度 $>mid$ 的运输计划覆盖」的边中长度最大的那个，因此我们只需要想一想怎么求出一条边被覆盖的次数。这个直接树上差分即可，当然也可以像我一样写树剖+线段树（但是不吸氧可能会 T...