Blog
I use blog to record something.
【冷门知识点】支配树
支配树 在一个有向图中，有一个起点R，对于任意点W，对于R->W的任意路径都经过点P，则称P为W的支配点。设idom[i]表示距离i最近的支配点。在原图基础上，idom[i]向i连边构成一颗新树，称为支配树 支配树的性质 1.支...
fhq treap
fhq treap(神仙数据结构) 前置知识：treap平衡树 BST 开始 首先说一下 这个东西可以搞一切bst，treap，splay所能搞的东西 这个东西的学名应该是叫做fhq treap，应该是treap的强化版。 整个数据结...
【偏序，cdq】陌上花开
题面 有 n 个元素，第 i 个元素有 ai bi ci 三个属性，设 f(i) 表示满足 aj≤ai 且 bj≤bi 且 cj≤ci 的 j 的数量。 对于 d∈[0,n) ，求 f(i)=d 的 i 的数量。 输入 第一行两个...
4556woj整除
题面 麦克雷有一个 1→n 的排列，他想知道对于一些区间，有多少对区间内的数（x，y），满足x能被y整除。 输入 第一行包含 2 个正整数 n，m。表示有 n个数，m 个询问。 接下来一行包含n 个正整数，表示麦克雷有的数列。 接下来...
20190525考试
考试 不干啦，爆零啦！ T1选数问题 在麦克雷的面前有N 个数，以及一个 R∗C 的矩阵。现在他的任务是从N 个数中取出R∗C 个，并填入这个矩阵中。矩阵每一行的法值为本行最大值与最小值的差，而整个矩阵的法值为每一行的法值的最大值。现...
【线段树+每一位处理】woj 3763 线段树
题面 请你维护一个线段树 支持一下操作 A x l r 区间 and x O x l r区间 Or x X x l r 区间 Xor x S l r 区间求和 输入 一个数 T表示数据组数 一个数n表示初始序列长 m表示查询...