Chro's Blog

だから 迷わない 頑張ろう

Those things that hurt, instruct.


  1. 「BZOJ 4012」「HNOI2015」开店

    Description风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 n 个地方,编号为 1 到 n,被 n-1 条带权的边连接起来。每个地方都住着一个妖怪,其中第 …

    BZOJ, 主席树, 树链剖分 继续阅读

  2. 「BZOJ 3545/3551」[ONTAK2010]Peaks & 加强版

    Description在Bytemountains有N座山峰,每座山峰有他的高度h_i。有些山峰之间有双向道路相连,共M条路径,每条路径有一个困难值,这个值越大表示越难走,现在有Q组询问,每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰,如果无解输出-1。 Input第一行三个数N,M,Q。 第二行N个数,第i个数为h_i 接下来M行,每行3个数a b c,表示从a到…

    BZOJ, DFS 序, 主席树, 平衡树, 并查集, 最小生成树 继续阅读

  3. 「BZOJ 3673/3674」可持久化并查集 by zky & 加强版

    Descriptionn个集合 m个操作 操作: 1 a b 合并a,b所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问a,b是否属于同一集合,是则输出1否则输出0 0 < n, m <= 2*10^4 Sample Input12345675 61 1 23 1 22 03 1 22 13 1 2 Sample Output123101 Solution貌…

    BZOJ, 主席树, 可持久化平衡树 继续阅读

  4. 「BZOJ 4826」「HNOI2017」影魔

    题解首先求出以每个位置向左、向右首个碰到的比自己大的数,记为区间 [L[i], R[i]]。用单调栈以便达到均摊 O(1) 的效率。 根据题目所述规则,不难得出: 区间 [L[i], R[i]] 的贡献是 p1 对于每个 [i+1, R[i]-1] 内的数 j,区间 [L[i], j] 的贡献是 p2 对于每个 [L[i]+1, i-1] 内的数 j,区间 [j, R[i]] 的贡献是 p2…

    BZOJ, 主席树 继续阅读

  5. 「Codeforces 323C」Two permutations

    You are given two permutations p and q, consisting of n elements, and m queries of the form: l1, r1, l2, r2 (l1 ≤ r1; l2 ≤ r2). The response for the query is the number of such integers from 1 to n, t…

    Codeforces, 主席树 继续阅读

  6. 「CodeChef BTREE」Union on Tree

    There is a country whose road system is a tree, the nodes in the tree represent cities and the edge is the road between them, and each edge is of unit length. For safety, the government should put gua…

    CodeChef, 主席树, 点分治, 虚树 继续阅读

  7. 「BZOJ 2653」middle

    Description一个长度为 n 的序列 a,设其排过序之后为 b,其中位数定义为$b_{\frac{n}{2}}$,其中 a, b从 0 开始标号,除法取下整。 给你一个长度为 n 的序列 s。 回答 Q 个这样的询问:s 左端点在$\left[ a,b \right]$之间,右端点在$\left[ c,d \right]$之间的子序列中,最大的中位数。 其中 a<b<c<…

    BZOJ, 主席树 继续阅读

  8. 「BZOJ 3524」「POI2014」Couriers

    Description给一个长度为 n 的序列 a。$1 \leq a_i \leq n$。 $$m$$组询问,每次询问一个区间$\left[ l,r \right]$,是否存在一个数在$\left[ l,r \right]$中出现的次数大于$\frac{r-l+1}{2}$。如果存在,输出这个数,否则输出 0。 Input第一行两个数 n,m。 第二行 n 个数,$a_i$。 接下来 m 行,每…

    BZOJ, 主席树 继续阅读

  9. 「SPOJ COT」Count on a tree

    You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight. We will ask you to perform the following operation: u v k: ask for the k-th minimum weight …

    SPOJ, 主席树 继续阅读

  10. 「BZOJ 2809」「APIO2012」dispatching

    Description在一个忍者的帮派里,一些忍者们被选中派遣给顾客,然后依据自己的工作获取报偿。在这个帮派里,有一名忍者被称之为 Master。除了 Master以外,每名忍者都有且仅有一个上级。为保密,同时增强忍者们的领导力,所有与他们工作相关的指令总是由上级发送给他的直接下属,而不允许通过其他的方式发送。现在你要招募一批忍者,并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水,同时…

    BZOJ, 主席树 继续阅读

  11. 「BZOJ 3932」「CQOI2015」任务查询系统

    Description最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和Ei秒任务也在运行),其优先级为Pi。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第Xi秒正在运行的任务中,优先级最…

    BZOJ, 主席树 继续阅读

  12. 「BZOJ 1901」「ZOJ 2112」Dynamic Rankings

    The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a …

    BZOJ, ZOJ, 主席树, 树状数组 继续阅读

  13. 「POJ 2104」K-th Number

    DescriptionYou are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to …

    POJ, 主席树 继续阅读