Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「NOI2008」糖果雨 - 坐标变换 + 二维树状数组

    在一个长度为 len \mathrm{len} 的区间上,有以下操作:

    1. t t 时刻,出现一条线段 [l,r] [l, r] ,这条线段将要向左或向右移动;
    2. t t 时刻查询与线段 [l,r] [l, r] 有公共点的线段有多少;
    3. t t 时刻某条线段消失。

    每一时刻,每条线段都会移动,线段的左端点最小为 0 0 ,当一条向左移动的线段左端点碰到 0 0 时,下一时刻它会改为向右移动;当一条向右移动的线段左端点碰到 len \mathrm{len} 时,下一时刻它会改为向左移动。

    于  BZOJ, NOI, 二维树状数组, 坐标变换, 树状数组 继续阅读

  2. 「NOIP2013」火柴排队 - 逆序对

    涵涵有两盒火柴,每盒装有 n n 根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为

    i=1n(aibi)2 \sum\limits_{i = 1} ^ n (a_i - b_i) ^ 2

    其中 ai a_i 表示第一列火柴中第 i i 个火柴的高度,bi b_i 表示第二列火柴中第 i i 个火柴的高度。

    每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?

    于  CodeVS, NOIP, 树状数组, 逆序对 继续阅读

  3. 「HDU 5906」Square Revolution - 后缀数组 + 并查集 + 树状数组

    对于一个给定的字符串 S S ,有多少连续子串是 prefix-suffix-square free 的。

    一个字符串被称为 square 当且仅当它可以由两个相同的串连接而成。例如,ababaa 是 square,而 aaaabba 不是。一个字符串是 prefix-suffix-square free 的当且仅当他的任何前缀或者后缀都不是 square。

    于  Bestcoder, HDU, 后缀数组, 字符串, 并查集, 树状数组, 离线 继续阅读

  4. 「BZOJ 2716」天使玩偶 - CDQ

    维护一个平面,支持以下两种操作:

    1. 加入点 (x, y) (x,\ y)
    2. 查询麦哈顿距离与点 (x, y) (x,\ y) 最小的点。

    于  BZOJ, CDQ, 分治, 数据结构, 树状数组 继续阅读

  5. 「SHOI2007」园丁的烦恼 - CDQ

    每一棵树可以用一个整数坐标来表示,每次询问你某一个矩阵内有多少树。

    于  BZOJ, CDQ, SHOI, 分治, 数据结构, 树状数组 继续阅读

  6. 「CQOI2011」动态逆序对 - CDQ

    对于序列 A A ,它的逆序对数定义为满足 i<j i < j ,且 Ai>Aj A_i > A_j 的数对 (i, j) (i,\ j) 的个数。给 1 1 n n 的一个排列,按照某种顺序依次删除 m m 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

    于  BZOJ, CDQ, CQOI, 分治, 数据结构, 树状数组 继续阅读

  7. 「BZOJ 1176」Mokia - CDQ

    维护一个 N×N N \times N N2000000 N \leq 2000000 )的矩阵,初始值均为 S S 。每次操作可以增加某格子的权值,或询问某子矩阵的总权值。

    修改操作数 160000 \leq 160000 ,询问数 10000 \leq 10000

    于  BZOJ, CDQ, 分治, 数据结构, 树状数组 继续阅读

  8. 「BZOJ 3262」陌上花开 - CDQ

    定义一个序列,序列中每个元素都是一个三元组 Ai=(a, b, c) A_i = (a,\ b,\ c)
    aiaj, bibj, cicj a_i \leq a_j,\ b_i \leq b_j,\ c_i \leq c_j ,则称 Aj A_j Ai A_i 优。
    定义 Ai A_i 的等级为有多少 Aj A_j 满足 Ai A_i Aj A_j 更优。

    求每个等级的元素数量。

    于  BZOJ, CDQ, 分治, 数据结构, 树状数组 继续阅读

  9. 「TJOI2013」最长上升子序列 - 离线 + 树状数组

    给定一个序列,初始为空。现在我们将 1 1 N N 的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?

    于  BZOJ, Splay, TJOI, 树状数组, 离线 继续阅读

  10. 「省选模拟赛」小奇的糖果 - 扫描线 + 链表

    N N 个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的颜色。

    于  安徽集训, 扫描线, 树状数组, 离散化, 链表 继续阅读